org.opentripplanner.routing.spt

Class ShortestPathTree

java.lang.Object

org.opentripplanner.routing.spt.ShortestPathTree

public class ShortestPathTree
extends Object

This class keeps track which graph vertices have been visited and their associated states, so that decisions can be made about whether new states should be enqueued for later exploration. It also allows states to be retrieved for a given target vertex. We no longer have different implementations of ShortestPathTree because the label-setting (multi-state) approach used in public transit routing, turn restrictions, bike rental, etc. is a generalization of the basic Dijkstra (single-state) approach. It is much more straightforward to use the more general SPT implementation in all cases. Note that turn restrictions make all searches multi-state; however turn restrictions do not apply when walking. The turn restriction handling is done in the base dominance function implementation, and applies to all subclasses. It essentially splits each vertex into N vertices depending on the incoming edge being taken.

Field Summary

Fields

Modifier and Type	Field and Description
DominanceFunction	dominanceFunction
RoutingRequest	options

Constructor Summary

Constructors

Constructor and Description
ShortestPathTree(RoutingRequest options, DominanceFunction dominanceFunction)

Method Summary

Modifier and Type	Method and Description
boolean	add(State newState) The add method checks a new State to see if it is non-dominated and thus worth visiting later.
void	dump() Print out a summary of the number of states and vertices.
Collection<State>	getAllStates()
RoutingRequest	getOptions()
GraphPath	getPath(Vertex dest, boolean optimize)
List<GraphPath>	getPaths()
List<GraphPath>	getPaths(Vertex dest, boolean optimize)
State	getState(Vertex dest) Returns the 'best' state for the given Vertex, where 'best' depends on the implementation.
List<State>	getStates(Vertex dest) Returns a collection of 'interesting' states for the given Vertex.
int	getVertexCount()
Set<Vertex>	getVertices()
String	toString()
boolean	visit(State state) The visit method should be called upon extracting a State from a priority queue.

Methods inherited from class java.lang.Object

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

Field Detail

options

public final RoutingRequest options

dominanceFunction

public final DominanceFunction dominanceFunction

Constructor Detail

ShortestPathTree

public ShortestPathTree(RoutingRequest options,
                        DominanceFunction dominanceFunction)

Method Detail

getPaths

public List<GraphPath> getPaths(Vertex dest,
                                boolean optimize)

Returns:

a list of GraphPaths, sometimes empty but never null.

getPaths

public List<GraphPath> getPaths()

Returns:

a default set of back-optimized paths to the target vertex.

getPath

public GraphPath getPath(Vertex dest,
                         boolean optimize)

Returns:

a single optimal, optionally back-optimized path to the given vertex.

getOptions

public RoutingRequest getOptions()

Returns:

the routing context for the search that produced this tree

dump

public void dump()

Print out a summary of the number of states and vertices.

getVertices

public Set<Vertex> getVertices()

add

public boolean add(State newState)

The add method checks a new State to see if it is non-dominated and thus worth visiting later. If so, the method returns 'true' indicating that the state is deemed useful and should be enqueued for later exploration. The method will also perform implementation-specific actions that track dominant or optimal states.

Parameters:

newState - the State to add to the SPT, if it is deemed non-dominated

Returns:

a boolean value indicating whether the state was added to the tree and should therefore be enqueued

getState

public State getState(Vertex dest)

Returns the 'best' state for the given Vertex, where 'best' depends on the implementation.

Parameters:

dest - the vertex of interest

Returns:

a 'best' state at that vertex

getStates

public List<State> getStates(Vertex dest)

Returns a collection of 'interesting' states for the given Vertex. Depending on the implementation, this could contain a single optimal state, a set of Pareto-optimal states, or even states that are not known to be optimal but are judged interesting by some other criteria.

Parameters:

dest - the vertex of interest

Returns:

a collection of 'interesting' states at that vertex

getVertexCount

public int getVertexCount()

Returns:

number of vertices referenced in this SPT

visit

public boolean visit(State state)

The visit method should be called upon extracting a State from a priority queue. It checks whether the State is still worth visiting (i.e. whether it has been dominated since it was enqueued) and informs the ShortestPathTree that this State's outgoing edges have been relaxed. A state may remain in the priority queue after being dominated, and such sub-optimal states must be caught as they come out of the queue to avoid unnecessary branching. So this function checks that a state coming out of the queue is still in the Pareto-optimal set for this vertex, which indicates that it has not been ruled out as a state on an optimal path. Many shortest path algorithms will decrease the key of a vertex in the priority queue when it is updated, but we store states in the queue rather than vertices, and states do not get updated or change their weight. TODO consider just removing states from the priority queue. When the Fibonacci heap was replaced with a binary heap, the decrease-key operation was removed for the same reason: both improve theoretical run time complexity, at the cost of high constant factors and more complex code. So there can be dominated (useless) states in the queue. When they come out we want to ignore them rather than spend time branching out from them.

Parameters:

state - - the state about to be visited

Returns:

- whether this state is still considered worth visiting.

getAllStates

public Collection<State> getAllStates()

Returns:

every state in this tree

toString

public String toString()

Overrides:

toString in class Object