com.luciad.network.algorithm.routing

Graph and Routing EngineClass TLcdPartitionedShortestRouteAlgorithm

java.lang.Object

com.luciad.network.algorithm.routing.TLcdPartitionedShortestRouteAlgorithm

All Implemented Interfaces:

ILcdShortestRouteAlgorithm

public class TLcdPartitionedShortestRouteAlgorithm
extends Object
implements ILcdShortestRouteAlgorithm

Implementation of ILcdShortestRouteAlgorithm, working with partitioned graphs. This algorithm offers a better performance than the basic shortest route algorithm when working with large graphs:

• the number of edges evaluated by the algorithm is strongly reduced when routing over long distances
.
• it is not required to have the full graph loaded into memory, while routing.

The algorithm needs a preprocessing step, done by the 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.

Since:

5.1

See Also:

TLcdShortestRouteDistanceTable, TLcdShortestRouteDistanceTableProvider, TLcdPartitionedShortestRoutePreprocessor

Constructor Summary

Constructors

Constructor and Description
TLcdPartitionedShortestRouteAlgorithm() Constructs a new TLcdPartitionedShortestRouteAlgorithm.
TLcdPartitionedShortestRouteAlgorithm(ILcdShortestRouteDistanceTableProvider aShortestRouteDistanceTableProvider) Constructs a new TLcdPartitionedShortestRouteAlgorithm, that will use the given ILcdShortestRouteDistanceTableProvider.

Method Summary

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.

Methods inherited from class java.lang.Object

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

Constructor Detail

TLcdPartitionedShortestRouteAlgorithm

public TLcdPartitionedShortestRouteAlgorithm()

Constructs a new TLcdPartitionedShortestRouteAlgorithm. An ILcdShortestRouteDistanceTableProvider should be set, before the first routing takes place.

TLcdPartitionedShortestRouteAlgorithm

public TLcdPartitionedShortestRouteAlgorithm(ILcdShortestRouteDistanceTableProvider aShortestRouteDistanceTableProvider)

Constructs a new TLcdPartitionedShortestRouteAlgorithm, that will use the given ILcdShortestRouteDistanceTableProvider.

Parameters:

aShortestRouteDistanceTableProvider - the distance table provider to be used.

Throws:

NullPointerException - if the given distance table provider is null.

Method Detail

setDistanceTableProvider

public void setDistanceTableProvider(ILcdShortestRouteDistanceTableProvider aShortestRouteDistanceTableProvider)

Sets the given distance table provider as the distance table provider to be used by the algorithm.

Parameters:

aShortestRouteDistanceTableProvider - the distance table provider to be used by the algorithm.

getShortestRoute

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)

Description copied from interface: ILcdShortestRouteAlgorithm

Returns an ILcdRoute describing the shortest route between aPrecedingRoute and aSucceedingRoute.

Specified by:

getShortestRoute in interface ILcdShortestRouteAlgorithm

Parameters:

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 edge

aHeuristicDistanceFunction - 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.

Returns:

The shortest route between the two given routes, or null if no such route is found.