Search⌘ K
Home
Courses
Learn Graph Algorithms in C++

Implementation of Kosaraju's Algorithm

Explore how to implement splitting a graph into its strongly connected components.

We'll cover the following...

Implementing SCC identification

Our implementation of Kosaraju’s algorithm uses similar building blocks as our topological sort implementation. The setup of the class is similar, again using the adjacency list graph representation.

C++ 17
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<vector<int>> AdjacencyList;
enum class NodeState {UNVISITED, IN_PROGRESS, FINISHED};
class StronglyConnectedComponents {
private:
    AdjacencyList adjacencyList;
    vector<NodeState> nodeStates;
    vector<int> finishOrder;
    // vector to store the resulting SCCs
    vector<vector<int>> scc;
public: 
    StronglyConnectedComponents(AdjacencyList _adjacencyList) 
        : adjacencyList {_adjacencyList} 
        , nodeStates {vector<NodeState>(adjacencyList.size(), NodeState::UNVISITED)}
    {}
    vector<vector<int>> computeScc() {
        // TODO
    }
    // similar DFS routine as for topological sort
    void dfs(int u) {
        this->nodeStates[u] = NodeState::IN_PROGRESS;
        for (int v : this->adjacencyList[u]) {
            // we ignore back edges and redundant edges here
            if (this->nodeStates[v] == NodeState::UNVISITED) { 
                this->dfs(v); 
            }
        }
        this->nodeStates[u] = NodeState::FINISHED;
        this->finishOrder.push_back(u);
    }
};

We’ve also borrowed the dfs routine from the topological sort class, which keeps track of the node finishing order during DFS. The main work will be done in the yet unfinished computeScc function (line 21). The variable scc (line 14) will be used to store the strongly connected components while they compute. Each SCC is represented as a vector<int> of the nodes it contains, and in total, all SCCs form a vector<vector<int>>.

Let’s start implementing computeScc. First, we need to run the forward pass DFS.

C++ 17
for (int u = 0; u < this->adjacencyList.size(); ++u) {
    if (this->nodeStates[u] == NodeState::UNVISITED) {
        this->dfs(u);
    }
}
// get the reverse finishing order
vector<int> traverseOrder(finishOrder.rbegin(), finishOrder.rend());

This is a straightforward DFS from all starting nodes. In the end, we’ll obtain the reverse finishing order for the backward DFS. We now have to do some bookkeeping before we run the backward DFS.

fill(this->nodeStates.begin(), this->nodeStates.end(), NodeState::UNVISITED);
this->finishOrder.clear();
this->transpose();

Here, we’ll reset all nodes to be unvisited and clear the finishOrder vector populated by the dfs. we’ll use it during the backward pass to store the newly discovered SCC. We’ll also call the transpose function to reverse all edges. Its implementation looks like this:

C++ 17
void transpose() {
    // create new transposed adjacency list
    AdjacencyList tmp = AdjacencyList(this->adjacencyList.size());
    for (int u = 0; u < this->adjacencyList.size(); ++u) {
        for (int v : this->adjacencyList[u]) {
            // add reverse edge (v, u)
            tmp[v].push_back(u);
        }
    }
    // replace the adjacency list
    this->adjacencyList = tmp;
}

In ...