Adjacency List

In graph theory, the adjacency list is defined as a collection of unordered lists used to represent a finite graph, where each list describes the set of neighbors of a vertex in the graph (Wikipedia). Mendz.Graphs.AdjacencyList implements an enhanced adjacency list that can also be used to retrieve the incidence.

An adjacency list, by definition, is very focused on the vertices. When I implemented my adjacency list to be a dictionary of dictionaries, I was convinced that the second dictionary should store the incidence as its value. Sure I could've used a simpler collection type to avoid the need for this, but it feels like a waste of opportunities as you will see in the AdjacencyList.Fill() method's implementation.

Creating a list using Mendz.Graphs starts with inheriting the GraphListBase.

    public class AdjacencyList 
        : GraphListBase<ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>>>
    {
        public AdjacencyList(Graph graph)
            : base(graph)
        {

        }
    }

This code defines the AdjacencyList class that inherits the GraphListBase with the list type set as a dictionary of dictionaries. It shows that the constructor requires a graph instance, which is stored to and exposed via Graph property.

        public override void Initialize()
        {
            List = new ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>>();
            Graph.Vertices
                .AsParallel()
                .ForAll((vertex) => 
                    List.TryAdd(vertex.Key, new ConcurrentDictionary<int, Edge>()));
        }

This code shows the implementation of the Initialize() method. Observe that it doesn't just create an empty dictionary of dictionaries. Instead, it creates a vertex ID pre-filled dictionary of empty dictionaries. Note also that the pre-fill is performed as a parallel operation on Graph.Vertices.

        public override ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>> Fill()
        {
            Initialize();
            Graph.Edges
                .AsParallel()
                .ForAll((edge) => AdjacencyList.SetEntries(List, edge.Value));
            return List;
        }

This code shows the implementation of the Fill() method. It starts by calling the Initialize() method. Note that the fill is performed as a parallel operation on Graph.Edges. This is the reason why I chose the ConcurrentDictionary as my list type. I need my list to be inherently thread-safe. The actual fill operation itself is a call to a static SetEntries() method.

        private static void SetEntries(
            ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>> list, 
            Edge edge)
        {
            int tailID = edge.Tail.ID;
            int headID = edge.Head.ID;
            list[tailID].TryAdd(headID, edge);
            if (!edge.Directed)
            {
                list[headID].TryAdd(tailID, edge);
            }
        }

This code shows the List being filled based on an edge. Let me repeat that: based on an edge. This is exactly the reason why I wanted to store the incidence as well in my adjacency list: I already have the information at hand and I have a place to store it to right here, right now!

Now, to really find the value of this design, you have to see how an adjacency list can be used. For now, here's the full code.

AdjacencyList.cs
using System.Collections.Concurrent;
using System.Linq;

namespace Mendz.Graphs.Representations.Lists
{
    public class AdjacencyList 
        : GraphListBase<ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>>>
    {
        public AdjacencyList(Graph graph)
            : base(graph)
        {

        }

        public override void Initialize()
        {
            List = new ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>>();
            Graph.Vertices
                .AsParallel()
                .ForAll((vertex) => 
                    List.TryAdd(vertex.Key, new ConcurrentDictionary<int, Edge>()));
        }

        public override ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>> Fill()
        {
            Initialize();
            Graph.Edges
                .AsParallel()
                .ForAll((edge) => AdjacencyList.SetEntries(List, edge.Value));
            return List;
        }

        private static void SetEntries(
            ConcurrentDictionary<int, ConcurrentDictionary<int, Edge>> list, 
            Edge edge)
        {
            int tailID = edge.Tail.ID;
            int headID = edge.Head.ID;
            list[tailID].TryAdd(headID, edge);
            if (!edge.Directed)
            {
                list[headID].TryAdd(tailID, edge);
            }
        }
    }
}