Module org.jgrapht.core

Package org.jgrapht.alg.shortestpath

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 org.jgrapht.alg.interfaces.MultiObjectiveShortestPathAlgorithm

MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E>

Field Summary

Fields

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

Fields inherited from class org.jgrapht.alg.shortestpath.BaseMultiObjectiveShortestPathAlgorithm

graph, GRAPH_MUST_CONTAIN_THE_SINK_VERTEX, GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
private java.util.Map<V,java.util.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.
java.util.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(java.util.function.Function<E,double[]> edgeWeightFunction)	Check the validity of the edge weight function

Methods inherited from class org.jgrapht.alg.shortestpath.BaseMultiObjectiveShortestPathAlgorithm

createEmptyPath

Methods inherited from class java.lang.Object

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

Field Detail

edgeWeightFunction

private final java.util.function.Function<E,double[]> edgeWeightFunction

objectives

private final int objectives

nodeLabels

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

heap

private final org.jheaps.Heap<MartinShortestPath.Label> heap

Constructor Detail

MartinShortestPath

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

Create a new shortest path algorithm

Parameters:

graph - the input graph

edgeWeightFunction - the edge weight function

Method Detail

getPaths

public java.util.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 java.util.Map<V,java.util.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(java.util.function.Function<E,double[]> edgeWeightFunction)

Check the validity of the edge weight function

Parameters:

edgeWeightFunction - the edge weight function

Returns:

the number of dimensions