public List < SCC < N > > getStronglyConnectedComponents ( ) { final Map < N , Node > nodes = new HashMap <> ( ) ; for ( N n : nodes ( ) ) { nodes . put ( n , new Node ( n ) ) ; } final List < SCC < N > > sccs = new ArrayList <> ( ) ; class Tarjan { int index = 0 ; int sccIndex = 0 ; /** * Nodes not yet classified for the strongly connected components */ Stack < Node > pending = new Stack <> ( ) ; void traverse ( ) { for ( Node n : nodes . values ( ) ) { if ( n . index == - 1 ) visit ( n ) ; } } void visit ( Node v ) { v . index = v . lowlink = index ++ ; pending . push ( v ) ; for ( N q : v . edges ( ) ) { Node w = nodes . get ( q ) ; if ( w . index == - 1 ) { visit ( w ) ; v . lowlink = Math . min ( v . lowlink , w . lowlink ) ; } else if ( pending . contains ( w ) ) { v . lowlink = Math . min ( v . lowlink , w . index ) ; } } if ( v . lowlink == v . index ) { // found a new SCC SCC < N > scc = new SCC <> ( sccIndex ++ ) ; sccs . add ( scc ) ; Node w ; do { w = pending . pop ( ) ; w . scc = scc ; scc . members . add ( w . n ) ; } while ( w != v ) ; } } } new Tarjan ( ) . traverse ( ) ; Collections . reverse ( sccs ) ; return sccs ; }
Performs the Tarjan s algorithm and computes strongly - connected components from the sink to source order .