[Algo] Directed Graph & Strong Connectivity

DAG: Topological Sorting

• We can do topological sorting by both DFS and BFS traversal.
• Both DFS and BFS provides us a way to calculates DP values based on Topological Sorting order. But they are slightly different.
  • In DFS, we aggregates successors’ DP values to get ancestors’ value. When we backtrack to the ancestor node, we are sure all its successors’ DP values are ready. This is more like a bottom-up approach. For example, we can calculate “number of successors” etc.
  • In BFS, we push ancestor’s value to its successor. When we traverse to the successor node, we are sure all its ancestor’s DP values are ready. This is more like a top-down approach. For example, we can calculate “number of different paths”, “shortest/longest path” etc.

// DFS
void DFS(int cur ...) {
  if (vis[cur]) return;
  
  // We can push some partial_value from the current node to its successors.
  partial_value;
  
  for (auto next:graph[cur]) {
    DFS(next, partial_value ...);
  }

  // DP values are aggregated from all its successors to the current node.
  dp[cur] = aggregate(dp[next1], dp[next2] ...);
  postorder_nodes.push_back(cur);
}
std::reverse(postorder_nodes.begin(), postorder_nodes.end());

// BFS
while (!q.empty()) {
  int sz=q.size();
  for (int i=0;i<sz;++i) {
    int cur=q.front(); q.pop();

    // DP values are aggregated from all its ancestors to the current node.
    dp[cur] = aggregates(ancestor_dp[cur] ...)

    for (auto next:graph[cur]) {
      // We push current node's DP value to all its successors.
      ancestor_dp[next].push_back(dp[cur]);
      
      indegree[next]--;
      if (indegree[next]==0) {
        q.push(next);
      }
    }
  }
}

Successor Graph

• A special type of directed graph, where all nodes’ out degree is 1. This can be represent as a succ vector, where the i-th value is the successor node. The important property of this type of graph is that, it will contain one or more component. Each component contains a cycle and zero, one or more paths that lead to the cycle.
• Successor graph can be called functional graphs. Because it correspond to a function which maps one node to another according to the edge. We can then compose higher order function base on this function. More specifically, succ(x, k) = succ(succ(x, k-1), 1)
• Successor graph can be viewed as a set of reversed trees too. Finding ancestor in the tree is the same as finding successor here.
• Successor graph can be viewed as a set of single linked lists too. Single linked list algorithms, e.g. two pointers algorithms apply here too.

// A divide and conquer method to calculate succ(x, k) faster
std::vector<std::vector<int>> succ(max_pw2+1, std::vector<int>(n));
succ[0] = original_succ;

// Calculate for 2^i
for (int i=1;i<=max_pw2;++i) {
  for (int j=0;j<n;++j) {
    succ[i][j] = succ[i-1][succ[i-1][j]];
  }
}

// Query succ(x, k) in log(k) time
int pw2 = 0;
while (k) {
  if (k & (1<<pw2)) {
    x = succ[pw2][x];
    k -= (1<<pw2);
  }
  pw2++;
}

// Slow-Fast pointers to find cycle start nodes
// This only traverses a possible path and the cycle. But
// there could be zero, one or multiple paths to the cycle.
int s=f=start;
do {
  s = succ[s];
  f = succ[succ[f]];
} while (s!=f);

// After the loop, slow-fast pointers will both stop
// at the intersect point of the list and the cycle.
// Based on the intersect point, we can traverse the
// cycle, or traverse the path to the cycle.
s=start;
while (s!=f) {
  s=succ[s];
  f=succ[f];
}

Strong Connectivity

Kosaraju algorithm is a O(n) method to find the strongly connected components in the directly graph.

1. It first sort all nodes by the reverse of post order of the original graph. (This is the same as finding the topological sort order in acyclic graph)
2. Then it does a depth first search on the reversed graph. Each DFS search tree is a strongly connected component.

The first traversal gives us a list of nodes, where nodes in the front can reach nodes in the back. The second traversal is on the reversed graph. So if nodes in the front can reach nodes in the back, it means in the original graph, nodes in the back can reach nodes in the front too. It is a strongly connect component.

In the second traversal, since we are traversing on a special order, it will not traverse to another strongly connected component. If so, those connected component must be traversed before the traverse of current connected component.

// First DFS traversal
void DFS1(int cur, graph ...) {
  if (vis[cur]) return;  
  for (auto next:graph[cur]) {
    DFS(next ...);
  }
  postorder_nodes.push_back(cur);
}

for (int i=0;i<n;++i) {
  DFS1(i, graph);
}
std::reverse(postorder_nodes.begin(), postorder_nodes.end());

// Second DFS traversal
void DFS2(int cur, int component_id, reversed_graph ...) {
  if (vis[cur]) return;  
  for (auto next:reversed_graph[cur]) {
    DFS(next ...);
  }
  components[cur] = component_id
}

int component_id=0;
for (int i=0;i<n;++i) {
  DFS2(postorder_nodes[i], component_id++, reversed_graph);
}