程序包 org.antlr.misc

类 Graph<T>


  • public class Graph<T>
    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.
    • 嵌套类概要

      嵌套类 
      修饰符和类型 说明
      static class  Graph.Node<T>  
    • 字段概要

      字段 
      修饰符和类型 字段 说明
      protected java.util.Map<T,​Graph.Node<T>> nodes
      Map from node payload to node containing it
    • 构造器概要

      构造器 
      构造器 说明
      Graph()  
    • 方法概要

      所有方法 实例方法 具体方法 
      修饰符和类型 方法 说明
      void addEdge​(T a, T b)  
      void DFS​(Graph.Node<T> n, java.util.Set<Graph.Node<T>> visited, java.util.ArrayList<T> sorted)  
      protected Graph.Node<T> getNode​(T a)  
      java.util.List<T> sort()
      DFS-based topological sort.
      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 字段详细资料

      • nodes

        protected java.util.Map<T,​Graph.Node<T>> nodes
        Map from node payload to node containing it
    • 构造器详细资料

      • Graph

        public Graph()
    • 方法详细资料

      • addEdge

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

        public java.util.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,
                        java.util.Set<Graph.Node<T>> visited,
                        java.util.ArrayList<T> sorted)