org.eigenbase.util
Class Graph<T>

java.lang.Object
  extended by org.eigenbase.util.Graph<T>

public class Graph<T>
extends Object

A Graph is a collection of directed arcs between nodes, and supports various graph-theoretic operations.

Since:
May 6, 2003
Version:
$Id: //open/dev/farrago/src/org/eigenbase/util/Graph.java#11 $
Author:
jhyde

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

noArcs

public static final Graph.Arc[] noArcs

shortestPath

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


arcs

private Set<Graph.Arc<T>> arcs

mutable

private boolean mutable
Constructor Detail

Graph

public Graph()
Method Detail

getPaths

public Iterator<Graph.Arc<T>[]> getPaths(T from,
                                         T to)
Returns an iterator of all paths between two nodes, shortest first.

The current implementation is not optimal.


getShortestPath

public Graph.Arc<T>[] getShortestPath(T from,
                                      T to)
Returns the shortest path between two points, null if there is no path.

Parameters:
from -
to -
Returns:
A list of arcs, null if there is no path.

createArc

public Graph.Arc createArc(T from,
                           T to)

deleteArc

public Graph.Arc deleteArc(T from,
                           T to)
Removes an arc between two vertices.

Returns:
The arc removed, or null

findPaths

private void findPaths(T from,
                       T to,
                       List<Graph.Arc<T>[]> list)

findPathsExcluding

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".


makeImmutable

private void makeImmutable()