Package org.goplanit.algorithms.shortest

Class ShortestPathGeneralised

  • Direct Known Subclasses:
    ConjugateShortestPathGeneralised, ShortestBushGeneralised, ShortestPathDijkstra
    public class ShortestPathGeneralised
extends Object
    Dijkstra's shortest path algorithm Dijkstra's shortest path is a one-to-all implementation of the shortest path algorithm based on the generalized costs on each link segment (edge). The costs should be provided upon instantiation and are reused whenever a One-To-All execution conditional on the chosen source node is performed. Note that while it is one-to-all the direction of the search can be inverted such that it effectively becomes an all-to-one search. In its current form, it assumes a macroscopic network and macroscopic link segments to operate on
    Author:
    markr

    • Field Detail

      • currentSource

        protected DirectedVertex currentSource
        Reference to starting point for search for which we collect shortest paths from/to

      • edgeSegmentCosts

        protected final double[] edgeSegmentCosts
        Track the cost for each edge to determine shortest paths

      • numberOfVertices

        protected final int numberOfVertices
        The number of vertices in the network

      • getVertexAtExtreme

        protected Function<EdgeSegment,​DirectedVertex> getVertexAtExtreme
        depending on configuration this function collects vertex at desired edge segment extremity

      • getEdgeSegmentsInDirection

        protected Function<DirectedVertex,​Iterable<? extends EdgeSegment>> getEdgeSegmentsInDirection
        depending on configuration this function collects edge segments in entry or exit direction of vertex

    • Constructor Detail

      • ShortestPathGeneralised

        public ShortestPathGeneralised​(double[] edgeSegmentCosts,
                               int numberOfVertices)
        Constructor for an edge cost based Dijkstra algorithm for finding shortest paths.
        Parameters:
        edgeSegmentCosts - Edge segment costs, both physical and connectoid
        numberOfVertices - Vertices, both nodes and centroids

    • Method Detail

      • getEdgeSegmentCost

        protected Double getEdgeSegmentCost​(EdgeSegment edgeSegment)
        The standard way to collect edge segment costs is by edge segment id from the edge segment cost raw array.
        Parameters:
        edgeSegment - to use
        Returns:
        cost of traversing edge segment

      • initialiseOpenVertices

        protected void initialiseOpenVertices​(PriorityQueue<Pair<DirectedVertex,​Double>> openVertices,
                                      double[] vertexMeasuredCost)
        Initialise the open vertices. Default behaviour is to place the (single) source vertex at zero cost
        Parameters:
        openVertices - to bootstrap with one or more initial vertices
        vertexMeasuredCost - to initialise based on the bootstrapping of the open vertices, otherwise all entries have maximum double values

      • internalExecute

        protected double[] internalExecute​(BiPredicate<Double,​Double> verifyVertex,
                                   Consumer<EdgeSegment> shortestAlternativeEdgeSegmentConsumer)
        Generalised shortest-X search
        Parameters:
        verifyVertex - predicate to test if the new cost to reach vertex is considered shortest compared to existing cost
        shortestAlternativeEdgeSegmentConsumer - process the "shortest" alternative edge segment when verified by the predicate
        Returns:
        found shortest costs for vertices, where the most recent found "shortest" cost is the one available in the array

      • execute

        protected double[] execute​(ShortestSearchType searchType,
                           BiPredicate<Double,​Double> verifyVertex,
                           Consumer<EdgeSegment> shortestIncomingEdgeSegmentConsumer)
        Generalised shortest-X search where the search type determines to which of the other methods to delegate, oneToAll or AllToOne.
        Parameters:
        searchType - to use
        verifyVertex - predicate to test if the new cost to reach vertex is considered shortest compared to existing cost
        shortestIncomingEdgeSegmentConsumer - process the "shortest" incoming edge segment when verified by the predicate
        Returns:
        found shortest costs for vertices, where the most recent found "shortest" cost is the one available in the array

      • executeOneToAll

        protected double[] executeOneToAll​(BiPredicate<Double,​Double> verifyVertex,
                                   Consumer<EdgeSegment> shortestIncomingEdgeSegmentConsumer)
        Generalised one-to-all shortest-X search where the test whether or not an alternative edge segment is shortest is dictated by the provided predicate while the processing of the alternative edge segment when the predicate tests as true is outsourced to the provided consumer. It is however assumed that only a single cost is stored per vertex resulting in the returned vertex measured cost array
        Parameters:
        verifyVertex - predicate to test if the new cost to reach vertex is considered shortest compared to existing cost
        shortestIncomingEdgeSegmentConsumer - process the "shortest" incoming edge segment when verified by the predicate
        Returns:
        found shortest costs for vertices, where the most recent found "shortest" cost is the one available in the array

      • executeAllToOne

        protected double[] executeAllToOne​(BiPredicate<Double,​Double> verifyVertex,
                                   Consumer<EdgeSegment> shortestIncomingEdgeSegmentConsumer)
        Generalised all-to-one shortest-X search where the test whether or not an alternative edge segment is shortest is dictated by the provided predicate while the processing of the alternative edge segment when the predicate tests as true is outsourced to the provided consumer. It is however assumed that only a single cost is stored per vertex resulting in the returned vertex measured cost array
        Parameters:
        verifyVertex - predicate to test if the new cost to reach vertex is considered shortest compared to existing cost
        shortestIncomingEdgeSegmentConsumer - process the "shortest" incoming edge segment when verified by the predicate
        Returns:
        found shortest costs for vertices, where the most recent found "shortest" cost is the one available in the array