com.bmwcarit.barefoot.topology

Class Dijkstra<E extends AbstractEdge<E>,P extends Point<E>>

java.lang.Object

com.bmwcarit.barefoot.topology.Dijkstra<E,P>

Type Parameters:

E - Implementation of AbstractEdge in a directed Graph.

P - Point type of positions in the network.

All Implemented Interfaces:

Router<E,P>

public class Dijkstra<E extends AbstractEdge<E>,P extends Point<E>>
extends Object
implements Router<E,P>

Dijkstra's algorithm implementation of a Router. The routing functions use the Dijkstra algorithm for finding shortest paths according to a customizable Cost function.

Constructor Summary

Constructors

Constructor and Description
Dijkstra()

Method Summary

Modifier and Type	Method and Description
List<E>	route(P source, P target, Cost<E> cost) Gets path, i.e.
List<E>	route(P source, P target, Cost<E> cost, Cost<E> bound, Double max) Gets path, i.e.
Map<P,List<E>>	route(P source, Set<P> targets, Cost<E> cost) Gets path, i.e.
Map<P,List<E>>	route(P source, Set<P> targets, Cost<E> cost, Cost<E> bound, Double max) Gets path, i.e.
Map<P,Tuple<P,List<E>>>	route(Set<P> sources, Set<P> targets, Cost<E> cost) Gets path, i.e.
Map<P,Tuple<P,List<E>>>	route(Set<P> sources, Set<P> targets, Cost<E> cost, Cost<E> bound, Double max) Gets path, i.e.

Methods inherited from class java.lang.Object

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

Constructor Detail

Dijkstra

public Dijkstra()

Method Detail

route

public List<E> route(P source,
                     P target,
                     Cost<E> cost)

Description copied from interface: Router

Gets path, i.e. a sequence of AbstractEdges, from source Point to target Point with minimum cost according to Cost function.

Specified by:

route in interface Router<E extends AbstractEdge<E>,P extends Point<E>>

Parameters:

source - Source Point in the graph.

target - Target Point in the graph.

cost - Custom Cost function.

Returns:

Path, i.e. a sequence of AbstractEdges, from source Point to target Point with minimum cost according to Cost function. If there is no path from source to target, it returns null.

route

public List<E> route(P source,
                     P target,
                     Cost<E> cost,
                     Cost<E> bound,
                     Double max)

Description copied from interface: Router

Gets path, i.e. a sequence of AbstractEdges, from source Point to target Point with minimum cost according to Cost function. Search depth of routing can be bound by bounding Cost function and a maximum bounding cost value.

Specified by:

route in interface Router<E extends AbstractEdge<E>,P extends Point<E>>

Parameters:

source - Source Point in the graph.

target - Target Point in the graph.

cost - Custom Cost function.

bound - Bounding Cost function.

max - Maximum bounding cost value to bound search depth.

Returns:

Path, i.e. a sequence of AbstractEdges, from source Point to target Point with minimum cost according to Cost function. If there is no path from source to target, it returns null.

route

public Map<P,List<E>> route(P source,
                            Set<P> targets,
                            Cost<E> cost)

Description copied from interface: Router

Gets path, i.e. a sequence of AbstractEdges, from source Point to each target Point with minimum cost according to Cost function.

Specified by:

route in interface Router<E extends AbstractEdge<E>,P extends Point<E>>

Parameters:

source - Source Point in the graph.

targets - Set of target Points in the graph.

cost - Custom Cost function.

Returns:

Map of target Point to path, i.e. a sequence of AbstractEdges, from source Point to target Point with minimum cost according to Cost function. If there is no path from source to target, it maps to null.

route

public Map<P,List<E>> route(P source,
                            Set<P> targets,
                            Cost<E> cost,
                            Cost<E> bound,
                            Double max)

Description copied from interface: Router

Gets path, i.e. a sequence of AbstractEdges, from source Point to each target Point with minimum cost according to Cost function. Search depth of routing can be bound by bounding Cost function and a maximum bounding cost value.

Specified by:

route in interface Router<E extends AbstractEdge<E>,P extends Point<E>>

Parameters:

source - Source Point in the graph.

targets - Set of target Points in the graph.

cost - Custom Cost function.

bound - Bounding Cost function.

max - Maximum bounding cost value to bound search depth.

Returns:

Map of target Point to path, i.e. a sequence of AbstractEdges, from source Point to target Point with minimum cost according to Cost function. If there is no path from source to target, it maps to null.

route

public Map<P,Tuple<P,List<E>>> route(Set<P> sources,
                                     Set<P> targets,
                                     Cost<E> cost)

Description copied from interface: Router

Gets path, i.e. a sequence of AbstractEdges, to each target Point from exactly that source Point that has minimum cost according to Cost function.

Specified by:

route in interface Router<E extends AbstractEdge<E>,P extends Point<E>>

Parameters:

sources - Set of source Points in the graph.

targets - Set of target Points in the graph.

cost - Custom Cost function.

Returns:

Map of target Point to a tuple of path, i.e. a sequence of AbstractEdges, and source Point that have minimum cost according to Cost function for reaching the target. If there is no path to target, it maps to null.

route

public Map<P,Tuple<P,List<E>>> route(Set<P> sources,
                                     Set<P> targets,
                                     Cost<E> cost,
                                     Cost<E> bound,
                                     Double max)

Description copied from interface: Router

Gets path, i.e. a sequence of AbstractEdges, to each target Point from exactly that source Point that has minimum cost according to Cost function. Search depth of routing can be bound by bounding Cost function and a maximum bounding cost value.

Specified by:

route in interface Router<E extends AbstractEdge<E>,P extends Point<E>>

Parameters:

sources - Set of source Points in the graph.

targets - Set of target Points in the graph.

cost - Custom Cost function.

bound - Bounding Cost function.

max - Maximum bounding cost value to bound search depth.

Returns:

Map of target Point to a tuple of path, i.e. a sequence of AbstractEdges, and source Point that have minimum cost according to Cost function for reaching the target. If there is no path to target, it maps to null.