< Summary

Class:Itinero.Routing.Flavours.Dijkstra.Bidirectional.BidirectionalDijkstra
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/BidirectionalDijkstra.cs
Covered lines:147
Uncovered lines:7
Coverable lines:154
Total lines:330
Line coverage:95.4% (147 of 154)
Covered branches:71
Total branches:76
Branch coverage:93.4% (71 of 76)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
get_PruneCost()100%2100%
get_Default()100%1100%
RunAsync()100%1100%
ContinueAsync()100%1100%
RunCoreAsync()90.38%5291.13%
TryMeet(...)100%20100%
BuildPath(...)100%2100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/BidirectionalDijkstra.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using System.Threading;
 5using System.Threading.Tasks;
 6using Itinero.Network;
 7using Itinero.Network.Enumerators.Edges;
 8using Itinero.Routes.Paths;
 9using Itinero.Routing.Costs;
 10using Itinero.Routing.DataStructures;
 11using Itinero.Snapping;
 12
 13namespace Itinero.Routing.Flavours.Dijkstra.Bidirectional;
 14
 15/// <summary>
 16/// Edge-based bidirectional Dijkstra. Two single-source edge-based searches grow
 17/// simultaneously — forward from the source, backward from the target. Visits in
 18/// both halves are dedup'd by <c>(edge, vertex)</c>, so different incoming edges at
 19/// a vertex retain distinct best-cost state. They meet wherever a forward-settled
 20/// <c>(E_f, V)</c> shares a vertex V with a backward-settled <c>(E_b, V)</c> and the
 21/// turn at V from E_f to E_b is allowed.
 22///
 23/// When <c>isMainN</c> is supplied each half applies the same per-half access rule
 24/// in its own search direction: reject relaxations where the previous edge is main-N
 25/// and the candidate next edge is not. The two halves combined admit exactly the
 26/// five valid path shapes the unidirectional state-bit Dijkstra admits.
 27/// </summary>
 28internal class BidirectionalDijkstra
 29{
 30    // Not readonly: a search can be handed halves that someone else already expanded. See
 31    // ContinueAsync.
 1532    private SearchHalf _forward = new(isForwardHalf: true);
 1533    private SearchHalf _backward = new(isForwardHalf: false);
 34
 35    // Best meeting found so far.
 36    private double _bestCost;
 37
 38    /// <summary>
 39    /// How far past the best meeting the search keeps relaxing, as a multiple of it. 1.0 is a
 40    /// route; above that it keeps the transitions a caller mapping the region around it needs.
 41    /// </summary>
 1542    private double _pruneFactor = 1.0;
 43
 44    /// The ceiling relaxations are pruned at, and the stopping threshold.
 45    private double PruneCost =>
 349646        _bestCost >= double.MaxValue ? double.MaxValue : _bestCost * _pruneFactor;
 47    private uint _bestForward;
 48    private uint _bestBackward;
 49    // Path returned by the same-edge single-hop fast path; bypasses meeting.
 50    private Path? _singleHopPath;
 51
 52    /// <summary>Fresh instance per call. See <see cref="Dijkstra.Default"/> for rationale.</summary>
 1353    public static BidirectionalDijkstra Default => new();
 54
 55    public async Task<(Path? path, double cost)> RunAsync(
 56        RoutingNetwork network,
 57        SnapPoint source,
 58        SnapPoint target,
 59        ICostFunction costFunction,
 60        Func<VertexId, Task<bool>>? settledCb = null,
 61        CancellationToken cancellationToken = default,
 62        IsMainNFunc? isMainN = null,
 63        HeuristicFunc? potential = null,
 64        bool localAccessRule = false,
 65        double pruneFactor = 1.0,
 66        RelaxedCallback? onForwardRelaxed = null,
 67        RelaxedCallback? onBackwardRelaxed = null)
 8568    {
 8569        _forward = new SearchHalf(isForwardHalf: true);
 8570        _backward = new SearchHalf(isForwardHalf: false);
 71
 8572        return await this.RunCoreAsync(network, source, target, costFunction, seedTerminals: true,
 8573            settledCb, cancellationToken, isMainN, potential, localAccessRule,
 8574            forwardCostFunction: null, backwardCostFunction: null,
 8575            pruneFactor, onForwardRelaxed, onBackwardRelaxed);
 8576    }
 77
 78    /// <summary>
 79    /// Runs to completion from two halves someone else has already expanded.
 80    /// </summary>
 81    /// <remarks>
 82    /// The halves come from snapping, which had to expand outward anyway. The snap points are
 83    /// still needed, not to seed but because the path's end offsets come from them.
 84    /// </remarks>
 85    public async Task<(Path? path, double cost)> ContinueAsync(
 86        RoutingNetwork network,
 87        SearchHalf forward,
 88        SearchHalf backward,
 89        SnapPoint source,
 90        SnapPoint target,
 91        ICostFunction costFunction,
 92        Func<VertexId, Task<bool>>? settledCb = null,
 93        CancellationToken cancellationToken = default,
 94        IsMainNFunc? isMainN = null,
 95        HeuristicFunc? potential = null,
 96        bool localAccessRule = false,
 97        ICostFunction? forwardCostFunction = null,
 98        ICostFunction? backwardCostFunction = null,
 99        double pruneFactor = 1.0,
 100        RelaxedCallback? onForwardRelaxed = null,
 101        RelaxedCallback? onBackwardRelaxed = null)
 32102    {
 32103        _forward = forward;
 32104        _backward = backward;
 105
 32106        return await this.RunCoreAsync(network, source, target, costFunction, seedTerminals: false,
 32107            settledCb, cancellationToken, isMainN, potential, localAccessRule,
 32108            forwardCostFunction, backwardCostFunction,
 32109            pruneFactor, onForwardRelaxed, onBackwardRelaxed);
 32110    }
 111
 112    private async Task<(Path? path, double cost)> RunCoreAsync(
 113        RoutingNetwork network,
 114        SnapPoint source,
 115        SnapPoint target,
 116        ICostFunction costFunction,
 117        bool seedTerminals,
 118        Func<VertexId, Task<bool>>? settledCb,
 119        CancellationToken cancellationToken,
 120        IsMainNFunc? isMainN,
 121        HeuristicFunc? potential,
 122        bool localAccessRule,
 123        ICostFunction? forwardCostFunction = null,
 124        ICostFunction? backwardCostFunction = null,
 125        double pruneFactor = 1.0,
 126        RelaxedCallback? onForwardRelaxed = null,
 127        RelaxedCallback? onBackwardRelaxed = null)
 117128    {
 117129        _pruneFactor = pruneFactor < 1.0 ? 1.0 : pruneFactor;
 130
 131        // Each half can carry its own pocket relabelling, so the two endpoints are independent.
 117132        var forwardCostFn = forwardCostFunction ?? costFunction;
 117133        var backwardCostFn = backwardCostFunction ?? costFunction;
 117134        _bestCost = double.MaxValue;
 117135        _bestForward = uint.MaxValue;
 117136        _bestBackward = uint.MaxValue;
 117137        _singleHopPath = null;
 138
 139        // Single-edge fast path. If both snap points are on the same edge a direct sub-edge
 140        // path may already win; we seed _bestCost so the bidirectional search can still
 141        // improve via a longer path that happens to have lower cost.
 117142        if (network.TrySingleHop(source, target, costFunction, out var singleHopPath, out var singleHopCost))
 49143        {
 49144            _singleHopPath = singleHopPath;
 49145            _bestCost = singleHopCost;
 49146        }
 147
 117148        var enumerator = network.GetEdgeEnumerator();
 149
 150        // Balanced potentials sum to zero at every vertex, which keeps the stopping rule
 151        // below valid: at any meeting vertex the two keys still add up to the true cost.
 117152        HeuristicFunc? forwardPotential = null;
 117153        HeuristicFunc? backwardPotential = null;
 117154        if (potential != null)
 1155        {
 1156            forwardPotential = potential;
 13157            backwardPotential = (longitude, latitude) => -potential(longitude, latitude);
 1158        }
 159
 117160        if (seedTerminals)
 85161        {
 85162            _forward.PushTerminal(enumerator, source, forwardCostFn, forwardPotential);
 85163            _backward.PushTerminal(enumerator, target, backwardCostFn, backwardPotential);
 85164        }
 32165        else if (potential != null)
 1166        {
 167            // An adopted half was keyed with no potential; mixing orderings settles states out
 168            // of order. Re-keying costs O(n log n) in a frontier bounded by the expansion.
 1169            _forward.ReKey(network, forwardPotential);
 1170            _backward.ReKey(network, backwardPotential);
 1171        }
 172
 173        // Built once, not per step: the search runs these millions of times and a fresh closure
 174        // each time would be pure allocation.
 117175        var onForwardReached = new ReachedCallback((edge, fwd, headOrder, pointer, cost, vertex) =>
 3632176            this.TryMeet(network, costFunction, isForwardHalf: true, edge, fwd, headOrder, pointer,
 3632177                cost, vertex, _backward));
 117178        var onBackwardReached = new ReachedCallback((edge, fwd, headOrder, pointer, cost, vertex) =>
 3640179            this.TryMeet(network, costFunction, isForwardHalf: false, edge, fwd, headOrder, pointer,
 3640180                cost, vertex, _forward));
 181
 117182        if (!seedTerminals)
 32183        {
 184            // Adopted halves never asked whether they had already met. For two endpoints in one
 185            // pocket that is the whole answer, and without this the search reports no route.
 98186            foreach (var (vertex, arrivals) in _forward.SettledByVertex)
 1187            {
 2188                if (!_backward.SettledByVertex.ContainsKey(vertex)) continue;
 189
 0190                foreach (var arrival in arrivals)
 0191                {
 0192                    this.TryMeet(network, costFunction, isForwardHalf: true, arrival.Edge,
 0193                        arrival.Forward, arrival.HeadOrder, arrival.Pointer, arrival.Cost, vertex,
 0194                        _backward);
 0195                }
 0196            }
 32197        }
 198
 117199        _forward.OtherEndpointEdge = target.EdgeId;
 117200        _backward.OtherEndpointEdge = source.EdgeId;
 201
 117202        var forwardCost = 0.0;
 117203        var backwardCost = 0.0;
 204
 1231205        while (_forward.Heap.Count > 0 || _backward.Heap.Count > 0)
 1221206        {
 1221207            cancellationToken.ThrowIfCancellationRequested();
 208
 209            // Once both heap mins combined exceed the ceiling, nothing left can come in under it.
 1304210            if (this.PruneCost <= forwardCost + backwardCost) break;
 211
 1138212            if (_forward.Heap.Count > 0)
 1138213            {
 1138214                var popped = await _forward.StepAsync(network, forwardCostFn, isMainN, localAccessRule,
 1138215                    this.PruneCost, settledCb, forwardPotential, onForwardReached, cancellationToken,
 1138216                    onForwardRelaxed);
 2276217                if (popped.HasValue) forwardCost = popped.Value;
 1138218            }
 1138219            if (_backward.Heap.Count > 0)
 1137220            {
 1137221                var popped = await _backward.StepAsync(network, backwardCostFn, isMainN, localAccessRule,
 1137222                    this.PruneCost, settledCb, backwardPotential, onBackwardReached, cancellationToken,
 1137223                    onBackwardRelaxed);
 2274224                if (popped.HasValue) backwardCost = popped.Value;
 1137225            }
 226
 227            // One half has run out of anywhere to go and never got to the other endpoint, so
 228            // it has settled everything reachable from its own and the other endpoint is not
 229            // among it. The two cannot meet.
 1160230            if (_forward.Heap.Count == 0 && !_forward.ReachedOtherEndpoint) break;
 1118231            if (_backward.Heap.Count == 0 && !_backward.ReachedOtherEndpoint) break;
 1114232        }
 233
 134234        if (_bestCost >= double.MaxValue) return (null, double.MaxValue);
 235
 236        // Single-hop won.
 149237        if (_bestForward == uint.MaxValue) return (_singleHopPath, _bestCost);
 238
 51239        var forwardPath = BuildPath(network, _forward.Tree, _bestForward);
 51240        var backwardPath = BuildPath(network, _backward.Tree, _bestBackward);
 51241        forwardPath.Append(backwardPath.InvertDirection());
 242
 51243        forwardPath.Offset1 = forwardPath.First.direction ? source.Offset : (ushort)(ushort.MaxValue - source.Offset);
 51244        forwardPath.Offset2 = forwardPath.Last.direction ? target.Offset : (ushort)(ushort.MaxValue - target.Offset);
 245
 51246        return (forwardPath, _bestCost);
 117247    }
 248
 249    private void TryMeet(
 250        RoutingNetwork network,
 251        ICostFunction costFunction,
 252        bool isForwardHalf,
 253        EdgeId edge,
 254        bool forward,
 255        byte? headOrder,
 256        uint pointer,
 257        double cost,
 258        VertexId vertex,
 259        SearchHalf other)
 7038260    {
 13158261        if (!other.SettledByVertex.TryGetValue(vertex, out var settledList)) return;
 262
 4912263        foreach (var entry in settledList)
 1079264        {
 1464265            if (entry.Edge == edge) continue; // U-turn
 266
 267            // Quick early-out before computing the turn cost.
 694268            var combinedNoTurn = cost + entry.Cost;
 1290269            if (combinedNoTurn >= _bestCost) continue;
 270
 271            // Determine the path-incoming and path-outgoing edge at the meeting vertex:
 272            //   - Path-incoming is the FORWARD half's settled edge at V (forward arrived here via it).
 273            //   - Path-outgoing is the BACKWARD half's settled edge at V (path order continues via it
 274            //     toward target; backward search came from target via that edge).
 275            // When the active half is forward, `edge` is path-incoming and `entry.Edge` is outgoing;
 276            // when active half is backward, the roles swap.
 277            EdgeId pathIncoming;
 278            byte? pathIncomingHeadOrder;
 279            EdgeId pathOutgoing;
 280            bool pathOutgoingForwardFromOther;
 98281            if (isForwardHalf)
 35282            {
 35283                pathIncoming = edge;
 35284                pathIncomingHeadOrder = headOrder;
 35285                pathOutgoing = entry.Edge;
 35286                pathOutgoingForwardFromOther = entry.Forward;
 35287            }
 288            else
 63289            {
 63290                pathIncoming = entry.Edge;
 63291                pathIncomingHeadOrder = entry.HeadOrder;
 63292                pathOutgoing = edge;
 63293                pathOutgoingForwardFromOther = forward;
 63294            }
 295
 98296            var turnCost = SearchHalf.TurnCostBetween(network.GetEdgeEnumerator(), costFunction,
 98297                pathIncoming, pathIncomingHeadOrder,
 98298                pathOutgoing, pathOutgoingForwardFromOther);
 110299            if (turnCost is >= double.MaxValue or < 0) continue;
 300
 86301            var combined = combinedNoTurn + turnCost;
 86302            if (combined >= _bestCost) continue;
 303
 86304            _bestCost = combined;
 86305            if (isForwardHalf)
 34306            {
 34307                _bestForward = pointer;
 34308                _bestBackward = entry.Pointer;
 34309            }
 310            else
 52311            {
 52312                _bestForward = entry.Pointer;
 52313                _bestBackward = pointer;
 52314            }
 86315        }
 7038316    }
 317
 318    private static Path BuildPath(RoutingNetwork network, PathTree tree, uint pointer)
 102319    {
 102320        var path = new Path(network);
 102321        var visit = tree.GetVisit(pointer);
 348322        while (true)
 348323        {
 348324            path.Prepend(visit.edge, visit.forward);
 450325            if (visit.previousPointer == uint.MaxValue) break;
 246326            visit = tree.GetVisit(visit.previousPointer);
 246327        }
 102328        return path;
 102329    }
 330}