Package org.antlr.v4.misc
Class Graph<T>
- java.lang.Object
-
- org.antlr.v4.misc.Graph<T>
-
public class Graph<T> extends 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<T>
-
Field Summary
Fields Modifier and Type Field Description protected Map<T,Graph.Node<T>>
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(T a, T b)
void
DFS(Graph.Node<T> n, Set<Graph.Node<T>> visited, ArrayList<T> sorted)
Graph.Node<T>
getNode(T a)
List<T>
sort()
DFS-based topological sort.
-
-
-
Field Detail
-
nodes
protected Map<T,Graph.Node<T>> nodes
Map from node payload to node containing it
-
-
Method Detail
-
getNode
public Graph.Node<T> getNode(T a)
-
sort
public 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, Set<Graph.Node<T>> visited, ArrayList<T> sorted)
-
-