public List < VertexT > topologicalSort ( ) { Preconditions . checkState ( ! wasSorted ) ; wasSorted = true ; Queue < VertexT > queue = new ArrayDeque <> ( ) ; for ( Map . Entry < VertexT , Integer > entry : vertices . entrySet ( ) ) { if ( entry . getValue ( ) == 0 ) { queue . add ( entry . getKey ( ) ) ; } } List < VertexT > result = Lists . newArrayList ( ) ; while ( ! queue . isEmpty ( ) ) { VertexT vertex = queue . remove ( ) ; result . add ( vertex ) ; for ( VertexT successor : adjacencyList . get ( vertex ) ) { if ( decrementAndGetCount ( successor ) == 0 ) { queue . add ( successor ) ; } } } if ( result . size ( ) != vertices . size ( ) ) { throw new IllegalArgumentException ( "failed to perform topological sort, graph has a cycle" ) ; } return result ; }
one - time use only calling this multiple times on the same graph won t work