Job search for a software engineer in 2020 is synonymous with the word "algorithms". With the amount of data that are available for processing these days, the companies want to hire people who are really good at problem-solving and knowing when to use which data structure. But regardless of how much time I spend attempting to comprehend all of this information, there is one topic that just seems harder than the rest of them. And that topic is "graphs".

I understand what a graph is, why, and where it is used, and I even understand the basic traversal algorithms - BSF (Breadth-First Search) and DSF (Depth-First Search). The hardest part, however, is comprehending how a graph is represented in code. During my somewhat recently started career as a software engineer, I have only had to use it a couple of times outside the algorithm challenges on HackerRank, LeetCode, and resources alike. So in this post, I am going to attempt to explain a couple of different ways of representing a graph in C#, with the hope that I will finally remember how to do it. Because the best way to learn something is to teach someone else.

Terminology

Imagine you are learning a different language. If words are just thrown at you without any context, and none of them sound familiar, it's unlikely that you will get very far. But if you had learned some words and developed a vocabulary, even a basic one, then even when you don't quite understand everything, you could still make sense of what was said to you and even attempt to reply. So let's apply the same concept here and learn some new vocabulary.

Graph

It would be silly not to cover what a graph is. In simplest terms, it's just points connected by lines. Points can also be called Vertices (Vertex for singular) or Nodes, and lines are typically called "Edges".

Vertex

This may sound like a bad dictionary, since we already covered it in a "Graph" section, but a vertex is just a point on a graph that can be connected by graph edges.

Edge

This was causing me some confusion for a long time because an "edge" in my mind represents the end of something, or as the internet would say, it is "the outside limit of an object". This is not the case in mathematical graphs though and an edge is just a line that connects two nodes (vertices).

Undirected Graph

In an undirected graph, edges don't have the direction and you can get from node A to node B via the same edge as you would get from node B to node A.

Directed Graph

In the directed graph, each edge has a direction and you can only get from node A to node B if there is an edge pointing in that direction.

Adjacent Vertices

Vertices (nodes) that are connected with exactly one edge. Note: a vertex cannot be adjacent to itself

Edge Weight

This is also referred to as the "cost" of the edge. This is used to define whether one path is better over another one to get from node A to node B. Smaller the weight - the better the path is.

Defining Abstract GraphBase Class

Hopefully, with this new vocabulary, it will be easier for us to look at graph representations in code and not be completely lost. Since we're going to implement two different representations, I am going to start with defining an abstract class which I'll call GraphBase.

public abstract class GraphBase
    {
        protected readonly int NumVertices;
        protected readonly bool Directed;

        public GraphBase(int numVertices, bool directed = false)
        {
            this.NumVertices = numVertices;
            this.Directed = directed;
        }

        public abstract void AddEdge(int v1, int v2, int weight);

        public abstract IEnumerable<int> GetAdjacentVertices(int v);

        public abstract int GetEdgeWeight(int v1, int v2);

        public abstract void Display();

        public int NumVertices { get { return this.numVertices; } }
    }

Adjacency Matrix Representation of a Graph

The code here is pretty simple and self-explanatory. Now let's try to use it and implement a graph using an adjacency matrix. To make it easier to comprehend, I will post the code in chunks. Let's start with the Matrix field and the constructor, which in turn will call GenerateEmptyMatrix method to populate the matrix with empty values (or zeros). This Matrix is going to be our graph representation.

        int[,] Matrix;
        public AdjacencyMatrixGraph(int numVertices, bool directed = false) : base(numVertices, directed)
        {
            GenerateEmptyMatrix(numVertices);
        }

        private void GenerateEmptyMatrix(int numVertices)
        {
            this.Matrix = new int[numVertices, numVertices];
            for (int row = 0; row < numVertices; row++)
            {
                for (int col = 0; col < numVertices; col++)
                {
                    Matrix[row, col] = 0;
                }
            }
        }

If we have a graph with 9 vertices, the matrix will look like this after the constructor is called:

This contains 81 different cells though! That's right, the way it works is if we want to see if a vertex is connected to another vertex, we quickly look it up in this matrix. For example, if we want to see if vertex 0 is connected to vertex 8, we just look at the top right element in the matrix and quickly see that these two nodes aren't connected. Let's add a method to add edges now and see how it changes after we "connect" these two vertices.

public override void AddEdge(int v1, int v2, int weight = 1)
{
    if (v1 >= this.numVertices || v2 >= this.numVertices || v1 < 0 || v2 < 0)
        throw new ArgumentOutOfRangeException("Vertices are out of bounds");

    if (weight < 1) throw new ArgumentException("Weight cannot be less than 1");

    this.Matrix[v1, v2] = weight;

    //In an undirected graph all edges are bi-directional
    if (!this.directed) this.Matrix[v2, v1] = weight;
}            

Nothing too complicated is going on here. We validate that the vertices are within the bounds of the matrix, verify that the weight is no less than 1, and create an edge between the given nodes. If it's not a directed graph, the edge should exist both ways and the matrix will appear to be symmetrical.

Now, let's try adding the edge from vertex 0 to vertex 8 and see how it changes our matrix.

class Program
{
    static void Main(string[] args)
    {
        var adjMatrixGraph = new AdjacencyMatrixGraph(9, false);
        adjMatrixGraph.AddEdge(0, 8);
    }
}

Here's what the matrix looks like after adding this edge:

As you can see, edges from 0 to 8, as well as edges from 8 to 0 were created because it's an undirected graph.

