Package org.goplanit.assignment.ltm.sltm.conjugate

Class ConjugateDestinationBush

  • All Implemented Interfaces:
    Comparable<IdAble>, Bush, IdAble
    public class ConjugateDestinationBush
extends RootedBush<ConjugateDirectedVertex,​ConjugateEdgeSegment>
    A conjugate rooted bush is an acyclic directed graph comprising of implicit paths along a conjugate network, i.e. turn based network (conjugate edge segments). It has a single root based on the original network, i.e. in the ocnjugate network it can represent multiple conjugate nodes since conjugate nodes are edges/edgeSegments on the original network leading to this vertex.

    The conjugate edge segments in the conjugate bush represent pairs of original link segments, i.e. turns in the physical network

    Author:
    markr

    • Constructor Detail

      • ConjugateDestinationBush

        public ConjugateDestinationBush​(IdGroupingToken idToken,
                                CentroidVertex destination,
                                ConjugateConnectoidNode rootVertex,
                                int maxSubGraphTurns)
        Constructor. It is expected that all provided root vertices represent edges in the orignal network leading to a single root.
        Parameters:
        idToken - the token to base the id generation on
        destination - this conjugate destination bush has rooted conjugate vertices for
        rootVertex - this conjugate node represents the root vertex as it is the dummy node from which all initial turns enter/exit the conjugate network from theconjugate destination
        maxSubGraphTurns - The maximum number of conjugate edge segments, i.e. turns, the conjugate bush can at most register given the parent network it is a subset of

      • ConjugateDestinationBush

        public ConjugateDestinationBush​(ConjugateDestinationBush bush,
                                boolean deepCopy)
        Copy constructor
        Parameters:
        bush - to copy
        deepCopy - when true, create a eep copy, shallow copy otherwise

    • Method Detail

      • computeMinMaxShortestPaths

        public MinMaxPathResult computeMinMaxShortestPaths​(double[] conjugatelinkSegmentCosts,
                                                   int totalConjugateVertices)
        Compute the min-max path tree rooted in location depending on underlying dag configuration of derived implementation and given the provided conjugate (network wide) costs. The provided costs are at the conjugate network level so should contain all the conjugate segments active in the bush
        Specified by:
        computeMinMaxShortestPaths in class RootedBush<ConjugateDirectedVertex,​ConjugateEdgeSegment>
        Parameters:
        conjugatelinkSegmentCosts - to use
        totalConjugateVertices - needed to be able to create primitive array recording the (partial) subgraph backward conjugate link segment results (efficiently)
        Returns:
        minMaxPathResult, null if unable to complete

      • getTopologicalIterator

        public Iterator<ConjugateDirectedVertex> getTopologicalIterator​(boolean originDestinationDirection)
        Collect an iterator over topologically sorted bush in origin-destination or destination-origin direction. Depending on the derived bush implementation this might require inverting the iteration direction. Hence it is an abstract method here
        Parameters:
        originDestinationDirection - when true, iterator runs topological order from origin towards destinatino, when false, they other way around
        Returns:
        iterator over topologically ordered bush vertices

      • getShortestSearchType

        public ShortestSearchType getShortestSearchType()
        Description copied from interface: Bush
        determine the search type supported by the bush based on the underlying dag's construction, i.e., a destination-based dag results in All-To-One, whereas an origin based dag results in One-To-All searches.
        Returns:
        shortest search type compatible with this bush implementation

      • determineIntroduceCycle

        public ConjugateEdgeSegment determineIntroduceCycle​(ConjugateEdgeSegment[] alternative)
        Verify if adding the sub-path conjugated edge segments (turns) would introduce a cycle in this bush
        Parameters:
        alternative - to verify
        Returns:
        edge segment that would introduces a cycle, null otherwise

      • addTurnSendingFlow

        public double addTurnSendingFlow​(ConjugateEdgeSegment turn,
                                 double addFlowPcuH)
        Add turn sending flow to the conjugate bush. In case the turn does not yet exist on the bush it is newly registered. If it does exist and there is already flow present, the provided flow is added to it. If by adding the flow (can be negative) the turn no longer has any flow, the turn itself is removed
        Parameters:
        turn - the turn
        addFlowPcuH - to add
        Returns:
        new labelled turn sending flow after adding given flow

      • addTurnSendingFlow

        public double addTurnSendingFlow​(ConjugateEdgeSegment turn,
                                 double addFlowPcuH,
                                 boolean allowTurnRemoval)
        Add turn sending flow to the bush. In case the turn does not yet exist on the bush it is newly registered. If it does exist and there is already flow present, the provided flow is added to it. If by adding the flow (can be negative) the turn no longer has any flow, it is rmeoved if allowed
        Parameters:
        turn - the turn
        addFlowPcuH - to add
        allowTurnRemoval - when true we remove turn when no flow remains after adding (negative) flow, when false, we only change the flow to zero but the bush is not adjusted
        Returns:
        new turn sending flow after adding given flow

      • getTurnSendingFlow

        public double getTurnSendingFlow​(ConjugateEdgeSegment turn)
        Collect bush turn sending flow (if any)
        Parameters:
        turn - to use
        Returns:
        sending flow, zero if unknown

      • getSendingFlowPcuH

        public double getSendingFlowPcuH​(ConjugateNode conjugateNode)
        Collect the sending flow of a conjugate node (original edge segment) in the conjugate bush, if not present, zero flow is returned
        Parameters:
        conjugateNode - to collect sending flow for
        Returns:
        bush sending flow

      • containsTurnSendingFlow

        public boolean containsTurnSendingFlow​(ConjugateEdgeSegment turn)
        Verify if the provided turn has any registered sending flow
        Parameters:
        turn - to use
        Returns:
        true when turn sending flow is present, false otherwise

      • getSplittingRate

        public double getSplittingRate​(ConjugateEdgeSegment turn)
        Collect the bush splitting rate on the given turn
        Parameters:
        turn - to use
        Returns:
        found splitting rate, in case the turn is not used, 0 is returned

      • getSplittingRates

        public double[] getSplittingRates​(ConjugateDirectedVertex conjugateVertex)
        Collect the bush splitting rates for a given conjugate node (original incoming edge segment). If no flow, zero splitting rates are returned
        Parameters:
        conjugateVertex - to use
        Returns:
        splitting rates in primitive array in order of which one iterates over the outgoing (conjugate) edge segments

      • removeTurn

        public void removeTurn​(ConjugateEdgeSegment turn)
        Remove a turn from the conjugate bush
        Parameters:
        turn - of the turn

      • containsTurnSegment

        public boolean containsTurnSegment​(ConjugateEdgeSegment turnSegment)
        Verify if the bush contains the given turn segment
        Parameters:
        turnSegment - to verify
        Returns:
        true when present, false otherwise

      • containsAnyTurnSegmentOf

        public boolean containsAnyTurnSegmentOf​(ConjugateDirectedEdge conjugateEdge)
        Verify if the bush contains any conjugate edge segment (turn) of the conjugate edge in either direction
        Parameters:
        conjugateEdge - to verify
        Returns:
        true when present, false otherwise

      • findBushAlternativeSubpath

        public Pair<DirectedVertex,​Map<DirectedVertex,​EdgeSegment>> findBushAlternativeSubpath​(DirectedVertex referenceVertex,
                                                                                                   short[] alternativeSubpathVertexLabels)
        The alternative subpath is provided through link segment labels of value -1. The point at which they coincide with the bush is indicated with label 1 at the given reference vertex (passed in). Here we do a breadth-first search on the bush in the direction towards its root to find a location the alternative path reconnects to the bush, which, at the latest, should be at the root and at the earliest directly at the next vertex compared to the reference vertex.

        Note that the breadth-first approach is a choice not a necessity but the underlying idea is that a shorter PAS (which is likely to be found) is used by more origins and therefore more useful to explore than a really long PAS. This is preferred - in the original TAPAS - over simply backtracking along either the shortest or longest path of the min-max tree which would also be viable options,a s would a depth-first search.

        Consider implementing various strategies here in order to explore what works best but for now we adopt a breadth-first search

        The returned map contains the next edge segment for each vertex, from the vertex closer to the bush root to the reference vertex where for the reference vertex the edge segment remains null

        Parameters:
        referenceVertex - to start breadth first search from as it is the point of coincidence of the alternative path (via labelled vertices) and bush
        alternativeSubpathVertexLabels - indicating the shortest (network) path at the reference vertex but not part of the bush at that point (different edge segment used)
        Returns:
        vertex at which the two paths coincided again and the map to extract the path from the this vertex to the reference vertex that was found using the breadth-first method

      • computeSubPathSendingFlow

        public double computeSubPathSendingFlow​(DirectedVertex startVertex,
                                        DirectedVertex endVertex,
                                        Map<DirectedVertex,​EdgeSegment> subPathMap)
        Determine the sending flow between origin,destination vertex using the subpath given by the subPathMap, where each vertex provides its exit segment. This is used to traverse the subpath and extract the portion of the sending flow currently known at the bushes startVertex provided to the end vertex
        Parameters:
        startVertex - to use
        endVertex - to use
        subPathMap - to extract path from
        Returns:
        sendingFlowPcuH between start and end vertex following the found sub-path

      • computeSubPathAcceptedFlow

        public double computeSubPathAcceptedFlow​(DirectedVertex startVertex,
                                         DirectedVertex endVertex,
                                         EdgeSegment[] subPathArray,
                                         double[] linkSegmentAcceptanceFactors)
        Determine the accepted flow between origin,destination vertex using the subpath given by the subPathArray in order from start to finish. We utilise the initial sending flow on the first segment as the base flow which is then reduced by the splitting rates and acceptance factor up to and including the final link segment
        Parameters:
        startVertex - to use
        endVertex - to use
        subPathArray - to extract path from
        linkSegmentAcceptanceFactors - the acceptance factor to apply along the path, indexed by link segment id
        Returns:
        acceptedFlowPcuH between start and end vertex following the sub-path

      • determineSubPathSendingFlow

        public double determineSubPathSendingFlow​(EdgeSegment entrySegment,
                                          EdgeSegment[] subPathArray)
        Determine the sending flow between origin,destination vertex using the subpath given by the segment + subPathArray in order from start to finish. We utilise the initial sending flow on the entry segment as the base flow which is then followed along the subpath through the bush splitting rates up to the final link segment
        Parameters:
        entrySegment - to start subpath from
        subPathArray - to append to entry segment to extract path from
        Returns:
        sendingFlowPcuH between start and end vertex following the sub-path

      • determineProportionalFlowCompositionRates

        public TreeMap<BushFlowLabel,​Double> determineProportionalFlowCompositionRates​(EdgeSegment edgeSegment,
                                                                                     Set<BushFlowLabel> pasFlowCompositionLabels)
        Find out the portion of the origin attributed flow on the segment that belongs to each available flow composition label proportional to the total flow across all provided labels on this same segment
        Parameters:
        edgeSegment - to determine the label rates for
        pasFlowCompositionLabels - to determine relative proportions for based on total flow across provided labels on the link segment
        Returns:
        the rates at hand for each found composition label

      • syncToNetworkFlows

        public void syncToNetworkFlows​(double[] originalNetworkFlowAcceptanceFactors)
        Conduct an update of the bush turn flows based on the network flow acceptance factors by conducting a bush DAG loading and updating the turn sending flows from the root, i.e., scale them back with the flow acceptance factor whenever one is encountered.
        Specified by:
        syncToNetworkFlows in class RootedBush<ConjugateDirectedVertex,​ConjugateEdgeSegment>
        Parameters:
        originalNetworkFlowAcceptanceFactors - to use

      • isEmpty

        public boolean isEmpty()
        Verify if empty
        Returns:
        true when empty, false otherwise