public List < N > sortedNodesByReachability ( ) throws AGraphCircularityException { if ( hasCycles ( ) ) { throw new AGraphCircularityException ( ) ; } final Object [ ] result = new Object [ nodes . length ] ; int nextIdx = 0 ; final Set < N > unprocessed = new HashSet <> ( ) ; for ( Object node : nodes ) { //noinspection unchecked unprocessed . add ( ( N ) node ) ; } //TODO Map<N,Integer> with 'remaining' incoming edges, decrement when a node is 'processed' --> JMH while ( ! unprocessed . isEmpty ( ) ) { final Set < N > nextBatch = ACollectionHelper . filter ( unprocessed , new APredicateNoThrow < N > ( ) { @ Override public boolean apply ( N n ) { for ( E e : incomingEdges ( n ) ) { if ( unprocessed . contains ( e . getFrom ( ) ) ) { return false ; } } return true ; } } ) ; unprocessed . removeAll ( nextBatch ) ; for ( N n : nextBatch ) { result [ nextIdx ] = n ; nextIdx += 1 ; } } return new ArrayIterable <> ( result ) ; }
A directed graph defines a partial order through reachability and this method sorts the graph s nodes based on that partial order .