Class Graph<T>


  • public class Graph<T>
    extends Object
    A generic graph with edges; Each node as a single Object payload. This is only used to topologically sort a list of file dependencies at the moment.
    • Field Detail

      • nodes

        protected Map<T,​Graph.Node<T>> nodes
        Map from node payload to node containing it
    • Constructor Detail

      • Graph

        public Graph()
    • Method Detail

      • addEdge

        public void addEdge​(T a,
                            T b)
      • sort

        public List<T> sort()
        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.