Package org.goplanit.assignment.ltm.sltm

Class PasManager

  • public class PasManager
extends Object
    Container class for tracking all unique PASs indexed by their last (merge) vertex
    Author:
    markr

    • Field Detail

      • DETAILED_LOGGING

        public static final boolean DETAILED_LOGGING
        default for detailed logging flag
        See Also:
        Constant Field Values

    • Constructor Detail

      • PasManager

        public PasManager​(boolean registerByDiverge)
        Constructor
        Parameters:
        registerByDiverge - when true store PASs by (most upstream) diverge vertex, otherwise by their (most downstream) merge vertex

    • Method Detail

      • isCostEffective

        public static boolean isCostEffective​(double alternativeHighCost,
                                      double alternativeLowCost,
                                      double reducedCost)
        Verify if extending a bush with the given PAS given the reduced cost found, it would be effective in improving the bush. This is verified by

        reducedCost = bush_min_path_cost - PAS_min_path_cost, then it is considered effective if (PAS_max_path_cost - PAS_min_path_cost) exceeds mu*bushReducedCost.

        Formulation based on Bar-Gera (2010). IDea is that if the PAS has little difference between high and low cost, we can't shift much flow to improve and it is less attractive. This is ok if the reduced cost, i.e., the maximum improvement given the current state of the network, is also low, but when the best option (which might not exactly follow this PAS) is much better than what this PAS offers, we regard this PAS as not cost-effective and ignore it as a viable option.

        Parameters:
        alternativeHighCost - to use
        alternativeLowCost - to use
        reducedCost - to use
        Returns:
        true when considered effective, false otherwise

      • createSubpathArrayFrom

        public static EdgeSegment[] createSubpathArrayFrom​(DirectedVertex closestToSearchRoot,
                                                   DirectedVertex furthestFromSearchRoot,
                                                   ShortestPathResult searchResultTree,
                                                   int arrayLength,
                                                   boolean truncateArray)
        Extract a subpath in the form of a raw edge segment array in downstream direction based on the shortest path result provided. Since the path tree is in reverse direction, the array is filled from the back, i.e.,if there is spare capacity the front of the array would be empty.
        Parameters:
        closestToSearchRoot - vertex in relation to searchResult tree
        furthestFromSearchRoot - vertex in relation to searchResult tree
        searchResultTree - to extract path from, tree's direction is automatically accounted for
        arrayLength - to use for the to be created array which should be at least as long as the path that is to be extracted
        truncateArray - flag indicating to truncate the subpath array in case the front of the array is not fully used due to the existence of spare capacity
        Returns:
        created array in downstream direction, null if no path could be found

      • createSubpathArrayFrom

        public static EdgeSegment[] createSubpathArrayFrom​(DirectedVertex closestToSearchRoot,
                                                   DirectedVertex furthestFromSearchRoot,
                                                   ShortestSearchType shortestSearchType,
                                                   Map<DirectedVertex,​EdgeSegment> invertedBfSearchResultTree,
                                                   int arrayLength,
                                                   boolean truncateArray)
        Extract a subpath in the form of a raw edge segment array in downstream direction based on the breadth-first (BF) search result provided. This search result is expected to be constructed from the regular shortest path result which direction depends on the search type. the BF search results are expected to be provided in the SAME direction as the search itself (unlike shortestXResults which are in the opposite direction), i.e., if the search was one-to-all (not inverted) then the bf results are also provided in the downstream direction, whereas all-to-one is in the opposite direction.
        Parameters:
        closestToSearchRoot - vertex in relation to searchResult tree
        furthestFromSearchRoot - vertex in relation to searchResult tree
        shortestSearchType - shortestSearchType used to obtain inverted search result, i.e., when on-to-all inverted search result is in downstream direction, when all-to-one in upstream direction
        invertedBfSearchResultTree - to extract path from, tree is in inverted direction compared to regular search tree result, i.e., one-to-all search result is normally in upstream direction, here it is in downstream direction etc.
        arrayLength - to use for the to be created array which should be at least as long as the path that is to be extracted
        truncateArray - flag indicating to truncate the subpath array in case the back of the array is not fully used due to the existence of spare capacity
        Returns:
        created array always in downstream direction, null if no path could be found

      • createAndRegisterNewPas

        public Pas createAndRegisterNewPas​(RootedLabelledBush bush,
                                   EdgeSegment[] s1,
                                   EdgeSegment[] s2)
        create a new PAS for the given cheap and expensive paired alternative segments (subpaths) and register the origin bush on it that was responsible for creating it
        Parameters:
        bush - responsible for triggering the creation of this PAS
        s1 - cheap alternative segment
        s2 - expensive alternative segment
        Returns:
        createdPas

      • createAndRegisterNewPas

        public Pas createAndRegisterNewPas​(RootedLabelledBush bush,
                                   Collection<EdgeSegment> s1,
                                   Collection<EdgeSegment> s2)
        create a new PAS for the given cheap and expensive paired alternative segments (subpaths) and register the origin bush on it that was responsible for creating it
        Parameters:
        bush - responsible for triggering the creation of this PAS
        s1 - cheap alternative segment
        s2 - expensive alternative segment
        Returns:
        createdPas

      • removePas

        public void removePas​(Pas pas,
                      boolean logRemovedPas)
        Remove the PAS from the manager
        Parameters:
        pas - to remove
        logRemovedPas - when true log removed pas, when false do not

      • getPassByReferenceVertex

        public Collection<Pas> getPassByReferenceVertex​(DirectedVertex referenceVertex)
        Collect all PASs that share the same reference vertex. Make sure this vertex is in line with the manager's chosen reference vertex (diverge or merge vertex of the PAS container key)
        Parameters:
        referenceVertex - to collect for
        Returns:
        found PAS matches, null if none

      • findExistingPas

        public Pas findExistingPas​(EdgeSegment[] alternative1,
                           EdgeSegment[] alternative2)
        Find PAS that exactly matches the provides alternative segments. Identical to findExistingPas(EdgeSegment[], EdgeSegment[])
        Parameters:
        alternative1 - alternative segment of PAS
        alternative2 - alternative segment of PAS
        Returns:
        the matching PAS, null otherwise

      • isRegisteredOnAnyPasAtReferenceVertex

        public boolean isRegisteredOnAnyPasAtReferenceVertex​(RootedLabelledBush bush,
                                                     DirectedVertex referenceVertex)
        Verify if any PAS at given reference vertex is used by this origin bush.
        Parameters:
        bush - to test for
        referenceVertex - to test for
        Returns:
        true when PAS is used by origin bush ending at this vertex, false otherwise

      • findFirstSuitableExistingPas

        public Pas findFirstSuitableExistingPas​(RootedLabelledBush bush,
                                        DirectedVertex referenceVertex,
                                        double[] flowAcceptanceFactors,
                                        double reducedCost)
        find the first PAS which has the given merge vertex as end vertex and which if we would extend the bush with its least cost alternative would improve to the point it is considered effective enough compared to the upper bound (reduced cost) improvement provided as well as that the bush has sufficient flow on the high cost alternative of the PAS such that it can improve sufficiently by shifting flow towards the new low cost segment. If this all holds the PAS is selected and returned. We select the first PAS we can find that matches this criteria.
        Parameters:
        bush - to find suitable PAS for
        referenceVertex - to use
        flowAcceptanceFactors - to use (required to assess flow effectiveness in capacitated context)
        reducedCost - the upper bound on the improvement that is known for this merge vertex
        Returns:
        pas found, null if no suitable candidates exist

      • updateCosts

        public void updateCosts​(double[] linkSegmentCosts)
        Update costs on all registered PASs
        Parameters:
        linkSegmentCosts - to use

      • updateCosts

        public void updateCosts​(Collection<Pas> pass,
                        double[] linkSegmentCosts)
        Update cost for a selection of PASs only
        Parameters:
        pass - collection of specific PASs to update
        linkSegmentCosts - to use

      • getPassSortedByReducedCost

        public Collection<Pas> getPassSortedByReducedCost()
        Construct a priority queue based on the PASs reduced cost, i.e., difference between their high and low cost segments in descending order.
        Returns:
        sorted PAS queue in descending order, i.e., highest reduced cost first

      • forEachPas

        public void forEachPas​(Consumer<Pas> pasConsumer)
        Loop over all Pass
        Parameters:
        pasConsumer - to apply

      • getNumberOfPass

        public long getNumberOfPass()
        Number of PASs registered
        Returns:
        number of PASs registered

      • isDetailedLogging

        public boolean isDetailedLogging()

      • setDetailedLogging

        public void setDetailedLogging​(boolean detailedLogging)