- java.lang.Object
-
- org.jgrapht.alg.shortestpath.BaseMultiObjectiveShortestPathAlgorithm<V,E>
-
- org.jgrapht.alg.shortestpath.MartinShortestPath<V,E>
-
- Type Parameters:
V
- the vertex typeE
- 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
All Methods Static Methods Instance Methods Concrete Methods 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 algorithmprivate static double[]
sum(double[] a, double[] b)
Compute the sum of two vectorsprivate 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
-
-
-
-
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
-
-
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 vertexsink
- 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 interfaceMultiObjectiveShortestPathAlgorithm<V,E>
- Overrides:
getPaths
in classBaseMultiObjectiveShortestPathAlgorithm<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 vectorb
- 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 vectorb
- 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
-
-