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

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor and Description
Graph()

Method Summary

Methods

Modifier and Type	Method and 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.

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<java.lang.Object,Graph.Node> nodes

Map from node payload to node containing it

Constructor Detail

Graph

public Graph()

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)