Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

Class BaseBidirectionalShortestPathAlgorithm<V,E>

java.lang.Object

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

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 BaseShortestPathAlgorithm<V,E>

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) static class	BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,E>	Base class of the search frontier used by bidirectional shortest path algorithms.

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

ShortestPathAlgorithm.SingleSourcePaths<V,E>

Field Summary

Fields inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm

graph, GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
protected GraphPath<V,E>	createPath(BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,E> forwardFrontier, BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,E> 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.

Methods inherited from class org.jgrapht.alg.shortestpath.BaseShortestPathAlgorithm

createEmptyPath, getPaths, getPathWeight

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

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(BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,E> forwardFrontier,
                                          BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,E> 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