The Graph Theory in C# (Part 7)

The Edge is a monster of a beast!

Let's get right down to business. Before I jump in to the Edge's constructor, I mentioned that the Edge needs an ID and IDGenerator as well like the Vertex.

public class Edge
{

    ...

    public int ID { get; private set; }

    protected static class IDGenerator
    {
        private static int _id = 0;

        public static int Generate()
        {
            return ++_id;
        }
    }
}

This code defines Edge's own IDGenerator as a protected class, making it pretty much available only to the Edge. Note that the code is different from the Vertex's IDGenerator. For the Edge, the IDs generated cannot be influenced outside of the Edge, so there was no need to have a Seed() method. To prove that point, the Edge's constructor does not accept an ID parameter.

    protected Edge(Vertex tail, Vertex head, 
        bool directed = false, int weight = 0, string label = "")
    {
        ID = IDGenerator.Generate();
        Tail = tail;
        Head = head;
        Directed = directed;
        Weight = weight;
        Label = label;
    }

This code defines a protected constructor that prevents the Edge from getting instantiated outside the Edge. The constructor calls the IDGenerator to generate the Edge's ID, exposed as a read-only property. Only the constructor accesses the IDGenerator. This is the reason why I decided to make the IDGenerator protected: no one can call it anyway except the Edge's constructor, which, remember, no one can access.

I know I said the Edge is monstrous beast, but I didn't say it's going to be a ghost, right? The Edge should still provide a way to be instantiated, so I added a Create() method and made it static, which means that it can be accessed without having to instantiate the Edge.

    protected internal static Edge Create(Vertex tail, Vertex head, 
        bool directed = false, int weight = 0, string label = "")
    {
        return new Edge(tail, head, directed, weight, label);
    }

This code defines Create() as a protected internal method, making it accessible to the Edge and to the classes in the same assembly. To be specific, the other class that we will allow access to this method is the Graph. Only the Graph knows its Vertices, so it is the best class to create and validate Edges. This means that we'll have to revisit the Graph and add more features to it. We'll get to that later.

For now, let's see... are we done? Nope! Let's add the test for equality via ID like what we did for the Vertex. Also, let's add a property that returns the Edge's name, which is basically the edge's DOT representation. I call this property Name, which is just a mnemonic to call the ToString() method, overridden to return the edge's DOT notation with support for directed and undirected edges. Below is the full code.

Edge.cs
using System;
using System.Collections.ObjectModel;

namespace Mendz.Graphs
{
    public class Edge
    {
        public const string DIRECTED_DOT_NOTATION = " -> ";
        public const string UNDIRECTED_DOT_NOTATION = " -- ";

        protected Vertex[] _endpoints = new Vertex[2];

        public int ID { get; private set; }

        public string Name
        {
            get
            {
                return ToString();
            }
        }

        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; }

        protected Edge(Vertex tail, Vertex head, 
            bool directed = false, int weight = 0, string label = "")
        {
            ID = IDGenerator.Generate();
            Tail = tail;
            Head = head;
            Directed = directed;
            Weight = weight;
            Label = label;
        }

        public override bool Equals(object obj)
        {
            if (obj == null || !(obj is Edge))
            {
                return false;
            }
            return ID == ((Edge)obj).ID;
        }

        public override int GetHashCode()
        {
            return ID;
        }

        public override string ToString()
        {
            return Tail.Value.ToString() 
                + (Directed ? DIRECTED_DOT_NOTATION : UNDIRECTED_DOT_NOTATION) 
                + Head.Value.ToString();
        }

        protected internal static Edge Create(Vertex tail, Vertex head, 
            bool directed = false, int weight = 0, string label = "")
        {
            return new Edge(tail, head, directed, weight, label);
        }

        protected static class IDGenerator
        {
            private static int _id = 0;

            public static int Generate()
            {
                return ++_id;
            }
        }
    }
}

Notice that in order to generate the DOT string, I expected the Tail and Head (Vertex.Value) values to be convertible to string. It is important therefore that the Vertex.Value's ToString() method returns a meaningful text for the graph. This would be important especially when using the DOT generated to render or visualize the graph.

The edge plays an important role in the existence of a graph. The graph is just a list of vertices/values without the edges. However, in order for the graph to be reliable, it should have edges that do not violate the definition of the edge: where it should contain a pair of vertices known by the graph. Thus, I defined Edge in such a way that it cannot be created on its own. Rather, it must be created through the Graph itself.

The Edge has many possible properties and features. The most popular ones are defined here. This Edge class can be inherited and extended with additional attributes and behaviors as needed. As far as I'm concerned, the Edge is complete. It is time to revisit the Graph.