Kosaraju.cs

using System.Collections.Generic;
using System.Linq;
using DataStructures.Graph;

namespace Algorithms.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>
    public static class Kosaraju<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>
        public static void Visit(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 (var u in graph.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>
        public static void Assign(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 (var u in graph.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>
        public static Dictionary<Vertex<T>, Vertex<T>> GetRepresentatives(IDirectedWeightedGraph<T> graph)
        {
            HashSet<Vertex<T>> visited = new HashSet<Vertex<T>>();
            Stack<Vertex<T>> reversedL = new Stack<Vertex<T>>();
            Dictionary<Vertex<T>, Vertex<T>> representatives = new Dictionary<Vertex<T>, Vertex<T>>();

            foreach (var v in graph.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);
            }

            return representatives;
        }

        /// <summary>
        /// Get the Strongly Connected Components for the graph.
        /// </summary>
        /// <param name="graph">Graph to explore.</param>
        /// <returns>An array of SCC.</returns>
        public static IEnumerable<Vertex<T>>[] GetScc(IDirectedWeightedGraph<T> graph)
        {
            var representatives = GetRepresentatives(graph);
            Dictionary<Vertex<T>, List<Vertex<T>>> scc = new Dictionary<Vertex<T>, List<Vertex<T>>>();
            foreach (var kv in representatives)
            {
                // 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, new List<Vertex<T>> { kv.Key });
                }
            }

            return scc.Values.ToArray();
        }
    }
}