Class KShortestPaths<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    @Deprecated
    public class KShortestPaths<V,​E>
    extends java.lang.Object
    Deprecated.
    Use KShortestPaths instead.
    The algorithm determines the k shortest simple paths in increasing order of weight. Weights can be negative (but no negative cycle is allowed), and paths can be constrained by a maximum number of edges. Multigraphs are allowed.

    The algorithm is a variant of the Bellman-Ford algorithm but instead of only storing the best path it stores the "k" best paths at each pass, yielding a complexity of O(k*n*(m^2)) where m is the number of edges and n is the number of vertices.

    Since:
    July 5, 2007
    • Constructor Summary

      Constructors 
      Constructor Description
      KShortestPaths​(Graph<V,​E> graph, V startVertex, int k)
      Deprecated.
      Creates an object to compute ranking shortest paths between the start vertex and others vertices.
      KShortestPaths​(Graph<V,​E> graph, V startVertex, int nPaths, int nMaxHops)
      Deprecated.
      Creates an object to calculate ranking shortest paths between the start vertex and others vertices.
      KShortestPaths​(Graph<V,​E> graph, V startVertex, int nPaths, int nMaxHops, PathValidator<V,​E> pathValidator)
      Deprecated.
      Creates an object to calculate ranking shortest paths between the start vertex and others vertices.
      KShortestPaths​(Graph<V,​E> graph, V startVertex, int k, PathValidator<V,​E> pathValidator)
      Deprecated.
      Creates an object to compute ranking shortest paths between the start vertex and others vertices.
    • Field Detail

      • graph

        private Graph<V,​E> graph
        Deprecated.
        Graph on which shortest paths are searched.
      • nMaxHops

        private int nMaxHops
        Deprecated.
      • nPaths

        private int nPaths
        Deprecated.
      • startVertex

        private V startVertex
        Deprecated.
    • Constructor Detail

      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              V startVertex,
                              int k)
        Deprecated.
        Creates an object to compute ranking shortest paths between the start vertex and others vertices.
        Parameters:
        graph - graph on which shortest paths are searched.
        startVertex - start vertex of the calculated paths.
        k - number of paths to be computed.
      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              V startVertex,
                              int k,
                              PathValidator<V,​E> pathValidator)
        Deprecated.
        Creates an object to compute ranking shortest paths between the start vertex and others vertices. Providing non-null path validator may be used to accept/deny paths according to some external logic. These validations will be used in addition to the basic path validations - that the path is from start to target with no loops.
        Parameters:
        graph - graph on which shortest paths are searched.
        startVertex - start vertex of the calculated paths.
        k - number of paths to be computed.
        pathValidator - the path validator to use
      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              V startVertex,
                              int nPaths,
                              int nMaxHops)
        Deprecated.
        Creates an object to calculate ranking shortest paths between the start vertex and others vertices.
        Parameters:
        graph - graph on which shortest paths are searched.
        startVertex - start vertex of the calculated paths.
        nPaths - number of ranking paths between the start vertex and an end vertex.
        nMaxHops - maximum number of edges of the calculated paths.
        Throws:
        java.lang.NullPointerException - if the specified graph or startVertex is null.
        java.lang.IllegalArgumentException - if nPaths is negative or 0.
        java.lang.IllegalArgumentException - if nMaxHops is negative or 0.
      • KShortestPaths

        public KShortestPaths​(Graph<V,​E> graph,
                              V startVertex,
                              int nPaths,
                              int nMaxHops,
                              PathValidator<V,​E> pathValidator)
        Deprecated.
        Creates an object to calculate ranking shortest paths between the start vertex and others vertices. Providing non-null path validator may be used to accept/deny paths according to some external logic. These validations will be used in addition to the basic path validations - that the path is from start to target with no loops.
        Parameters:
        graph - graph on which shortest paths are searched.
        startVertex - start vertex of the calculated paths.
        nPaths - number of ranking paths between the start vertex and an end vertex.
        nMaxHops - maximum number of edges of the calculated paths.
        pathValidator - the path validator to use
        Throws:
        java.lang.NullPointerException - if the specified graph or startVertex is null.
        java.lang.IllegalArgumentException - if nPaths is negative or 0.
        java.lang.IllegalArgumentException - if nMaxHops is negative or 0.
    • Method Detail

      • getPaths

        public java.util.List<GraphPath<V,​E>> getPaths​(V endVertex)
        Deprecated.
        Returns the k shortest simple paths in increasing order of weight.
        Parameters:
        endVertex - target vertex of the calculated paths.
        Returns:
        list of paths, or null if no path exists between the start vertex and the end vertex.
      • assertGetPaths

        private void assertGetPaths​(V endVertex)
        Deprecated.
      • assertKShortestPathsFinder

        private void assertKShortestPathsFinder​(Graph<V,​E> graph,
                                                V startVertex,
                                                int nPaths,
                                                int nMaxHops)
        Deprecated.