Not so bad thus far but we're not done yet. In order for us to do the graph traversals, we need a way to find the adjacent vertices. Let's implement that next.

public override IEnumerable<int> GetAdjacentVertices(int v)
{
    if (v < 0 || v >= this.numVertices) throw new ArgumentOutOfRangeException("Cannot access vertex");

    List<int> adjacentVertices = new List<int>();
    for (int i = 0; i < this.numVertices; i++)
    {
        if (this.Matrix[v, i] > 0)
            adjacentVertices.Add(i);
    }
    return adjacentVertices;
}

As we can see, getting the adjacent vertices is as simple as iterating over the row in which the given vertex is located, and getting the matching vertices edges to which have a weight value of greater than zero.
Let's add three edges: from 0 to 8, from 0 to 3, and from 8 to 4, and then get the adjacent vertices of the 0th vertex.

var adjMatrixGraph = new AdjacencyMatrixGraph(9, false);
adjMatrixGraph.AddEdge(0, 8);
adjMatrixGraph.AddEdge(0, 3);
adjMatrixGraph.AddEdge(8, 4);
var adjacent = adjMatrixGraph.GetAdjacentVertices(0);

This is what our matrix and adjacent vertices look like:

As you can see, we correctly got 3 and 8 as the vertices adjacent to vertex 0, and correctly ignored vertex 4 because it's adjacent to 8 but not 0. If we now call GetAdjacentVertices on vertex 8, we should get vertices 0 and 4 as adjacent to 8.

var adjacent = adjMatrixGraph.GetAdjacentVertices(8);

One last thing we have to do now is to implement the GetEdgeWeight method. With the matrix representation, it's as easy as getting the value of the "intersection" of vertex1 and vertex2.

public override int GetEdgeWeight(int v1, int v2)
{
    return this.Matrix[v1, v2];
}

This definitely wasn't too bad. Probably the most challenging part is remembering how 2D arrays work in C#.
Now let's take a quick look at another implementation of a graph using an adjacency set.

Adjacency Set Representation of a Graph

To help us with representing a graph using a set, let's define a class named Node that will hold the edges and allow us to easily access the adjacent vertices.

public class Node
{
   private readonly int VertexId;
   private readonly HashSet<int> AdjacencySet;

   public Node(int vertexId)
   {
       this.VertexId = vertexId;
       this.AdjacencySet = new HashSet<int>();
   }

   public void AddEdge(int v)
   {
       if (this.VertexId == v)
           throw new ArgumentException("The vertex cannot be adjacent to itself");
       this.AdjacencySet.Add(v);
   }

   public HashSet<int> GetAdjacentVertices()
   {
       return this.AdjacencySet;
   }
}

Each node will have a VertexId field so we could easily refer to it, as well as an Adjacency HashSet holding the edges. Adding an edge becomes as easy as adding a vertex to the set, and getting adjacent vertices is as simple as returning the AdjacencySet.
Now let's look at the implementation of GraphBase using AdjacencySetGraph. As last time, let's begin with the constructor:

private HashSet<Node> vertexSet;
public AdjacencySetGraph(int numVertices, bool directed = false) : base(numVertices, directed)
{
       this.vertexSet = new HashSet<Node>();
       for (var i = 0; i < numVertices; i++)
       {
           vertexSet.Add(new Node(i));
       }
}

Here, we're creating another set to hold Nodes that represent vertices' information and populate it with the number of vertices specified at the creation of the graph object. Simple enough so far.

Let's look at the AddEdge method:

public override void AddEdge(int v1, int v2, int weight = 1)
{
      if (v1 >= this.numVertices || v2 >= this.numVertices || v1 < 0 || v2 < 0)
           throw new ArgumentOutOfRangeException("Vertices are out of bounds");

      if (weight != 1) throw new ArgumentException("An adjacency set cannot represent non-one edge weights");

      this.vertexSet.ElementAt(v1).AddEdge(v2);

      //In an undirected graph all edges are bi-directional
      if (!this.directed) this.vertexSet.ElementAt(v2).AddEdge(v1);
}

Did you notice a limitation of representing a graph this way? We can't have a weight whose value is not 1. Well, maybe having a GraphBase abstract class was a little premature.
Adding an edge is as simple though as accessing the node with the given VertexId and calling an AddEdge method on it, which, as we remember, just adds the vertex to the set of adjacent vertices. Hence, getting adjacent vertices is as simple:

public override IEnumerable<int> GetAdjacentVertices(int v)
{
      if (v < 0 || v >= this.numVertices) throw new ArgumentOutOfRangeException("Cannot access vertex");
      return this.vertexSet.ElementAt(v).GetAdjacentVertices();
}

And finally, we have to implement GetEdgeWeight method but since we can't have weights whose value is not a 1, we simply return 1:

public override int GetEdgeWeight(int v1, int v2)
{
     return 1;
}

I will leave it to you to figure out the pros and cons of each method, as well as possible issues that weren't handled in each implementation. Hopefully, it will help you on your journey to becoming a graph master. And I believe I am on track to finally "getting" it. If you want, try implementing a Depth-First Search or Breadth-First Search algorithms using either of these graph representations. And if you are reading this and have seen some errors or something you can't stand, leave a message in the comments section and we can discuss that.

Are graphs easy for you?

P.S. I didn't cover a lot of things about graphs in this post. For example, cyclic vs acyclic graphs. This article is about representing basic graphs in code and if you would like more information about the topic, there are a lot of resources online that will help you get deeper into the subject.