Class MartinShortestPath<V,E>

java.lang.Object

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

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 BaseMultiObjectiveShortestPathAlgorithm<V,E>

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.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	MartinShortestPath.Label	A node label.
private class	MartinShortestPath.LabelComparator	Lexicographic comparator of two node labels.

Nested classes/interfaces inherited from interface MultiObjectiveShortestPathAlgorithm

MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E>

Field Summary

Fields

Modifier and Type	Field	Description
private final Function<E,double[]>	edgeWeightFunction
private final org.jheaps.Heap<MartinShortestPath<V,E>.Label>	heap
private final Map<V, LinkedList<MartinShortestPath<V,E>.Label>>	nodeLabels
private final int	objectives

Fields inherited from class BaseMultiObjectiveShortestPathAlgorithm

graph, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
private Map<V, List<GraphPath<V,E>>>	buildPaths(V source)	Build the actual paths from the final labels of each node.
private static boolean	dominates(double[] a, double[] b)	Return whether a vector dominates another.
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.
private void	runAlgorithm(V source)	Execute the main algorithm
private static double[]	sum(double[] a, double[] b)	Compute the sum of two vectors
private int	validateEdgeWeightFunction(Function<E,double[]> edgeWeightFunction)	Check the validity of the edge weight function

Methods inherited from class BaseMultiObjectiveShortestPathAlgorithm

createEmptyPath

Methods inherited from class Object

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

Field Details

edgeWeightFunction

private final Function<E,double[]> edgeWeightFunction

objectives

private final int objectives

nodeLabels

private final Map<V, LinkedList<MartinShortestPath<V,E>.Label>> nodeLabels

heap

private final org.jheaps.Heap<MartinShortestPath<V,E>.Label> heap

Constructor Details

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 Details

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>

Overrides:

getPaths in class BaseMultiObjectiveShortestPathAlgorithm<V,E>

Parameters:

source - the source vertex

Returns:

the shortest paths

runAlgorithm

private void runAlgorithm(V source)

Execute the main algorithm

buildPaths

private Map<V, List<GraphPath<V,E>>> buildPaths(V source)

Build the actual paths from the final labels of each node.

Parameters:

source - the source vertex

Returns:

the paths

sum

private static double[] sum(double[] a,
 double[] b)

Compute the sum of two vectors

Parameters:

a - the first vector

b - the second vector

Returns:

the sum

dominates

private static boolean dominates(double[] a,
 double[] b)

Return whether a vector dominates another.

Parameters:

a - the first vector

b - the second vector

Returns:

true if the first vector dominates the second

validateEdgeWeightFunction

private int validateEdgeWeightFunction(Function<E,double[]> edgeWeightFunction)

Check the validity of the edge weight function

Parameters:

edgeWeightFunction - the edge weight function

Returns:

the number of dimensions