

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.eigenbase.util.Graph<T>
public class Graph<T>
A Graph
is a collection of directed arcs between nodes, and
supports various graphtheoretic operations.
Nested Class Summary  

static class 
Graph.Arc<T>
An Arc is a directed link between two nodes. 
static class 
Graph.GraphTest

Field Summary  

private Set<Graph.Arc<T>> 
arcs

private boolean 
mutable

static Graph.Arc[] 
noArcs

private Map<Graph.Arc<T>,Graph.Arc<T>[]> 
shortestPath
Maps Graph.Arc to Graph.Arc []. 
Constructor Summary  

Graph()

Method Summary  

Graph.Arc 
createArc(T from,
T to)

Graph.Arc 
deleteArc(T from,
T to)
Removes an arc between two vertices. 
private void 
findPaths(T from,
T to,
List<Graph.Arc<T>[]> list)

private void 
findPathsExcluding(T from,
T to,
List<Graph.Arc<T>[]> list,
Set<T> excludedNodes,
List<Graph.Arc<T>> prefix)
Finds all paths from "from" to "to" of length 2 or greater, such that the intermediate nodes are not contained in "excludedNodes". 
Iterator<Graph.Arc<T>[]> 
getPaths(T from,
T to)
Returns an iterator of all paths between two nodes, shortest first. 
Graph.Arc<T>[] 
getShortestPath(T from,
T to)
Returns the shortest path between two points, null if there is no path. 
private void 
makeImmutable()

Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

public static final Graph.Arc[] noArcs
private Map<Graph.Arc<T>,Graph.Arc<T>[]> shortestPath
Graph.Arc
to Graph.Arc
[].
private Set<Graph.Arc<T>> arcs
private boolean mutable
Constructor Detail 

public Graph()
Method Detail 

public Iterator<Graph.Arc<T>[]> getPaths(T from, T to)
The current implementation is not optimal.
public Graph.Arc<T>[] getShortestPath(T from, T to)
from
 to

public Graph.Arc createArc(T from, T to)
public Graph.Arc deleteArc(T from, T to)
private void findPaths(T from, T to, List<Graph.Arc<T>[]> list)
private void findPathsExcluding(T from, T to, List<Graph.Arc<T>[]> list, Set<T> excludedNodes, List<Graph.Arc<T>> prefix)
private void makeImmutable()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 