org.opentripplanner.routing.spt

Class DominanceFunction

java.lang.Object

org.opentripplanner.routing.spt.DominanceFunction

All Implemented Interfaces:

Serializable

Direct Known Subclasses:

DominanceFunction.EarliestArrival, DominanceFunction.LeastWalk, DominanceFunction.MinimumWeight, DominanceFunction.Pareto

public abstract class DominanceFunction
extends Object
implements Serializable

A class that determines when one search branch prunes another at the same Vertex, and ultimately which solutions are retained. In the general case, one branch does not necessarily win out over the other, i.e. multiple states can coexist at a single Vertex. Even functions where one state always wins (least weight, fastest travel time) are applied within a multi-state shortest path tree because bike rental, car or bike parking, and turn restrictions all require multiple incomparable states at the same vertex. These need the graph to be "replicated" into separate layers, which is achieved by applying the main dominance logic (lowest weight, lowest cost, Pareto) conditionally, only when the two states have identical bike/car/turn direction status. Dominance functions are serializable so that routing requests may passed between machines in different JVMs, for instance in OTPA Cluster.

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DominanceFunction.EarliestArrival This approach is more coherent in Analyst when we are extracting travel times from the optimal paths.
static class	DominanceFunction.LeastWalk A dominance function that prefers the least walking.
static class	DominanceFunction.MinimumWeight
static class	DominanceFunction.Pareto In this implementation the relation is not symmetric.

Constructor Summary

Constructors

Constructor and Description
DominanceFunction()

Method Summary

Modifier and Type	Method and Description
protected abstract boolean	betterOrEqual(State a, State b) Return true if the first state "defeats" the second state or at least ties with it in terms of suitability.
boolean	betterOrEqualAndComparable(State a, State b) For bike rental, parking, and approaching turn-restricted intersections states are incomparable: they exist on separate planes.
ShortestPathTree	getNewShortestPathTree(RoutingRequest routingRequest) Create a new shortest path tree using this function, considering whether it allows co-dominant States.

Methods inherited from class java.lang.Object

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

Constructor Detail

DominanceFunction

public DominanceFunction()

Method Detail

betterOrEqual

protected abstract boolean betterOrEqual(State a,
                                         State b)

Return true if the first state "defeats" the second state or at least ties with it in terms of suitability. In the case that they are tied, we still want to return true so that an existing state will kick out a new one. Provide this custom logic in subclasses. You would think this could be static, but in Java for some reason calling a static function will call the one on the declared type, not the runtime instance type.

betterOrEqualAndComparable

public boolean betterOrEqualAndComparable(State a,
                                          State b)

For bike rental, parking, and approaching turn-restricted intersections states are incomparable: they exist on separate planes. The core state dominance logic is wrapped in this public function and only applied when the two states have all these variables in common (are on the same plane).

getNewShortestPathTree

public ShortestPathTree getNewShortestPathTree(RoutingRequest routingRequest)

Create a new shortest path tree using this function, considering whether it allows co-dominant States. MultiShortestPathTree is the general case -- it will work with both single- and multi-state functions.