Package org.goplanit.assignment.ltm.sltm

Class Bush

  • All Implemented Interfaces:
    Cloneable, Comparable<IdAble>, IdAble
    public class Bush
extends Object
implements IdAble
    A bush is an acyclic directed graph comprising of all implicit paths used by an origin to reach all its destinations. This is achieved by having the total origin demand at its root vertex which is then split across the graph by (bush specific) splitting rates that reside on each edge. The sum of the edge splitting rates originating from a vertex must always sum to 1.

    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

    • Field Detail

      • origin

        protected final OdZone origin
        the origin of the bush

      • originDemandPcuH

        protected double originDemandPcuH
        the total demand of the bush

      • dag

        protected final ACyclicSubGraph dag
        the directed acyclic subgraph representation of the bush, pertaining solely to the topology

      • bushData

        protected final BushTurnData bushData
        track bush specific data

    • Constructor Detail

      • Bush

        public Bush​(IdGroupingToken idToken,
            OdZone origin,
            long numberOfEdgeSegments)
        Constructor
        Parameters:
        idToken - the token to base the id generation on
        origin - of the bush
        numberOfEdgeSegments - The maximum number of edge segments the bush can at most register given the parent network it is a subset of

      • Bush

        public Bush​(Bush bush)
        Copy constructor
        Parameters:
        bush - to copy

    • Method Detail

      • computeMinMaxShortestPaths

        public MinMaxPathResult computeMinMaxShortestPaths​(double[] linkSegmentCosts,
                                                   int totalTransportNetworkVertices)
        Compute the min-max path tree rooted at the origin 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
        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

      • addOriginDemandPcuH

        public void addOriginDemandPcuH​(double originDemandPcuH)
        Add additional demand to the bush's root
        Parameters:
        originDemandPcuH - to add

      • addTurnSendingFlow

        public void addTurnSendingFlow​(EdgeSegment fromEdgeSegment,
                               EdgeSegment toEdgeSegment,
                               double turnSendingflowPcuH)
        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.
        Parameters:
        fromEdgeSegment - from segment of the turn
        toEdgeSegment - to segment of the turn
        turnSendingflowPcuH - to add

      • getTurnSendingFlow

        public double getTurnSendingFlow​(EdgeSegment fromEdgeSegment,
                                 EdgeSegment toEdgeSegment)
        Collect bush turn sending flow (if any)
        Parameters:
        fromEdgeSegment - to use
        toEdgeSegment - to use
        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

      • containsTurnSendingFlow

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

      • getSplittingRate

        public double getSplittingRate​(EdgeSegment entrySegment,
                               EdgeSegment exitSegment)
        Collect the bush splitting rate on the given turn
        Parameters:
        entrySegment - to use
        exitSegment - to use
        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
        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

      • getRootVertexSplittingRates

        public double[] getRootVertexSplittingRates()
        Collect the splitting rates for the root vertex (which do not have an entry segment). Result has an entry for each outgoing segment regardless if it is part of the bush in the order of looping through the outgoing edge segments on the root vertex
        Returns:
        splitting rates for the root vertex exit segments.

      • 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
        Parameters:
        fromEdgeSegment - of the turn
        toEdgeSegment - of the turn

      • 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

      • getDirectedVertexIterator

        public Iterator<DirectedVertex> getDirectedVertexIterator()
        Collect iterator for all unique directed vertices in the bush
        Returns:
        iterator

      • findBushAlternativeSubpath

        public Pair<DirectedVertex,​Map<DirectedVertex,​EdgeSegment>> findBushAlternativeSubpath​(DirectedVertex mergeVertex,
                                                                                                   short[] alternativeSubpathVertexLabels)
        The alternative subpath (not in this bush) is provided as link segment labels of value -1. The end point at which they merge with the bush is indicated with label 1 at the downstream bush vertex (passed in). Here we do a breadth-first search on the bush in the upstream direction to find a location the alternative path diverged from the bush, which, at the latest, should be at the origin and at the earliest directly upstream of the provided 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 outgoing edge segment for each vertex, from the diverge to the merge node where for the merge node the edge segment remains null

        Parameters:
        mergeVertex - to start backward breadth first search from as it is the point of merging between alternative path (via labelled vertices) and bush
        alternativeSubpathVertexLabels - indicating the shortest (network) path merging at the bush vertex but not part of the bush's path to the merge vertex for some part of its path prior to merging
        Returns:
        vertex at which the two paths diverged upstream and the map to extract the path from the diverge vertex to the merge 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

      • computeSubPathSendingFlow

        public double computeSubPathSendingFlow​(DirectedVertex startVertex,
                                        DirectedVertex endVertex,
                                        EdgeSegment[] subPathArray)
        Determine the sending 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 followed along the subpath through the bush splitting rates up to the final link segment
        Parameters:
        startVertex - to use
        endVertex - to use
        subPathArray - to extract path from
        Returns:
        sendingFlowPcuH between start and end vertex following the sub-path

      • getTopologicallySortedVertices

        public Collection<DirectedVertex> getTopologicallySortedVertices()
        Topologically sorted vertices of the bush
        Returns:
        vertices

      • getOrigin

        public OdZone getOrigin()
        Get the origin, the root of this bush
        Returns:
        origin

      • getTravelDemandPcuH

        public double getTravelDemandPcuH()
        Collect the total travel demand for this origin bush
        Returns:
        travel demand

      • getId

        public long getId()
        Collect id of the entity
        Specified by:
        getId in interface IdAble
        Returns:
        id found

      • clone

        public Bush clone()
        Create a shallow copy of this entity
        Specified by:
        clone in interface IdAble
        Overrides:
        clone in class Object
        Returns:
        shallow copy of entity