Incremental Connected Components

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.IncrementalConnectedComponents allows to retrieve a delegate that returns the updated 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 graph = new AdjacencyGraph<int, Edge<int>>();
graph.AddVertexRange(new int[] { 0, 1, 2, 3 });
graph.IncrementalConnectedComponents(out Func<KeyValuePair<int, IDictionary<int, int>>> getComponents);

KeyValuePair<int, IDictionary<int, int>> current = getComponents();
Assert.AreEqual(4, current.Key);

graph.AddEdge(new Edge<int>(0, 1));
current = getComponents(); // Query algorithm again
Assert.AreEqual(3, current.Key);

See also Boost documentation on this algorithm.