Package org.goplanit.assignment.ltm.sltm

Class RootedLabelledBush

  • All Implemented Interfaces:
    Comparable<IdAble>, Bush, IdAble
    Direct Known Subclasses:
    DestinationBush, OriginBush
    public abstract class RootedLabelledBush
extends RootedBush<DirectedVertex,​EdgeSegment>
    A rooted bush is an acyclic directed graph comprising of implicit paths along a network. It has a single root which can be any vertex with only outgoing edge segments. while acyclic its direction can be either be in up or downstream direction compared to the super network it is situated on.

    The vertices in the bush represent link segments in the physical network, whereas each edge represents a turn from one link to another. This way each splitting rate uniquely relates to a single turn and all outgoing edges of a vertex represent all turns of a node's incoming link

    Author:
    markr

    • Constructor Detail

      • RootedLabelledBush

        public RootedLabelledBush​(IdGroupingToken idToken,
                          DirectedVertex rootVertex,
                          boolean inverted,
                          long maxSubGraphEdgeSegments)
        Constructor
        Parameters:
        idToken - the token to base the id generation on
        rootVertex - the root vertex of the bush which can be the end or starting point depending whether or not direction is inverted
        inverted - when true bush ends at root vertex and all other vertices precede it, when false the root is the starting point and all other vertices succeed it
        maxSubGraphEdgeSegments - The maximum number of edge segments the bush can at most register given the parent network it is a subset of

      • RootedLabelledBush

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

    • Method Detail

      • computeMinMaxShortestPaths

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

      • deepClone

        public abstract RootedLabelledBush deepClone()
        An id entity should always support a deep copy, i.e., all "owned" members will be deep copied when a clone of this instance is created via this call. To be used with caution if not called by managed id container related code
        Specified by:
        deepClone in interface Bush
        Specified by:
        deepClone in interface IdAble
        Specified by:
        deepClone in class RootedBush<DirectedVertex,​EdgeSegment>
        Returns:
        deep copy of entity

      • determineIntroduceCycle

        public EdgeSegment determineIntroduceCycle​(EdgeSegment[] alternative)
        Verify if adding the sub-path edge segments 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​(EdgeSegment from,
                                 BushFlowLabel fromLabel,
                                 EdgeSegment to,
                                 BushFlowLabel toLabel,
                                 double addFlowPcuH)
        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, nor labels nor the turn itself is removed
        Parameters:
        from - from segment of the turn
        fromLabel - to use
        to - to segment of the turn
        toLabel - to use
        addFlowPcuH - to add
        Returns:
        new labelled turn sending flow after adding given flow

      • addTurnSendingFlow

        public double addTurnSendingFlow​(EdgeSegment from,
                                 BushFlowLabel fromLabel,
                                 EdgeSegment to,
                                 BushFlowLabel toLabel,
                                 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, the labels are removed
        Parameters:
        from - from segment of the turn
        fromLabel - to use
        to - to segment of the turn
        toLabel - to use
        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 labelled turn sending flow after adding given flow

      • getTurnSendingFlow

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

      • getTurnSendingFlow

        public double getTurnSendingFlow​(EdgeSegment from,
                                 BushFlowLabel fromLabel,
                                 EdgeSegment to,
                                 BushFlowLabel toLabel)
        Collect bush turn sending flow (if any)
        Parameters:
        from - to use
        fromLabel - to filter by
        to - to use
        toLabel - to filter by
        Returns:
        sending flow, zero if unknown

      • getSendingFlowPcuH

        public double getSendingFlowPcuH​(EdgeSegment edgeSegment)
        Collect the sending flow of an edge segment in the bush, if not present, zero flow is returned
        Parameters:
        edgeSegment - to collect sending flow for
        Returns:
        bush sending flow on edge segment

      • getSendingFlowPcuH

        public double getSendingFlowPcuH​(EdgeSegment edgeSegment,
                                 BushFlowLabel compositionLabel)
        Collect the sending flow of an edge segment in the bush but only for the specified label, if not present, zero flow is returned
        Parameters:
        edgeSegment - to collect sending flow for
        compositionLabel - to filter by
        Returns:
        bush sending flow on edge segment

      • containsTurnSendingFlow

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

      • containsTurnSendingFlow

        public boolean containsTurnSendingFlow​(EdgeSegment from,
                                       BushFlowLabel fromLabel,
                                       EdgeSegment to,
                                       BushFlowLabel toLabel)
        Verify if the provided turn has any registered sending flow for the given label combination
        Parameters:
        from - to use
        fromLabel - to use
        to - to use
        toLabel - to use
        Returns:
        true when turn sending flow is present, false otherwise

      • getSplittingRate

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

      • getSplittingRate

        public double getSplittingRate​(EdgeSegment entrySegment,
                               EdgeSegment exitSegment,
                               BushFlowLabel entryExitLabel)
        Collect the bush splitting rate on the given turn for a given label. This might be 0, or 1, but cna also be something in between in case the label splits off in multiple directions
        Parameters:
        entrySegment - to use
        exitSegment - to use
        entryExitLabel - label to be used for both entry and exit of the turn
        Returns:
        found splitting rate, in case the turn is not used, 0 is returned

      • getSplittingRates

        public double[] getSplittingRates​(EdgeSegment entrySegment)
        Collect the bush splitting rates for a given incoming edge segment. If entry segment has no flow, zero splitting rates are returned for all turns
        Parameters:
        entrySegment - to use
        Returns:
        splitting rates in primitive array in order of which one iterates over the outgoing edge segments of the downstream from segment vertex

      • getSplittingRates

        public org.apache.commons.collections4.map.MultiKeyMap<Object,​Double> getSplittingRates​(EdgeSegment entrySegment,
                                                                                              BushFlowLabel entryLabel)
        Collect the bush splitting rates for a given incoming edge segment and entry label. If no flow exits, no splitting rate is provided in the returned map
        Parameters:
        entrySegment - to use
        entryLabel - to use
        Returns:
        splitting rates in multikeymap where the key is the combination of exit segment and exit label and the value is the portion of the entry segment entry label flow directed to it

      • removeTurn

        public void removeTurn​(EdgeSegment fromEdgeSegment,
                       EdgeSegment toEdgeSegment)
        Remove a turn from the bush by removing it from the acyclic graph and removing any data associated with it. Edge segments are also removed in case the no longer carry any flow
        Parameters:
        fromEdgeSegment - of the turn
        toEdgeSegment - of the turn

      • removeEdgeSegment

        public boolean removeEdgeSegment​(EdgeSegment edgeSegment)
        Remove edge segment from bush, if it no longer has flow
        Parameters:
        edgeSegment - to remove
        Returns:
        true when removed, false otherwise

      • containsEdgeSegment

        public boolean containsEdgeSegment​(EdgeSegment edgeSegment)
        Verify if the bush contains the given edge segment
        Parameters:
        edgeSegment - to verify
        Returns:
        true when present, false otherwise

      • containsAnyEdgeSegmentOf

        public boolean containsAnyEdgeSegmentOf​(DirectedEdge edge)
        Verify if the bush contains any edge segment of the edge in either direction
        Parameters:
        edge - to verify
        Returns:
        true when an edge segment of the edge is 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

      • getFlowCompositionLabels

        public TreeSet<BushFlowLabel> getFlowCompositionLabels​(EdgeSegment edgeSegment)
        The labels present for the given segment
        Parameters:
        edgeSegment - to collect composition labels for
        Returns:
        the flow composition labels found

      • getFirstFlowCompositionLabel

        public BushFlowLabel getFirstFlowCompositionLabel​(EdgeSegment edgeSegment)
        The first of the flow composition labels present on the given segment. If no lables are present null is returned
        Parameters:
        edgeSegment - to collect composition labels for
        Returns:
        the flow composition labels found

      • hasFlowCompositionLabel

        public boolean hasFlowCompositionLabel​(EdgeSegment edgeSegment)
        Verify if the edge segment has any flow composition labels registered on it
        Parameters:
        edgeSegment - to verify
        Returns:
        true when present, false otherwise

      • hasFlowCompositionLabel

        public boolean hasFlowCompositionLabel​(EdgeSegment edgeSegment,
                                       BushFlowLabel compositionLabel)
        Verify if the edge segment has the flow composition label provided
        Parameters:
        edgeSegment - to verify
        compositionLabel - to verify
        Returns:
        true when present, false otherwise

      • relabel

        public double relabel​(EdgeSegment fromSegment,
                      BushFlowLabel oldFromLabel,
                      EdgeSegment toSegment,
                      BushFlowLabel oldToLabel,
                      BushFlowLabel newFromToLabel)
        Relabel existing flow from one composition from-to combination to a new from-to label
        Parameters:
        fromSegment - from segment of turn
        oldFromLabel - from composition label to replace
        toSegment - to segment of turn
        oldToLabel - to composition label to replace
        newFromToLabel - label to replace flow with
        Returns:
        the amount of flow that was relabelled

      • relabelFrom

        public double relabelFrom​(EdgeSegment fromSegment,
                          BushFlowLabel oldFromLabel,
                          EdgeSegment toSegment,
                          BushFlowLabel toLabel,
                          BushFlowLabel newFromLabel)
        Relabel the from label of existing flow from one composition from-to combination to a new from-to label
        Parameters:
        fromSegment - from segment of turn
        oldFromLabel - from composition label to replace
        toSegment - to segment of turn
        toLabel - to composition label
        newFromLabel - label to replace flow with
        Returns:
        the amount of flow that was relabelled

      • relabelTo

        public double relabelTo​(EdgeSegment fromSegment,
                        BushFlowLabel fromLabel,
                        EdgeSegment toSegment,
                        BushFlowLabel oldToLabel,
                        BushFlowLabel newToLabel)
        Relabel the to label of existing flow from one composition from-to combination to a new from-to label
        Parameters:
        fromSegment - from segment of turn
        fromLabel - from composition label
        toSegment - to segment of turn
        oldToLabel - to composition label to replace
        newToLabel - label to replace flow with
        Returns:
        the amount of flow that was relabelled

      • syncToNetworkFlows

        public void syncToNetworkFlows​(double[] flowAcceptanceFactors)
        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<DirectedVertex,​EdgeSegment>
        Parameters:
        flowAcceptanceFactors - to use

      • isEmpty

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