Class 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 Detail

      • edgeWeightFunction

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

        private final int objectives
    • 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
      • 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