ConnectedComponents.cs

/***
 * Connected Components. 
 * 
 * Computes the connected components for undirected graphs.
 * 
 * Provides:
 * * Compute: Returns a list of lists of nodes. Each inner list represents a connected component of nodes.
 */

usingSystem;
usingSystem.Collections.Generic;

usingDataStructures.Graphs;

namespaceAlgorithms.Graphs
{
publicstaticclassConnectedComponents
{
/// <summary>
/// Private helper. Discovers a connected component and return from a source vertex in a graph.
/// </summary>
privatestaticList<TVertex>_bfsConnectedComponent<TVertex>(IGraph<TVertex>graph,TVertexsource,refHashSet<TVertex>visited)whereTVertex:IComparable<TVertex>
{
varcomponent=newList<TVertex>();
varqueue=newQueue<TVertex>();

queue.Enqueue(source);

while(queue.Count>0)
{
varcurrent=queue.Dequeue();

if(!visited.Contains(current))
{
component.Add(current);
visited.Add(current);

foreach(varadjacentingraph.Neighbours(current))
if(!visited.Contains(adjacent))
queue.Enqueue(adjacent);
}
}

returncomponent;
}


/// <summary>
/// Return the the connected components in graph as list of lists of nodes. Each list represents a connected component.
/// </summary>
publicstaticList<List<TVertex>>Compute<TVertex>(IGraph<TVertex>Graph)whereTVertex:IComparable<TVertex>
{
varcomponents=newList<List<TVertex>>();
varvisited=newHashSet<TVertex>();

// Validate the graph parameter
if(Graph==null)
thrownewArgumentNullException();
if(Graph.IsDirected==true)
thrownewNotSupportedException("Directed Graphs are not supported.");
if(Graph.VerticesCount==0)
returncomponents;

// Get connected components using BFS
foreach(varvertexinGraph.Vertices)
if(!visited.Contains(vertex))
components.Add(_bfsConnectedComponent<TVertex>(Graph,vertex,refvisited));

returncomponents;
}
}
}