Incremental Connected Components

This algorithm maintains a set of connected components for growing graphs (added edges only). Under the hood, it uses a disjoint set data structure to keep track of the components.

The AlgorithmExtensions.IncrementConnectedComponents returns a delegate that returns the update component count and map on each call. The delegate is a Func<KeyValuePair<int, IDictionary<TVertex, int>> where Key is the component count and Value is the map of vertices to component index.
var g = new AdjacencyGraph<int, SEdge<int>>();
g.AddVertexRange(new int[] { 0, 1, 2, 3 });
Func<KeyValuePair<int, IDictionary<TVertex, int>> components = AlgorithmExtensions.IncrementalConnectedComponents(g);

var current = components();
Assert.AreEqual(4, current.Key);

g.AddEdge(new SEdge<int>(0, 1));
current = components(); // query algorithm again
Assert.AreEqual(3, current.Key);


See also Boost documentation on this algorithm.

Last edited Mar 30, 2009 at 6:35 AM by pelikhan, version 1

Comments

fan2005 Jul 7, 2014 at 2:58 PM 
Can't get it run!