public static < T > List < T > toposort ( T root , Deps < T > deps ) { List < T > order = new ArrayList < T > ( ) ; HashSet < T > done = new HashSet < T > ( ) ; Stack < T > todo = new Stack < T > ( ) ; HashSet < T > ancestors = new HashSet < T > ( ) ; // Run a Tarjan (1976) style topological sort. todo . push ( root ) ; while ( ! todo . isEmpty ( ) ) { T x = todo . peek ( ) ; // Whether all x's descendents are done. boolean ready = true ; for ( T y : deps . getDeps ( x ) ) { if ( ! done . contains ( y ) ) { ready = false ; todo . push ( y ) ; } } if ( ready ) { todo . pop ( ) ; ancestors . remove ( x ) ; if ( done . add ( x ) ) { order . add ( x ) ; } } else { if ( ancestors . contains ( x ) ) { throw new IllegalStateException ( "Graph is not a DAG. Cycle involves node: " + x ) ; } ancestors . add ( x ) ; } } return order ; }
Gets a topological sort for the graph .