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.

  • Field Details

  • 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

      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