Class Graph<T>

java.lang.Object
org.antlr.v4.misc.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 Details

    • nodes

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

    • Graph

      public Graph()
  • Method Details

    • addEdge

      public void addEdge(T a, T b)
    • getNode

      public Graph.Node<T> getNode(T a)
    • 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.
    • DFS

      public void DFS(Graph.Node<T> n, Set<Graph.Node<T>> visited, ArrayList<T> sorted)