Package org.jgrapht.alg.shortestpath

Class ListSingleSourcePathsImpl<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.ListSingleSourcePathsImpl<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

java.io.Serializable, ShortestPathAlgorithm.SingleSourcePaths<V,E>

public class ListSingleSourcePathsImpl<V,E>
extends java.lang.Object
implements ShortestPathAlgorithm.SingleSourcePaths<V,E>, java.io.Serializable

An implementation of ShortestPathAlgorithm.SingleSourcePaths which stores one path per vertex.

This is an explicit representation which stores all paths. For a more compact representation see TreeSingleSourcePathsImpl.

Author:

Dimitrios Michail

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
protected Graph<V,E>	graph	The graph
protected java.util.Map<V,GraphPath<V,E>>	paths	One path per vertex
protected V	source	The source vertex of all paths

Constructor Summary

Constructors

Constructor	Description
ListSingleSourcePathsImpl(Graph<V,E> graph, V source, java.util.Map<V,GraphPath<V,E>> paths)	Construct a new instance.

Method Summary

Modifier and Type	Method	Description
Graph<V,E>	getGraph()	Returns the graph over which this set of paths is defined.
GraphPath<V,E>	getPath(V targetVertex)	Return the path from the source vertex to the sink vertex.
V	getSourceVertex()	Returns the single source vertex.
double	getWeight(V targetVertex)	Return the weight of the path from the source vertex to the sink vertex.

Methods inherited from class java.lang.Object

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

Field Detail

graph

protected Graph<V,E> graph

The graph

source

protected V source

The source vertex of all paths

paths

protected java.util.Map<V,GraphPath<V,E>> paths

One path per vertex

Constructor Detail

ListSingleSourcePathsImpl

public ListSingleSourcePathsImpl(Graph<V,E> graph,
                                 V source,
                                 java.util.Map<V,GraphPath<V,E>> paths)

Construct a new instance.

Parameters:

graph - the graph

source - the source vertex

paths - one path per target vertex

Method Detail

getGraph

public Graph<V,E> getGraph()

Returns the graph over which this set of paths is defined.

Specified by:

getGraph in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>

Returns:

the graph

getSourceVertex

public V getSourceVertex()

Returns the single source vertex.

Specified by:

getSourceVertex in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>

Returns:

the single source vertex

getWeight

public double getWeight(V targetVertex)

Return the weight of the path from the source vertex to the sink vertex. If no such path exists, Double.POSITIVE_INFINITY is returned. The weight of the path between a vertex and itself is always zero.

Specified by:

getWeight in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>

Parameters:

targetVertex - the sink vertex

Returns:

the weight of the path between source and sink vertices or Double.POSITIVE_INFINITY in case no such path exists

getPath

public GraphPath<V,E> getPath(V targetVertex)

Return the path from the source vertex to the sink vertex.

Specified by:

getPath in interface ShortestPathAlgorithm.SingleSourcePaths<V,E>

Parameters:

targetVertex - the sink vertex

Returns:

the path from the source vertex to the sink vertex or null if no such path exists