Following the implementation of the disjointset, another fun algorithm to implement was the offline least common ancestor problem. Tarjan proposed a algorithm based on the disjoint-set and a DFS traversal. Given that I now have all those ingredients in QuickGraph, it was just a matter of hooking together the implementation with the right events. The beef of the implementation looks as follows (and looks quite elegant to me):

var gpair = GraphExtensions.ToAdjacencyGraph(this.pairs);
// for fast lookup var disjointSet = new ForestDisjointSet

(); var vancestors = new Dictionary(); var dfs
= new DepthFirstSearchAlgorithm(this, this.VisitedGraph, new DictionaryGraphColor>>(this.VisitedGraph.VertexCount));
dfs.InitializeVertex += (sender, args) => disjointSet.MakeSet(args.Vertex); dfs.DiscoverVertex
+= (sender, args) => vancestors[args.Vertex] = args.Vertex; dfs.TreeEdge += (sender,
args) => { var edge = args.Edge; disjointSet.Union(edge.Source,
edge.Target); vancestors[disjointSet.FindSet(edge.Source)] = edge.Source; }; dfs.FinishVertex
+= (sender, args) => { foreach (var e in gpair.OutEdges(args.Vertex)) if (dfs.VertexColors[e.Target]
== GraphColor.Black) this.ancestors[EdgeExtensions.ToVertexPair(e)]
= vancestors[disjointSet.FindSet(e.Target)]; }; // go! dfs.Compute(root);

Enjoy!