org.antlr.misc
Class Graph

java.lang.Object
  extended by org.antlr.misc.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
static class Graph.Node
           
 
Field Summary
protected  java.util.Map<java.lang.Object,Graph.Node> nodes
          Map from node payload to node containing it
 
Constructor Summary
Graph()
           
 
Method Summary
 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)


Copyright © 2011. All Rights Reserved.