net.sf.saffron.util
Class Graph

java.lang.Object
  |
  +--net.sf.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/net/sf/saffron/util/Graph.java#2 $
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

noArcs

public static final Graph.Arc[] noArcs

shortestPath

private HashMap shortestPath
Maps Graph.Arc to Graph.Arc[].


arcs

private HashSet arcs

mutable

private boolean mutable
Constructor Detail

Graph

public Graph()
Method Detail

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.


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.

createArc

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

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


makeImmutable

private void makeImmutable()

SourceForge.net_Logo