org.eigenbase.util
Class Graph<T>

java.lang.Object
  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()