DataStructures
Class PositiveWeightedGraph

java.lang.Object
  |
  +--DataStructures.WeightedGraph
        |
        +--DataStructures.PositiveWeightedGraph

public class PositiveWeightedGraph

extends WeightedGraph

A class implementing shortest path algorithms for positively weighted directed graphs.

Author:

Peter Williams

Inner classes inherited from class DataStructures.WeightedGraph

WeightedGraph.Arc, WeightedGraph.Node, WeightedGraph.Tip

Fields inherited from class DataStructures.WeightedGraph

nodeMap, version

Constructor Summary

PositiveWeightedGraph()
Constructs an empty positive weighted graph

Method Summary

boolean	pathExists(java.lang.Object origin, java.lang.Object destination) Tests whether a path exists between two given nodes.
java.util.Enumeration	shortestPath(java.lang.Object origin, java.lang.Object destination) Enumerates the nodes in a shortest path between two given nodes.
int	shortestPathLength(java.lang.Object origin, java.lang.Object destination) Returns the length of a shortest path between two given nodes.

Methods inherited from class DataStructures.WeightedGraph

add, arcs, contains, nodes, nrArcs, nrNodes, readGraphTxtFile, writeGraphTxtFile

Methods inherited from class java.lang.Object

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

Constructor Detail

PositiveWeightedGraph

public PositiveWeightedGraph()

Constructs an empty positive weighted graph

Method Detail

pathExists

public boolean pathExists(java.lang.Object origin,
                          java.lang.Object destination)

Tests whether a path exists between two given nodes.

Parameters:

origin - the node at which to begin,

destination - the node at which to end.

Returns:

true if a path exists, false otherwise.

Throws:

java.util.NoSuchElementException - if either node does not exist.

ArithmeticException - if a negatively weighted arc is encountered in the search.

shortestPathLength

public int shortestPathLength(java.lang.Object origin,
                              java.lang.Object destination)

Returns the length of a shortest path between two given nodes.

Parameters:

origin - the node at which to begin,

destination - the node at which to end.

Returns:

the shortest path length.

Throws:

java.util.NoSuchElementException - if either node does not exist, or if there is no path between them.

ArithmeticException - if a negatively weighted arc is encountered in the search.

shortestPath

public java.util.Enumeration shortestPath(java.lang.Object origin,
                                          java.lang.Object destination)

Enumerates the nodes in a shortest path between two given nodes.

Parameters:

origin - the node at which to begin,

destination - the node at which to end.

Returns:

the enumeration.

Throws:

java.util.NoSuchElementException - if either node does not exist, or if there is no path between them.

ArithmeticException - if a negatively weighted arc is encountered in the search.