private static < T > @ NonNull List < T > topologicalSort ( final @ NonNull Graph < T > graph , final @ NonNull SortType < T > type ) { checkArgument ( graph . isDirected ( ) , "the graph must be directed" ) ; checkArgument ( ! graph . allowsSelfLoops ( ) , "the graph cannot allow self loops" ) ; final Map < T , Integer > requiredCounts = new HashMap <> ( ) ; for ( final T node : graph . nodes ( ) ) { for ( final T successor : graph . successors ( node ) ) { requiredCounts . merge ( successor , 1 , ( a , b ) -> a + b ) ; } } final Queue < T > processing = type . createQueue ( ) ; final List < T > results = new ArrayList <> ( ) ; for ( final T node : graph . nodes ( ) ) { if ( ! requiredCounts . containsKey ( node ) ) { processing . add ( node ) ; } } while ( ! processing . isEmpty ( ) ) { final T now = processing . poll ( ) ; for ( final T successor : graph . successors ( now ) ) { final int newCount = requiredCounts . get ( successor ) - 1 ; if ( newCount == 0 ) { processing . add ( successor ) ; requiredCounts . remove ( successor ) ; } else { requiredCounts . put ( successor , newCount ) ; } } results . add ( now ) ; } if ( ! requiredCounts . isEmpty ( ) ) { final StronglyConnectedComponentAnalyzer < T > analyzer = new StronglyConnectedComponentAnalyzer <> ( graph ) ; analyzer . analyze ( ) ; throw new CyclePresentException ( "Graph (" + graph + ") has cycle(s): " + analyzer . renderCycles ( ) , analyzer . components ( ) ) ; } return results ; }
Actual content of the topological sort . This is a breadth - first search based approach .