public class TLcdPartitionedShortestRouteAlgorithm extends Object implements ILcdShortestRouteAlgorithm
ILcdShortestRouteAlgorithm
, working with
partitioned graphs. This algorithm offers a better performance than the basic
shortest route algorithm when working with large graphs: TLcdPartionedShortestRoutePreprocessor
. This preprocessor
calculates a set of distance tables, each containing preprocessing
information for one of the partitions. These distance table are stored in an
ILcdShortestRouteDistanceTableProvider
, that keeps them until
they are requested by the routing algorithm.Constructor and Description |
---|
TLcdPartitionedShortestRouteAlgorithm()
Constructs a new
TLcdPartitionedShortestRouteAlgorithm . |
TLcdPartitionedShortestRouteAlgorithm(ILcdShortestRouteDistanceTableProvider aShortestRouteDistanceTableProvider)
Constructs a new
TLcdPartitionedShortestRouteAlgorithm , that
will use the given ILcdShortestRouteDistanceTableProvider . |
Modifier and Type | Method and Description |
---|---|
<N,E> ILcdRoute<N,E> |
getShortestRoute(ILcdGraph<N,E> aGraph,
ILcdRoute<N,E> aPrecedingRoute,
ILcdRoute<N,E> aSucceedingRoute,
ILcdEdgeValueFunction<N,E> aEdgeCostFunction,
ILcdDistanceFunction<N,E> aHeuristicDistanceFunction)
Returns an
ILcdRoute describing the shortest route between
aPrecedingRoute and aSucceedingRoute . |
void |
setDistanceTableProvider(ILcdShortestRouteDistanceTableProvider aShortestRouteDistanceTableProvider)
Sets the given distance table provider as the distance table provider to be
used by the algorithm.
|
public TLcdPartitionedShortestRouteAlgorithm()
TLcdPartitionedShortestRouteAlgorithm
. An
ILcdShortestRouteDistanceTableProvider
should be set, before
the first routing takes place.public TLcdPartitionedShortestRouteAlgorithm(ILcdShortestRouteDistanceTableProvider aShortestRouteDistanceTableProvider)
TLcdPartitionedShortestRouteAlgorithm
, that
will use the given ILcdShortestRouteDistanceTableProvider
.aShortestRouteDistanceTableProvider
- the distance table provider to be used.NullPointerException
- if the given distance table provider is
null
.public void setDistanceTableProvider(ILcdShortestRouteDistanceTableProvider aShortestRouteDistanceTableProvider)
aShortestRouteDistanceTableProvider
- the distance table provider to be used by the algorithm.public <N,E> ILcdRoute<N,E> getShortestRoute(ILcdGraph<N,E> aGraph, ILcdRoute<N,E> aPrecedingRoute, ILcdRoute<N,E> aSucceedingRoute, ILcdEdgeValueFunction<N,E> aEdgeCostFunction, ILcdDistanceFunction<N,E> aHeuristicDistanceFunction)
ILcdShortestRouteAlgorithm
ILcdRoute
describing the shortest route between
aPrecedingRoute
and aSucceedingRoute
.getShortestRoute
in interface ILcdShortestRouteAlgorithm
aGraph
- the graph for which the route is to be calculated.aPrecedingRoute
- the route preceding the shortest route, i.e. where the first
edge of the shortest route should connect to. Only the last
n
edges of this route will have an influence on
the result, where n
is equal to the order of the
given ILcdEdgeValueFunction
.aSucceedingRoute
- the route succeeding the shortest route, i.e. where the last
edge of the shortest route should connect to. Only the first
n
edges of this route will have an influence on
the result, where n
is equal to the order of the
given ILcdEdgeValueFunction
.aEdgeCostFunction
- a function that associates a cost with each edgeaHeuristicDistanceFunction
- a distance function, indicating the estimate cost to travel
from one node to another. This function can be used to
accelerate the search process. Note that this estimate
should always be an underestimate of the real remaining
distance, in order to result in an optimal solution. A
heuristic function, although it can greatly increase the performance
is not required for the algorithm to
work - it may be null
.null
if no such route is found.