Representing Vertices in C#

The Problem

You might wonder why this is a problem. After all, I could define a Vertex class very easily and add all the properties I need. The thing is, what properties do I need? As discussed in how to represent a graph in C#, each possible representation requires different information to be stored in a vertex. If we want to build a data structure that is reusable, we have a few different options.

.NET Inheritance

The most straightforward approach is to make use of inheritance in C#. A basic vertex interface can be the base and depending on each graph and/or algorithm, we extend the interface for our purpose.

interface IVertex<T>
{
    T Data
    {
        get;
        set;
    }
}

class MatrixVertex<T> : IVertex<T>
{
    public T Data
    {
        get;
        set;
    }

    public int Index
    {
        get;
        set;
    }
}

The approach is clean and adheres to good object-oriented programming concepts. One possible downside is that it is a bit verbose, specially if we only want to add a few properties to the vertex. A possible solution is to use an abstract class as the base instead of an interface, or we can try something different.

Dictionary

Instead of explicitly defining each property, a vertex can instead have a dictionary that stores property names and their associated value.

class Vertex<T>
{
    T data;
    public Dictionary<string, object> properties;
}

In this case, instead of accessing a property with something like vertex.Index, we would instead use vertex.properties["index"]. This might seem a little strange, specially in C# where properties would make code easier to write, read, and a lot less error-prone.

So what do we gain from this? Flexibility. I do not need to write a new vertex class every time I need to store a new property. I can also use the same vertex across different types of graphs and in different algorithms without having to worry about converting it to the proper vertex class type.

Attribute Dictionary

Finally we can try something that gives us even more flexibility. Instead of defining a dictionary to hold a vertex's properties, we can instead define an dictionary for a single property to hold vertices associated with that property and the corresponding value.

Dictionary<Vertex<string>, int> index = new Dictionary<Vertex<string>, int>();

Vertex<string> vertex1 = new Vertex<string>();
Vertex<string> vertex2 = new Vertex<string>();

index.Add(vertex1, 1);
index.Add(vertex2, 2);

int indexOfVertex2 = index[vertex2];

With this method, properties (whether C# properties, or a dictionary) don't even have to be defined within the vertex, they can be created at any point. A single function can instantly create and employ a property that might only be required for that one function. Additionally since a dictionary is created for each property, there is no need to worry about collisions in the vertex's dictionary.

Another interesting fact is that this method doesn't require an actual vertex class to exist at all. Any hash-able data type can be a "vertex". For example, instead of using Vertex<string>, we can directly create a dictionary as Dictionary<string, int>.

Conclusion

Representing vertices in C# with any of these three methods, along with representing the rest of the graph, brings C# programmers the power of the graph data structure and all the possible algorithms that accompany it.

< Back to part 1 - Representing Graphs in C#

Back to C# Article List

Other C# Articles