org.antlr.misc

Class Graph<T>

java.lang.Object

org.antlr.misc.Graph<T>

public class Graph<T>
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 and Description
static class	Graph.Node<T>

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Map<T,Graph.Node<T>>	nodes Map from node payload to node containing it

Constructor Summary

Constructors

Constructor and Description
Graph()

Method Summary

Modifier and Type	Method and Description
void	addEdge(T a, T b)
void	DFS(Graph.Node<T> n, java.util.Set<Graph.Node<T>> visited, java.util.ArrayList<T> sorted)
protected Graph.Node<T>	getNode(T a)
java.util.List<T>	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<T,Graph.Node<T>> nodes

Map from node payload to node containing it

Constructor Detail

Graph

public Graph()

Method Detail

addEdge

public void addEdge(T a,
                    T b)

getNode

protected Graph.Node<T> getNode(T a)

sort

public java.util.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,
                java.util.Set<Graph.Node<T>> visited,
                java.util.ArrayList<T> sorted)