saffron.util
Class Graph

java.lang.Object
  |
  +--saffron.util.Graph

public class Graph

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/saffron/src/main/saffron/util/Graph.java#1 $

Author:

jhyde

Nested Class Summary

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

Field Summary

private HashSet	arcs
private boolean	mutable
static Graph.Arc[]	noArcs
private HashMap	shortestPath Maps Graph.Arc to Graph.Arc[].

Constructor Summary

Graph()

Method Summary

Graph.Arc	createArc(Object from, Object to)
private void	findPaths(Object from, Object to, List list)
private void	findPathsExcluding(Object from, Object to, List list, HashSet excludedNodes, List prefix) Finds all paths from "from" to "to" of length 2 or greater, such that the intermediate nodes are not contained in "excludedNodes".
Iterator	getPaths(Object from, Object to) Returns an iterator of all paths between two nodes, shortest first.
Graph.Arc[]	getShortestPath(Object from, Object 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

arcs

private HashSet arcs

mutable

private boolean mutable

shortestPath

private HashMap shortestPath

Maps Graph.Arc to Graph.Arc[].

noArcs

public static final Graph.Arc[] noArcs

Constructor Detail

Graph

public Graph()

Method Detail

createArc

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

makeImmutable

private void makeImmutable()

getShortestPath

public Graph.Arc[] getShortestPath(Object from,
                                   Object 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.

getPaths

public Iterator getPaths(Object from,
                         Object to)

Returns an iterator of all paths between two nodes, shortest first.

The current implementation is not optimal.

findPaths

private void findPaths(Object from,
                       Object to,
                       List list)

findPathsExcluding

private void findPathsExcluding(Object from,
                                Object to,
                                List list,
                                HashSet excludedNodes,
                                List prefix)

Finds all paths from "from" to "to" of length 2 or greater, such that the intermediate nodes are not contained in "excludedNodes".