algorithmgraphdepth-first-searchstrongly-connected-graph

Strongly component


I am trying to write an algorithm that is given a graph G and 2 nodes 'x' and 'y'as input, which returns whether there is a cyclic path from 'x' to 'y'

Is it a good idea to find the strongly connected components first and then check if x and y belong to same strongly connected component.
If they belong to different connected component say x belongs to C1 and y belongs to C2, then if there exists a path from C1 to C2, then we can say that there is a cyclic path from x to y.


Solution

  • Your idea with strongly connected components should work. Here is a graph and some code for you to experiment:

    First, a digraph:

    enter image description here

    And it's adjacency lists representation:

    13 vertices, 22 edges
    0: 5 1
    1: 
    2: 0 3
    3: 5 2
    4: 3 2
    5: 4
    6: 9 4 8 0
    7: 6 9
    8: 6
    9: 11 10
    10: 12
    11: 4 12
    12: 9
    

    And it's strongly connected components:

    enter image description here

    7
    6 8
    9 10 11 12
    0 2 3 4 5
    1
    

    Now, after with implementation for digraph and Kosaraju-Sharir

    class StronglyConnectedComponents
    {
        private bool[] visited;
        private int[] componentIds;
        public int ComponentCount { get; private set; }
    
        public StronglyConnectedComponents(DirectedGraph graph)
        {
            visited = new bool[graph.VertexCount];
            componentIds = new int[graph.VertexCount];
    
            var order = new GraphTraversal(graph).ReverseOrder();
            var reversedGraph = graph.Reverse();
            foreach (var vertex in order)
            {
                if (!visited[vertex])
                {
                    DepthFirstSearch(reversedGraph, vertex);
                    ComponentCount++;
                }
            }
        }
    
        public int VertexComponentId(int vertex)
        {
            return componentIds[vertex];
        }
    
        public bool AreStronglyConnected(int source, int target)
        {
            return componentIds[source] == componentIds[target];
        }
    
        private void DepthFirstSearch(DirectedGraph graph, int vertex)
        {
            visited[vertex] = true;
            componentIds[vertex] = ComponentCount;
            foreach (var adjacent in graph.AdjacentTo(vertex))
            {
                if (!visited[adjacent])
                {
                    DepthFirstSearch(graph, adjacent);
                }
            }
        }
    }
    
    class GraphTraversal
    {
        private Stack<int> reversePostOrder;
        private bool[] visited;
    
        public GraphTraversal(DirectedGraph graph)
        {
            visited = new bool[graph.VertexCount];
            reversePostOrder = new Stack<int>();
    
            for (var vertex = 0; vertex < graph.VertexCount; vertex++)
            {
                if (!visited[vertex])
                {
                    DepthFirstSearch(graph, vertex);
                }
            }
        }
    
        public IEnumerable<int> ReverseOrder()
        {
            return reversePostOrder;
        }
    
        private void DepthFirstSearch(DirectedGraph graph, int vertex)
        {
            visited[vertex] = true;
            foreach (var adjacent in graph.AdjacentTo(vertex))
            {
                if (!visited[adjacent])
                {
                    DepthFirstSearch(graph, adjacent);
                }
            }
            reversePostOrder.Push(vertex);
        }
    }
    
    class DirectedGraph
    {
        public int VertexCount { get; set; }
        public int EdgeCount { get; set; } = 0;
    
        private List<int>[] adjacencyLists;
    
        public DirectedGraph(int vertexCount)
        {
            VertexCount = vertexCount;
            InitializeAdjacencyLists(vertexCount);
        }
    
        public void AddEdge(int from, int to)
        {
            adjacencyLists[from].Add(to);
            EdgeCount++;
        }
    
        public IEnumerable<int> AdjacentTo(int vertex)
        {
            return adjacencyLists[vertex];
        }
    
        public DirectedGraph Reverse()
        {
            var reversedGraph = new DirectedGraph(this.VertexCount);
            for (var vertex = 0; vertex < this.VertexCount; vertex++)
            {
                foreach (var adjacent in this.AdjacentTo(vertex))
                {
                    reversedGraph.AddEdge(adjacent, vertex);
                }
            }
            return reversedGraph;
        }
    
        public override string ToString()
        {
            String graghString = VertexCount + " vertices, " + EdgeCount + " edges \n";
            for (int vertex = 0; vertex < VertexCount; vertex++)
            {
                graghString += vertex + ": ";
                foreach (var adjacnet in this.AdjacentTo(vertex))
                {
                    graghString += adjacnet + " ";
                }
                graghString += "\n";
            }
            return graghString;
        }
    
        private void InitializeAdjacencyLists(int vertexCount)
        {
            adjacencyLists = new List<int>[vertexCount];
            for (var vertex = 0; vertex < vertexCount; vertex++)
            {
                adjacencyLists[vertex] = new List<int>();
            }
        }
    }
    

    Queries like scc.AreStronglyConnected(2, 5) will tell if directed cycle between vertices exists. Runnable code is here.