Using Mendz.Graphs..AdjacencyList

Mendz.Graphs.Representations.Lists.AdjacencyList implements an adjacency list. So, how do you use it?

First, let's get organized. The way I did it, Mendz.Graphs.Representations.* is actually in the same Mendz.Graphs project. I simply added a folder named Representations, in which I added a sub-folder named Lists. Representations contain the representation base classes. Representations\Lists contains the AdjacencyList.



Now, remember I like console applications to quickly appreciate my work? So that's what we're gonna do here. In Visual Studio, create a console application project that references Mendz.Graphs. In Program.cs Main(), initialize the graph.

Graph graph = new Graph();
int order = 2500;
for (int i = 1; i <= order; i++)
{
    graph.AddVertex(i, i);
}
Random random = new Random();
bool directed = false; // true
int size = 1250;
for (int i = 1; i <= size; i++)
{
    graph.AddEdge(random.Next(1, order + 1), random.Next(1, order + 1), directed);
}
Console.WriteLine(graph.ToString());
int vertexID = 250; // pick a vertex ID with neighbors

This code creates a graph with an order of 2500 vertices and a size of 1250 randomized edges.

Without Adjacency List

The main problem that the adjacency list solves is how to find all the vertices adjacent to a vertex v -- by "adjacent" it means that the vertex v is one of the endpoints in an edge. By using the raw graph data, trying to achieve this would require looping through all edges in order to find where the vertex v appears as an endpoint.

// if undirected, meaning directed = false
var q1 = from edgeID in (graph.Edges.Keys)
         where (edgeID.tail == vertexID || edgeID.head == vertexID)
         select graph.GetVertex((edgeID.tail == vertexID ? edgeID.head : edgeID.tail));
// if directed, meaning directed = true
//var q1 = from edgeID in (graph.Edges.Keys)
//         where (edgeID.tail == vertexID)
//         select graph.GetVertex(edgeID.head);
foreach (var vertex in q1)
{
    Console.WriteLine("[" + vertex.ID + "] " + vertex.Value);
}

The vertices found are the neighbors of the vertex v. Note that it should be taken into account whether the edge is directed or undirected. If the edge is undirected, then the vertex v can either be the tail or the head. If the edge is directed, the vertex v is always the tail and its neighbor is always the head. As you can imagine, the query would be more complicated if the graph is a mix of directed and undirected edges. Although this code does the job, note that it scans the entire 1250 edges to list just a single vertex v's neighborhood. If you need to list the neighbors of each vertex in Graph.Vertices, that's an easy 2500 * 1250 = 3,125,000 iterations!

With Adjacency List

With an adjacency list, listing the neighborhood is simpler. When the adjacency list was filled, it already performed all the iterations through the graph's vertices and edges, while applying the directed/undirected rule on each edge. Therefore, you can consume AdjacencyList.List over and over with the confidence that graph.Edges is no longer iterated each time.

AdjacencyList adjacencyList = new AdjacencyList(graph);
adjacencyList.Fill();
foreach (var id in adjacencyList.List.Keys
    .Where((key) => adjacencyList.List[key].Count > 0))
{
    Console.WriteLine(id.ToString());
}

This code lists only the vertices with neighbors. Note that the same adjacency list can be used to also identify the vertices with no neighbor.

foreach (var id in adjacencyList.List.Keys
    .Where((key) => adjacencyList.List[key].Count == 0))
{
    Console.WriteLine(id.ToString());
}

This is important to understand about Mendz.Graphs.AdjacencyList. Although most adjacency list implementations focus on listing only the vertices with neighbors, Mendz.Graphs.AdjacencyList does more by also listing the vertices with no adjacency or incidence. I don't know about you, but to me, that's an important information by itself. In a social networking application, for example, besides knowing which members have started to network, you might also be interested in knowing which members have not started networking yet. With that knowledge, you can have a list of members to target for a campaign that would encourage them to start networking.

var q2 = from id in adjacencyList.List[vertexID].Keys
         select graph.GetVertex(id);
foreach (var vertex in q2)
{
    Console.WriteLine("[" + vertex.ID.ToString() + "] " + vertex.Value.ToString());
}

This code lists the neighbors of the vertex with ID = vertexID. Using the social networking analogy, this is as good as listing out your friends, or the people you are directly linked to. The result can be different when the edges are directed or undirected. If directed, this will list only the friends you added in your friend list. If undirected, this will also list the people who added you as a friend, even if they are not in your friend list (yet).

Incidence List

With Mendz.Graphs.AdjacencyList, the following can also be achieved, which lists the edges incident to the vertex v -- by "incident" it means that the edge has the vertex v as one of the endpoints. This is also called an "incidence list".

foreach (var edge in adjacencyList.List[vertexID].Values)
{
    Console.WriteLine(edge.Name);
}

DFS on Adjacency List

The adjacency list can be traversed to produce a "subgraph" starting from the vertex with ID = vertexID. Imagine starting from a single vertex, spanning out to its neighbors, then crawling out to each neighbor's neighbors, on and on, etc. In a social networking application, for example, this is the same as listing out your friends AND "friends of friends". ;-)

HashSet<Edge> subgraphEdges = new HashSet<Edge>();
traversed = new HashSet<int>();
Action<int> traverse = (id) =>
    {
        if (!traversed.Contains(id))
        {
            traversed.Add(id);
            foreach (var item in adjacencyList.List[id])
            {
                subgraphEdges.Add(item.Value);
                traverse(item.Key);
            }
        }
    };
traverse(vertexID);
Console.WriteLine((directed ? "di" : "") + "graph G" + vertexID.ToString() + " {");
foreach (var edge in subGraphEdges)
{
    Console.WriteLine(" " + edge.Name + ";");
}
Console.WriteLine("}");

This code defines a depth-first search (DFS) traverse action that uses recursion to crawl from a starting vertex to its neighbors, to each neighbor's neighbors, on and on, etc. It keeps track of the vertices already traversed to avoid an infinite loop, which can happen if the graph has a cycle. The traversal builds a list of edges which is then used to print out the resulting subgraph's DOT notation.

Mendz.Graphs intentionally does not include algorithms. I encourage developers to build their own algorithm library or libraries based on Mendz.Graphs.