broadwick.graph.algorithms

Class ShortestPath<V extends Vertex,E extends Edge<V>>

java.lang.Object

broadwick.graph.algorithms.ShortestPath<V,E>

Type Parameters:

V - the vertex type.

E - the edge type.

public class ShortestPath<V extends Vertex,E extends Edge<V>>
extends Object

Calculates distances in a specified graph, using Dijkstra's single-source-shortest-path algorithm. All edge weights in the graph must be nonnegative; otherwise an IllegalArgumentException will be thrown.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	ShortestPath.EdgeWeightTransformer Transformer class to transform the edge of a graph to a double (it's weight).

Field Summary

Fields

Modifier and Type	Field and Description
private edu.uci.ics.jung.graph.AbstractTypedGraph<V,E>	jungGraph
private org.apache.commons.collections15.Transformer<E,Number>	weightTransformer

Constructor Summary

Constructors

Constructor and Description
ShortestPath(Graph<V,E> graph) Create a ShortestPath instance.

Method Summary

Modifier and Type	Method and Description
double	calculateDistance(V source, V target) Returns the length of a shortest path from the source to the target vertex, or null if the target is not reachable from the source.
List<E>	getEdgesInPath(V source, V target) Returns a List of the edges on the shortest path from source to target, in order of their occurrence on this path.

Methods inherited from class java.lang.Object

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

Field Detail

jungGraph

private edu.uci.ics.jung.graph.AbstractTypedGraph<V extends Vertex,E extends Edge<V>> jungGraph

weightTransformer

private final org.apache.commons.collections15.Transformer<E extends Edge<V>,Number> weightTransformer

Constructor Detail

ShortestPath

public ShortestPath(Graph<V,E> graph)

Create a ShortestPath instance.

Parameters:

graph - the network/graph on which we will be looking for shortest paths.

Method Detail

calculateDistance

public final double calculateDistance(V source,
                                      V target)

Returns the length of a shortest path from the source to the target vertex, or null if the target is not reachable from the source. If either vertex is not in the graph for which this instance was created, throws IllegalArgumentException.

Parameters:

source - the source

target - the target

Returns:

the distance from source to target

getEdgesInPath

public final List<E> getEdgesInPath(V source,
                                    V target)

Returns a List of the edges on the shortest path from source to target, in order of their occurrence on this path. If either vertex is not in the graph for which this instance was created, throws IllegalArgumentException

Parameters:

source - the vertex from which distances are measured

target - the number of vertics for which to measure distances

Returns:

a list of edges that comprise the shortest path from source to target.