org.jgrapht.alg.shortestpath

Class BaseBidirectionalShortestPathAlgorithm<V,E>

java.lang.Object

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

Type Parameters:

V - vertices type

E - edges type

All Implemented Interfaces:

ShortestPathAlgorithm<V,E>

Direct Known Subclasses:

BidirectionalAStarShortestPath, BidirectionalDijkstraShortestPath

public abstract class BaseBidirectionalShortestPathAlgorithm<V,E>
extends Object

Base class for the bidirectional shortest path algorithms. Currently known extensions are BidirectionalDijkstraShortestPath and BidirectionalAStarShortestPath.

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm

ShortestPathAlgorithm.SingleSourcePaths<V,E>

Field Summary

Fields

Modifier and Type	Field and Description
protected Graph<V,E>	graph The underlying graph.
protected static String	GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE Error message for reporting the existence of a negative-weight cycle.
protected static String	GRAPH_MUST_CONTAIN_THE_SINK_VERTEX Error message for reporting that a sink vertex is missing.
protected static String	GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX Error message for reporting that a source vertex is missing.

Constructor Summary

Constructors

Constructor and Description
BaseBidirectionalShortestPathAlgorithm(Graph<V,E> graph) Constructs a new instance of the algorithm for a given graph.

Method Summary

Modifier and Type	Method and Description
protected GraphPath<V,E>	createEmptyPath(V source, V sink) Create an empty path.
protected GraphPath<V,E>	createPath(org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier forwardFrontier, org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier backwardFrontier, double weight, V source, V commonVertex, V sink) Builds shortest path between source and sink based on the information provided by search frontiers and common vertex.
ShortestPathAlgorithm.SingleSourcePaths<V,E>	getPaths(V source) Compute all shortest paths starting from a single source vertex.
double	getPathWeight(V source, V sink) Get the weight of the shortest path from a source vertex to a sink vertex.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm

getPath

Field Detail

GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

Error message for reporting the existence of a negative-weight cycle.

See Also:

Constant Field Values

GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

Error message for reporting that a source vertex is missing.

See Also:

Constant Field Values

GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

Error message for reporting that a sink vertex is missing.

See Also:

Constant Field Values

graph

protected final Graph<V,E> graph

The underlying graph.

Constructor Detail

BaseBidirectionalShortestPathAlgorithm

public BaseBidirectionalShortestPathAlgorithm(Graph<V,E> graph)

Constructs a new instance of the algorithm for a given graph.

Parameters:

graph - the graph

Method Detail

createPath

protected GraphPath<V,E> createPath(org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier forwardFrontier,
                                    org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier backwardFrontier,
                                    double weight,
                                    V source,
                                    V commonVertex,
                                    V sink)

Builds shortest path between source and sink based on the information provided by search frontiers and common vertex.

Parameters:

forwardFrontier - forward direction frontier

backwardFrontier - backward direction frontier

weight - weight of the shortest path

source - path source

commonVertex - path common vertex

sink - path sink

Returns:

shortest path between source and sink

getPaths

public ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)

Compute all shortest paths starting from a single source vertex.

Specified by:

getPaths in interface ShortestPathAlgorithm<V,E>

Parameters:

source - the source vertex

Returns:

the shortest paths

getPathWeight

public double getPathWeight(V source,
                            V sink)

Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.

Specified by:

getPathWeight in interface ShortestPathAlgorithm<V,E>

Parameters:

source - the source vertex

sink - the sink vertex

Returns:

the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists

createEmptyPath

protected final GraphPath<V,E> createEmptyPath(V source,
                                               V sink)

Create an empty path. Returns null if the source vertex is different than the target vertex.

Parameters:

source - the source vertex

sink - the sink vertex

Returns:

an empty path or null null if the source vertex is different than the target vertex