Kosaraju.cs

usingSystem.Collections.Generic;
usingSystem.Linq;
usingDataStructures.Graph;

namespaceAlgorithms.Graph;

/// <summary>
/// Implementation of Kosaraju-Sharir's algorithm (also known as Kosaraju's algorithm) to find the
/// strongly connected components (SCC) of a directed graph.
/// See https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm.
/// </summary>
/// <typeparam name="T">Vertex data type.</typeparam>
publicstaticclassKosaraju<T>
{
/// <summary>
/// First DFS for Kosaraju algorithm: traverse the graph creating a reverse order explore list <paramref name="reversed"/>.
/// </summary>
/// <param name="v">Vertex to explore.</param>
/// <param name="graph">Graph instance.</param>
/// <param name="visited">List of already visited vertex.</param>
/// <param name="reversed">Reversed list of vertex for the second DFS.</param>
publicstaticvoidVisit(Vertex<T>v,IDirectedWeightedGraph<T>graph,HashSet<Vertex<T>>visited,Stack<Vertex<T>>reversed)
{
if(visited.Contains(v))
{
return;
}

// Set v as visited
visited.Add(v);

// Push v in the stack.
// This can also be done with a List, inserting v at the begining of the list
// after visit the neighbors.
reversed.Push(v);

// Visit neighbors
foreach(varuingraph.GetNeighbors(v))
{
Visit(u!,graph,visited,reversed);
}
}

/// <summary>
/// Second DFS for Kosaraju algorithm. Traverse the graph in reversed order
/// assigning a root vertex for every vertex that belong to the same SCC.
/// </summary>
/// <param name="v">Vertex to assign.</param>
/// <param name="root">Root vertext, representative of the SCC.</param>
/// <param name="graph">Graph with vertex and edges.</param>
/// <param name="roots">
/// Dictionary that assigns to each vertex the root of the SCC to which it corresponds.
/// </param>
publicstaticvoidAssign(Vertex<T>v,Vertex<T>root,IDirectedWeightedGraph<T>graph,Dictionary<Vertex<T>,Vertex<T>>roots)
{
// If v already has a representative vertex (root) already assigned, do nothing.
if(roots.ContainsKey(v))
{
return;
}

// Assign the root to the vertex.
roots.Add(v,root);

// Assign the current root vertex to v neighbors.
foreach(varuingraph.GetNeighbors(v))
{
Assign(u!,root,graph,roots);
}
}

/// <summary>
/// Find the representative vertex of the SCC for each vertex on the graph.
/// </summary>
/// <param name="graph">Graph to explore.</param>
/// <returns>A dictionary that assigns to each vertex a root vertex of the SCC they belong. </returns>
publicstaticDictionary<Vertex<T>,Vertex<T>>GetRepresentatives(IDirectedWeightedGraph<T>graph)
{
HashSet<Vertex<T>>visited=newHashSet<Vertex<T>>();
Stack<Vertex<T>>reversedL=newStack<Vertex<T>>();
Dictionary<Vertex<T>,Vertex<T>>representatives=newDictionary<Vertex<T>,Vertex<T>>();

foreach(varvingraph.Vertices)
{
if(v!=null)
{
Visit(v,graph,visited,reversedL);
}
}

visited.Clear();

while(reversedL.Count>0)
{
Vertex<T>v=reversedL.Pop();
Assign(v,v,graph,representatives);
}

returnrepresentatives;
}

/// <summary>
/// Get the Strongly Connected Components for the graph.
/// </summary>
/// <param name="graph">Graph to explore.</param>
/// <returns>An array of SCC.</returns>
publicstaticIEnumerable<Vertex<T>>[]GetScc(IDirectedWeightedGraph<T>graph)
{
varrepresentatives=GetRepresentatives(graph);
Dictionary<Vertex<T>,List<Vertex<T>>>scc=newDictionary<Vertex<T>,List<Vertex<T>>>();
foreach(varkvinrepresentatives)
{
// Assign all vertex (key) that have the seem root (value) to a single list.
if(scc.ContainsKey(kv.Value))
{
scc[kv.Value].Add(kv.Key);
}
else
{
scc.Add(kv.Value,newList<Vertex<T>>{kv.Key});
}
}

returnscc.Values.ToArray();
}
}