Package 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.
-
-
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.
-
-
-
Field Detail
-
nodes
protected java.util.Map<java.lang.Object,Graph.Node> nodes
Map from node payload to node containing it
-
-
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)
-
-