org.antlr.misc
Class Graph
java.lang.Object
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.
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 |
nodes
protected java.util.Map<java.lang.Object,Graph.Node> nodes
- Map from node payload to node containing it
Graph
public Graph()
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.