Wrapping up the dependency graph project just wanted to illustrate one as I think interesting challenge which is how to persist the graph.

The dilemma was this. Given a digraph represented with adjacency list

public class Digraph  
{
    public int V { get; private set; }
    public int E { get; private set; }

    private HashSet<int>[] _adj;
    // ...
}

how do we persist the graph without coupling it to some storage mechanism and violating encapsulation? What I mean by that is there are two bad design choices that we want to avoid. First one is to add Save method to the diagraph class which would loop over the internal adjacency list and save data to say, SQL Server or Redis. Among of the problem this solution creates is necessity to take a dependency on some storage library and also violating the single responsibility principle. Second slightly better choice is to make adjacency list public and have some other class to loop through the vertices and save them. This is also problematic because the other class would have to know the internal details of the digraph and plus they may be a need to initialize some digraph private properties which only digraph knows about.

This is exactly the reason why memento design pattern exists and here's how it works in practice in this situation.

First we need a generic Memento class:

public class Memento<T>  
{
    public Memento(T state)
    {
        this.State = state;
    }

    public T State { get; set; }
}

Next we have a method in Digraph to create memento:

public Memento<int[][]> CreateMemento ()  
{            
    var jaggedArray = new int[V][];
    for (int i = 0; i < V; i++)
    {
        jaggedArray[i] = _adj[i].ToArray();
    }            
    return new Memento<int[][]>(jaggedArray);
}

All Digraph knows that in order to persist himself it needs to return a jagged array built out of its adjacency list.

On the opposite side, when it is given a jagged array, it needs to be able to restore its state which is done in SetMemento method:

public void SetMemento (Memento<int[][]> memento)  
{            
    if (memento == null)
    {
        throw new ArgumentNullException(nameof(memento));
    }

    var jaggedArray = memento.State;
    V = jaggedArray.Count();
    _adj = new HashSet<int>[V];
    for (int v = 0; v < V; v++)
    {
        _adj[v] = new HashSet<int>(jaggedArray[v]);
        E += jaggedArray[v].Count();
    }
}

Once thing to note is in addition to restoring the array, this method also set E and V properties, which again only Digraph has knowledge of.

On a storage side we have a repository with two methods, first of which is SaveState

public void SaveState(DependencyGraph dg)  
{ 
    int[][] jaggedArray = dg.Digraph.CreateMemento().State;

    // Save
    using (var ctx = new DependencyGraphContext(_connectionString))
    {
        ctx.Database.ExecuteSqlCommand("TRUNCATE TABLE DependencyGraphModule;");
        ctx.Database.ExecuteSqlCommand("TRUNCATE TABLE DependencyGraph;");

        for (int i = 0; i < jaggedArray.Length; i++)
        {
            var json = JsonConvert.SerializeObject(jaggedArray[i]);
            ctx.Vertices.Add(new SqlStorage.Vertex { VertexId = i, AdjacencyListJson = json });
        }
        ctx.SaveChanges();
    }
}

Repository has no knowledge of Digraph internal structure, all it needs to do is ask Digraph to create memento object and then save the array. In this case I use EF, but it can be changed easily to any other storage mechanism.

Loading state from database and initializing the digraph is just the opposite:

public DependencyGraph LoadState()  
{
    int[][] jaggedArray;

    // Load
    using (var ctx = new DependencyGraphContext(_connectionString))
    {
        jaggedArray = new int[ctx.Vertices.Count()][];                
        for (int i = 0; i < jaggedArray.Length; i++)
        {
            var json = ctx.Vertices.Find(i).AdjacencyListJson;
            int[] adjencencyList = JsonConvert.DeserializeObject<int[]>(json);
            jaggedArray[i] = adjencencyList;                    
        }

    var g = new Digraph(new Memento<int[][]>(jaggedArray));
    return dg;
}

Repository gets the array from database and then passes it on to the digraph in the constructor. You can see the complete code here.