Graph.java 文件源码

/** DFS-based topological sort.  A valid sort is the reverse of
 *  the post-order DFA traversal.  Amazingly simple but true.
 *  For sorting, I'm not following convention here since ANTLR
 *  needs the opposite.  Here's what I assume for sorting:
 *
 *    If there exists an edge u -> v then u depends on v and v
 *    must happen before u.
 *
 *  So if this gives nonreversed postorder traversal, I get the order
 *  I want.
 */
public List<T> sort() {
    Set<Node<T>> visited = new OrderedHashSet<Node<T>>();
    ArrayList<T> sorted = new ArrayList<T>();
    while ( visited.size() < nodes.size() ) {
        // pick any unvisited node, n
        Node<T> n = null;
        for (Node<T> tNode : nodes.values()) {
            n = tNode;
            if ( !visited.contains(n) ) break;
        }
        if (n!=null) { // if at least one unvisited
            DFS(n, visited, sorted);
        }
    }
    return sorted;
}