org.jgrapht.alg.shortestpath

Class MartinShortestPath<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.MartinShortestPath<V,E>

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

MultiObjectiveShortestPathAlgorithm<V,E>

public class MartinShortestPath<V,E>
extends Object

Martin's algorithm for the multi-objective shortest paths problem.

Martin's label setting algorithm is a multiple objective extension of Dijkstra's algorithm, where the minimum operator is replaced by a dominance test. It computes a maximal complete set of efficient paths when all the cost values are non-negative.

Note that the multi-objective shortest path problem is a well-known NP-hard problem.

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MultiObjectiveShortestPathAlgorithm

MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E>

Field Summary

Fields

Modifier and Type	Field and Description
protected Graph<V,E>	graph The underlying graph.

Constructor Summary

Constructors

Constructor and Description
MartinShortestPath(Graph<V,E> graph, Function<E,double[]> edgeWeightFunction) Create a new shortest path algorithm

Method Summary

Modifier and Type	Method and Description
protected GraphPath<V,E>	createEmptyPath(V source, V sink) Create an empty path.
MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E>	getPaths(V source) Compute all shortest paths starting from a single source vertex.
List<GraphPath<V,E>>	getPaths(V source, V sink) Get a shortest path from a source vertex to a sink vertex.

Methods inherited from class java.lang.Object

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

Field Detail

graph

protected final Graph<V,E> graph

The underlying graph.

Constructor Detail

MartinShortestPath

public MartinShortestPath(Graph<V,E> graph,
                          Function<E,double[]> edgeWeightFunction)

Create a new shortest path algorithm

Parameters:

graph - the input graph

edgeWeightFunction - the edge weight function

Method Detail

getPaths

public List<GraphPath<V,E>> getPaths(V source,
                                     V sink)

Description copied from interface: MultiObjectiveShortestPathAlgorithm

Get a shortest path from a source vertex to a sink vertex.

Parameters:

source - the source vertex

sink - the target vertex

Returns:

a shortest path or null if no path exists

getPaths

public MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E> getPaths(V source)

Description copied from interface: MultiObjectiveShortestPathAlgorithm

Compute all shortest paths starting from a single source vertex.

Specified by:

getPaths in interface MultiObjectiveShortestPathAlgorithm<V,E>

Parameters:

source - the source vertex

Returns:

the shortest paths

createEmptyPath

protected final GraphPath<V,E> createEmptyPath(V source,
                                               V sink)

Create an empty path. Returns null if the source vertex is different than the target vertex.

Parameters:

source - the source vertex

sink - the sink vertex

Returns:

an empty path or null null if the source vertex is different than the target vertex