Skip to main content

scc_kosaraju

ringkernel_graph::algorithms::scc

Function scc_kosaraju 

Source 
pub fn scc_kosaraju(adj: &CsrMatrix) -> Result<Vec<ComponentId>>
Expand description

Kosaraju’s SCC algorithm.

Two-pass algorithm:

  1. DFS on original graph, record finish order
  2. DFS on transposed graph in reverse finish order

More parallelizable than Tarjan’s.