Package org.antlr.misc
Class Graph
java.lang.Object
org.antlr.misc.Graph
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 -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected Map<Object,
Graph.Node> Map from node payload to node containing it -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
void
DFS
(Graph.Node n, Set<Graph.Node> visited, ArrayList<Object> sorted) protected Graph.Node
sort()
DFS-based topological sort.
-
Field Details
-
nodes
Map from node payload to node containing it
-
-
Constructor Details
-
Graph
public Graph()
-
-
Method Details
-
addEdge
-
getNode
-
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
-