The Graph Theory in C# (Part 6)

Graph is a class with two main properties: a list of Vertex objects and a list of Edge objects. Vertex is a class with two main properties: an ID and a Value. Edge is a beast. Creating a class of type Edge is an exercise of self-control and avoiding temptations. As redundant as it may sound, the Edge can literally take you to the edge.

Say what?! Yes, exactly! Finding a definition of the edge in graph theory is like reading everything about graphs. The edge is as fundamental to the graph as the vertex. In fact, that's how Wikipedia describes it. Even WolfamAlpha's definition is painful to read. The simplicity of how the Boost Graph Library defines the edge won me over:

... an edge is a pair (u,v) with u,v in V.

The edge is basically a pair of vertices. However, if I should create a class for edge, I can't just say it has vertex#1 and vertex#2. That's so lame! I believe that if something is important, the language would have a name for it. If you read and search some more about edges, you'll find that the vertices of an edge are also called its endpoints. Endpoint#1 and endpoint#2? Lame! Finally, I settled with tail and head. Although it seems to suggest focus on directed graphs, it doesn't really matter for undirected graphs. I tossed a coin heads or tails, and decided to let both sides of the coin win.

public class Edge
{
    protected Vertex[] _endpoints = new Vertex[2];

    public string Label { get; set; }

    public ReadOnlyCollection<vertex> EndPoints
    {
        get
        {
            return new ReadOnlyCollection<vertex>(_endpoints);
        }
    }

    public Vertex Tail
    {
        get
        {
            return _endpoints[0];
        }
        private set
        {
            if (value == null)
            {
                throw new ArgumentNullException();
            }
            _endpoints[0] = value;
        }
    }

    public Vertex Head
    {
        get
        {
            return _endpoints[1];
        }
        private set
        {
            if (value == null)
            {
                throw new ArgumentNullException();
            }
            _endpoints[1] = value;
        }
    }

    public bool Directed { get; set; }

    public int Weight { get; set; }
}

This code defines a class Edge with properties Tail and Head. Setting these properties also set the Edge's internal representation of its endpoints, which is basically an array of two Vertex instances. Because "endpoints" appeared in some definitions of the edge, I decided to expose the internal endpoints as a read-only property EndPoints. An edge can be directed? A Directed property should exist then to indicate if the edge is directed (true) or undirected (false). An edge can have weight so let's add Weight, too. I read about labels. Label then. Anything else?! You graph scientist don't want to stop?!! You want a piece of me?!!!

Now I need a way to identify an Edge from the bunch. In the same tradition as the Vertex, the Edge needs an ID and an IDGenerator. That seems easy enough to do. I can simply pattern the code after Vertex and how the IDGenerator was used, right? Wrong!

If you look back at the edge's definition, it specifically said that the edge's endpoints (head and tail) should be a pair of vertices that are in the graph's list of vertices. This means that I would need to put in some form of validation against the graph's vertices. But the Edge can't know anything about the Graph. Also, I can't just let users of my library create an Edge instance without any guarantee that the endpoints are known by the Graph. I need a way to let users create an Edge without letting them directly create an Edge.

How in the world would I do that?!