Package org.goplanit.algorithms.shortest

Class ShortestBushGeneralised

  • All Implemented Interfaces:
    ShortestBushAllToOne, ShortestBushOneToAll
    public class ShortestBushGeneralised
extends ShortestPathGeneralised
implements ShortestBushOneToAll, ShortestBushAllToOne
    Shortest bush algorithm. Shortest bush algorithm is a one-to-all/all-to-one implementation (depending on configuration) of all (equal cost) implicit shortest bush comprising of all equal cost paths based on the generalised costs on each link segment (edge). It is identical to Dijkstra's shortest path algorithm except that it creates a bush rooted at the start vertex towards the destination vertex, where each node stores all its equal cheapest predecessor nodes from which the bush can be extracted when traversing it in reverse order.

    when configured as one-to-all, the result is to be traversed in reverse direction (destination to origin) to obtian apth information, whereas in all-to-one form the result is traversed from origin to destination (as the search itself is reversed in that case). In its current form, it assumes a macroscopic network and macroscopic link segments to operate on

    Author:
    markr

    • Field Detail

      • nextEdgeSegments

        protected Object[] nextEdgeSegments
        Track incoming edge segment(s) that are shortest for each vertex in this array. In case there is only a single shortest option, the object is an edge segment, otherwise it is a collection of edge segments

      • currEqualShortestCosts

        protected boolean currEqualShortestCosts
        track if most recent tested costs were equal, if so, any processed edge segment is to be added to existing shortest edge segments to complement the bush

    • Constructor Detail

      • ShortestBushGeneralised

        public ShortestBushGeneralised​(double[] edgeSegmentCosts,
                               int numberOfVertices)
        Constructor for an edge cost based algorithm for finding shortest bushes.
        Parameters:
        edgeSegmentCosts - Edge segment costs, both physical and connectoid
        numberOfVertices - Vertices, both nodes and centroids

    • Method Detail

      • executeOneToAll

        public ShortestBushResult executeOneToAll​(DirectedVertex currentOrigin)
        Construct shortest bush result from origin node to all other nodes in the network based on directed LinkSegment edges
        Specified by:
        executeOneToAll in interface ShortestBushOneToAll
        Parameters:
        currentOrigin - origin vertex of source node
        Returns:
        shortest bush result that can be used to extract bushes

      • executeAllToOne

        public ShortestBushResult executeAllToOne​(DirectedVertex currentDestination)
        Construct shortest bush result from all nodes to destination node in the network based on directed LinkSegment edges
        Specified by:
        executeAllToOne in interface ShortestBushAllToOne
        Parameters:
        currentDestination - origin vertex of source node
        Returns:
        shortest bush result that can be used to extract bushes