Package org.goplanit.algorithms.shortest

Class ShortestPathAcyclicMinMaxGeneralised

  • All Implemented Interfaces:
    ShortestPathAllToOne, ShortestPathOneToAll
    public class ShortestPathAcyclicMinMaxGeneralised
extends Object
implements ShortestPathOneToAll, ShortestPathAllToOne
    Build a min/max shortest path tree for a given start vertex based on the configuration used. This implementation requires an acyclic network representation such that the vertices can - and already are - topologically sorted. If the provided topological sorted list of vertices is incorrect undefined behaviour will occurs.

    Obtaining a topologically sorted list of vertices for a given acyclic (sub)graph can be generated via the functionality on the AcyclicSubGraph implementation

    Author:
    markr

    • Field Detail

      • 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

      • ShortestPathAcyclicMinMaxGeneralised

        public ShortestPathAcyclicMinMaxGeneralised​(ACyclicSubGraph acyclicSubGraph,
                                            boolean updateTopologicalOrder,
                                            double[] edgeSegmentCosts,
                                            int parentNetworkVertices)
        Constructor

        The edge segment costs should be set for all registered segments on the subgraph while the array itself is expected to match the ids of the edge segments which in turn are based on the number of edge segments on the over-arching network.

        Parameters:
        acyclicSubGraph - the subgraph we are conducting this search on
        updateTopologicalOrder - indicate if current topological order can be used, or it should be updated before use
        edgeSegmentCosts - for all edge segments
        parentNetworkVertices - number of vertices in parent network, required to create raw result array by contiguous vertex id without the need for any mapping

    • Method Detail

      • execute

        public MinMaxPathResultImpl execute​(DirectedVertex startVertex)
        Perform a generalised min-max path search where we construct both the least and most costly path from the start vertex provided to all other vertices in the (sub)graph based on the configuration. Since this is conducted on an acyclic graph all vertices only need to be explored once, which makes it computationally more attractive than the same search on a cyclic graph.
        Parameters:
        startVertex - to conduct search for
        Returns:
        created result

      • executeAllToOne

        public MinMaxPathResult executeAllToOne​(DirectedVertex currentDestination)
        Construct shortest paths from all nodes to a destination node in the network based on directed LinkSegment edges
        Specified by:
        executeAllToOne in interface ShortestPathAllToOne
        Parameters:
        currentDestination - destination vertex to which all paths go
        Returns:
        shortest path result that can be used to extract paths

      • executeOneToAll

        public MinMaxPathResult executeOneToAll​(DirectedVertex currentOrigin)
        Construct shortest paths from source node to all other nodes in the network based on directed LinkSegment edges
        Specified by:
        executeOneToAll in interface ShortestPathOneToAll
        Parameters:
        currentOrigin - start vertex
        Returns:
        shortest path result that can be used to extract paths