Class Graph


  • public class Graph
    extends java.lang.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.
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  Graph.Node  
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.util.Map<java.lang.Object,​Graph.Node> nodes
      Map from node payload to node containing it
    • Constructor Summary

      Constructors 
      Constructor Description
      Graph()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addEdge​(java.lang.Object a, java.lang.Object b)  
      void DFS​(Graph.Node n, java.util.Set<Graph.Node> visited, java.util.ArrayList<java.lang.Object> sorted)  
      protected Graph.Node getNode​(java.lang.Object a)  
      java.util.List<java.lang.Object> sort()
      DFS-based topological sort.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • nodes

        protected java.util.Map<java.lang.Object,​Graph.Node> nodes
        Map from node payload to node containing it
    • Constructor Detail

      • Graph

        public Graph()
    • Method Detail

      • addEdge

        public void addEdge​(java.lang.Object a,
                            java.lang.Object b)
      • getNode

        protected Graph.Node getNode​(java.lang.Object a)
      • sort

        public java.util.List<java.lang.Object> 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.
      • DFS

        public void DFS​(Graph.Node n,
                        java.util.Set<Graph.Node> visited,
                        java.util.ArrayList<java.lang.Object> sorted)