< 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:174
Uncovered lines:0
Coverable lines:174
Total lines:347
Line coverage:100% (174 of 174)
Covered branches:93
Total branches:102
Branch coverage:91.1% (93 of 102)
Tag:263_26948838820

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
.ctor()100%1100%
Clear()100%1100%
get_Edge()100%1100%
get_Default()100%1100%
RunAsync()95.83%24100%
PushTerminal(...)100%10100%
Step()83.33%42100%
TryMeet(...)100%20100%
TurnCostAtMeeting(...)75%4100%
IsMain(...)100%1100%
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{
 7730    private readonly Half _forward = new();
 7731    private readonly Half _backward = new();
 32
 33    // Best meeting found so far.
 34    private double _bestCost;
 35    private uint _bestForward;
 36    private uint _bestBackward;
 37    // Path returned by the same-edge single-hop fast path; bypasses meeting.
 38    private Path? _singleHopPath;
 39
 40    private sealed class Half
 41    {
 15442        public readonly PathTree Tree = new();
 15443        public readonly BinaryHeap<(uint pointer, EdgeId edge, VertexId vertex)> Heap = new();
 15444        public readonly HashSet<(EdgeId edge, VertexId vertex)> Settled = new();
 45        // Per-vertex list of settled arrivals. Each entry records the incoming edge plus
 46        // the head order at this vertex for that edge — both are needed to query turn
 47        // costs against this label when the other half asks "can I meet you here?".
 15448        public readonly Dictionary<VertexId, List<SettledEntry>> SettledByVertex = new();
 49
 50        public void Clear()
 15451        {
 15452            Tree.Clear();
 15453            Heap.Clear();
 15454            Settled.Clear();
 15455            SettledByVertex.Clear();
 15456        }
 57    }
 58
 46259    private readonly record struct SettledEntry(EdgeId Edge, bool Forward, byte? HeadOrder, uint Pointer, double Cost);
 60
 61    /// <summary>Fresh instance per call. See <see cref="Dijkstra.Default"/> for rationale.</summary>
 7762    public static BidirectionalDijkstra Default => new();
 63
 64    public async Task<(Path? path, double cost)> RunAsync(
 65        RoutingNetwork network,
 66        SnapPoint source,
 67        SnapPoint target,
 68        ICostFunction costFunction,
 69        Func<VertexId, Task<bool>>? settledCb = null,
 70        CancellationToken cancellationToken = default,
 71        IsMainNFunc? isMainN = null)
 7772    {
 7773        _forward.Clear();
 7774        _backward.Clear();
 7775        _bestCost = double.MaxValue;
 7776        _bestForward = uint.MaxValue;
 7777        _bestBackward = uint.MaxValue;
 7778        _singleHopPath = null;
 79
 80        // Single-edge fast path. If both snap points are on the same edge a direct sub-edge
 81        // path may already win; we seed _bestCost so the bidirectional search can still
 82        // improve via a longer path that happens to have lower cost.
 7783        if (network.TrySingleHop(source, target, costFunction, out var singleHopPath, out var singleHopCost))
 4884        {
 4885            _singleHopPath = singleHopPath;
 4886            _bestCost = singleHopCost;
 4887        }
 88
 7789        var enumerator = network.GetEdgeEnumerator();
 90
 7791        PushTerminal(enumerator, source, costFunction, _forward, asOrigin: true);
 7792        PushTerminal(enumerator, target, costFunction, _backward, asOrigin: false);
 93
 7794        var forwardCost = 0.0;
 7795        var backwardCost = 0.0;
 96
 87097        while (_forward.Heap.Count > 0 || _backward.Heap.Count > 0)
 84398        {
 84399            cancellationToken.ThrowIfCancellationRequested();
 100
 101            // Stopping: once both heap mins combined exceed best, no improvement possible.
 893102            if (_bestCost <= forwardCost + backwardCost) break;
 103
 793104            if (_forward.Heap.Count > 0)
 786105            {
 786106                var popped = await this.Step(network, _forward, _backward, isForwardHalf: true, costFunction, isMainN, s
 1572107                if (popped.HasValue) forwardCost = popped.Value;
 786108            }
 793109            if (_backward.Heap.Count > 0)
 791110            {
 791111                var popped = await this.Step(network, _backward, _forward, isForwardHalf: false, costFunction, isMainN, 
 1582112                if (popped.HasValue) backwardCost = popped.Value;
 791113            }
 793114        }
 115
 89116        if (_bestCost >= double.MaxValue) return (null, double.MaxValue);
 117
 118        // Single-hop won.
 113119        if (_bestForward == uint.MaxValue) return (_singleHopPath, _bestCost);
 120
 17121        var forwardPath = BuildPath(network, _forward.Tree, _bestForward);
 17122        var backwardPath = BuildPath(network, _backward.Tree, _bestBackward);
 17123        forwardPath.Append(backwardPath.InvertDirection());
 124
 17125        forwardPath.Offset1 = forwardPath.First.direction ? source.Offset : (ushort)(ushort.MaxValue - source.Offset);
 17126        forwardPath.Offset2 = forwardPath.Last.direction ? target.Offset : (ushort)(ushort.MaxValue - target.Offset);
 127
 17128        return (forwardPath, _bestCost);
 77129    }
 130
 131    private static void PushTerminal(
 132        RoutingNetworkEdgeEnumerator enumerator,
 133        SnapPoint snap,
 134        ICostFunction costFunction,
 135        Half half,
 136        bool asOrigin)
 154137    {
 138        // Mirror of the vertex-based DijkstraAlgorithmExtensions.Push contract:
 139        //   asOrigin=true  → cost computed in the edge's natural direction (tailToHead = true);
 140        //   asOrigin=false → cost computed against the edge (tailToHead = false), so the
 141        //                    backward search reaches "back toward source" with the right weights.
 1078142        foreach (var forward in new[] { true, false })
 308143        {
 308144            if (!enumerator.MoveTo(snap.EdgeId, forward)) continue;
 308145            var (canAccess, _, localAccess, cost, _) = costFunction.Get(enumerator, tailToHead: asOrigin, null);
 342146            if (!canAccess || cost <= 0) continue;
 274147            var offsetCost = forward
 274148                ? cost * (1 - snap.OffsetFactor())
 274149                : cost * snap.OffsetFactor();
 274150            var p = half.Tree.AddVisit(enumerator, leftMain: false, localAccess: localAccess, uint.MaxValue);
 274151            half.Heap.Push((p, enumerator.EdgeId, enumerator.Head), offsetCost);
 274152        }
 154153    }
 154
 155    private async Task<double?> Step(
 156        RoutingNetwork network,
 157        Half active,
 158        Half other,
 159        bool isForwardHalf,
 160        ICostFunction costFunction,
 161        IsMainNFunc? isMainN,
 162        Func<VertexId, Task<bool>>? settledCb,
 163        CancellationToken cancellationToken)
 1577164    {
 165        // Dequeue, skipping already-settled (edge, vertex) labels.
 1577166        var entry = active.Heap.Pop(out var cost);
 3768167        while (active.Settled.Contains((entry.edge, entry.vertex)))
 2191168        {
 2191169            if (active.Heap.Count == 0) return cost;
 2191170            entry = active.Heap.Pop(out cost);
 2191171        }
 1577172        if (!active.Settled.Add((entry.edge, entry.vertex))) return cost;
 173
 1577174        var (vertex, edge, forward, _, localAccess, headOrder, _) = active.Tree.GetVisitWithState(entry.pointer);
 175
 176        // Record in per-vertex settled multimap for meeting checks initiated by the other half.
 1577177        if (!active.SettledByVertex.TryGetValue(vertex, out var list))
 586178        {
 586179            list = new List<SettledEntry>(2);
 586180            active.SettledByVertex[vertex] = list;
 586181        }
 1577182        list.Add(new SettledEntry(edge, forward, headOrder, entry.pointer, cost));
 183
 184        // Settled callback semantics match the unidirectional edge-based: returning true
 185        // means "stop expanding from this vertex" (e.g. outside the max-distance box).
 1577186        if (settledCb != null && await settledCb(vertex)) return cost;
 1577187        if (cancellationToken.IsCancellationRequested) return cost;
 188
 189        // Meeting check against already-settled labels at this vertex in the other half.
 1577190        this.TryMeet(network, costFunction, isForwardHalf, edge, forward, headOrder, entry.pointer, cost, vertex, other)
 191
 192        // Expand neighbours.
 1577193        var probe = network.GetEdgeEnumerator();
 1577194        if (!probe.MoveTo(vertex)) return cost;
 7215195        while (probe.MoveNext())
 5638196        {
 5638197            var neighbourEdge = probe.EdgeId;
 7215198            if (neighbourEdge == edge) continue; // no U-turn
 199
 200            // Cost in this half's direction. Forward uses tailToHead=true, backward uses false.
 201            // PreviousEdgeEnumerable provides turn-cost context from the path so far.
 4061202            var prev = new PreviousEdgeEnumerable(active.Tree, entry.pointer);
 4061203            var (canAccess, _, neighbourLocalAccess, neighbourCost, turnCost) =
 4061204                costFunction.Get(probe, tailToHead: isForwardHalf, prev);
 4061205            if (!canAccess || neighbourCost is >= double.MaxValue or <= 0) continue;
 4087206            if (turnCost is >= double.MaxValue or < 0) continue;
 207
 208            // Per-half access-aware rule: reject prev_main && !curr_main in this half's direction.
 4035209            if (isMainN != null)
 4025210            {
 4025211                var prevMain = IsMain(edge, localAccess, isMainN);
 4025212                var currMain = IsMain(neighbourEdge, neighbourLocalAccess, isMainN);
 4029213                if (prevMain && !currMain) continue;
 4021214            }
 215
 4031216            var totalCost = cost + neighbourCost + turnCost;
 4053217            if (totalCost >= _bestCost) continue;
 218
 4009219            var neighbourPointer = active.Tree.AddVisit(probe, leftMain: false, localAccess: neighbourLocalAccess, entry
 220
 221            // Meeting check against the other half's settled set BEFORE pushing — mirrors the
 222            // existing vertex-based pattern's OnQueued hook.
 4009223            this.TryMeet(network, costFunction, isForwardHalf, neighbourEdge, probe.Forward, probe.HeadOrder,
 4009224                neighbourPointer, totalCost, probe.Head, other);
 225
 4009226            active.Heap.Push((neighbourPointer, neighbourEdge, probe.Head), totalCost);
 4009227        }
 228
 1577229        return cost;
 1577230    }
 231
 232    private void TryMeet(
 233        RoutingNetwork network,
 234        ICostFunction costFunction,
 235        bool isForwardHalf,
 236        EdgeId edge,
 237        bool forward,
 238        byte? headOrder,
 239        uint pointer,
 240        double cost,
 241        VertexId vertex,
 242        Half other)
 5586243    {
 11028244        if (!other.SettledByVertex.TryGetValue(vertex, out var settledList)) return;
 245
 842246        foreach (var entry in settledList)
 205247        {
 236248            if (entry.Edge == edge) continue; // U-turn
 249
 250            // Quick early-out before computing the turn cost.
 174251            var combinedNoTurn = cost + entry.Cost;
 315252            if (combinedNoTurn >= _bestCost) continue;
 253
 254            // Determine the path-incoming and path-outgoing edge at the meeting vertex:
 255            //   - Path-incoming is the FORWARD half's settled edge at V (forward arrived here via it).
 256            //   - Path-outgoing is the BACKWARD half's settled edge at V (path order continues via it
 257            //     toward target; backward search came from target via that edge).
 258            // When the active half is forward, `edge` is path-incoming and `entry.Edge` is outgoing;
 259            // when active half is backward, the roles swap.
 260            EdgeId pathIncoming;
 261            byte? pathIncomingHeadOrder;
 262            EdgeId pathOutgoing;
 263            bool pathOutgoingForwardFromOther;
 33264            if (isForwardHalf)
 5265            {
 5266                pathIncoming = edge;
 5267                pathIncomingHeadOrder = headOrder;
 5268                pathOutgoing = entry.Edge;
 5269                pathOutgoingForwardFromOther = entry.Forward;
 5270            }
 271            else
 28272            {
 28273                pathIncoming = entry.Edge;
 28274                pathIncomingHeadOrder = entry.HeadOrder;
 28275                pathOutgoing = edge;
 28276                pathOutgoingForwardFromOther = forward;
 28277            }
 278
 33279            var turnCost = TurnCostAtMeeting(network, costFunction, vertex,
 33280                pathIncoming, pathIncomingHeadOrder,
 33281                pathOutgoing, pathOutgoingForwardFromOther);
 49282            if (turnCost is >= double.MaxValue or < 0) continue;
 283
 17284            var combined = combinedNoTurn + turnCost;
 17285            if (combined >= _bestCost) continue;
 286
 17287            _bestCost = combined;
 17288            if (isForwardHalf)
 4289            {
 4290                _bestForward = pointer;
 4291                _bestBackward = entry.Pointer;
 4292            }
 293            else
 13294            {
 13295                _bestForward = entry.Pointer;
 13296                _bestBackward = pointer;
 13297            }
 17298        }
 5586299    }
 300
 301    /// <summary>
 302    /// Turn cost at the meeting vertex from the path-incoming edge to the path-outgoing edge.
 303    /// The backward search's enumerator visited <paramref name="pathOutgoing"/> with V as the
 304    /// head; in path order V is the tail of pathOutgoing, so the path-outgoing traversal is
 305    /// the opposite of the backward enumerator's direction.
 306    /// </summary>
 307    private static double TurnCostAtMeeting(
 308        RoutingNetwork network,
 309        ICostFunction costFunction,
 310        VertexId vertex,
 311        EdgeId pathIncoming,
 312        byte? pathIncomingHeadOrder,
 313        EdgeId pathOutgoing,
 314        bool pathOutgoingForwardFromOther)
 33315    {
 33316        var probe = network.GetEdgeEnumerator();
 317        // Position at the outgoing edge in path-outgoing direction (V is tail).
 33318        if (!probe.MoveTo(pathOutgoing, !pathOutgoingForwardFromOther)) return double.MaxValue;
 319
 33320        var previous = pathIncomingHeadOrder.HasValue
 33321            ? new (EdgeId edgeId, byte? turn)[] { (pathIncoming, pathIncomingHeadOrder) }
 33322            : null;
 33323        var (_, _, _, _, turnCost) = costFunction.Get(probe, tailToHead: true, previous);
 33324        return turnCost;
 33325    }
 326
 327    private static bool IsMain(EdgeId edgeId, bool localAccess, IsMainNFunc isMainN)
 8050328    {
 8050329        var verdict = isMainN(edgeId, localAccess);
 330        // Without a leftMain state-bit the bidirectional defaults unknown to "main": the per-half
 331        // rule then doesn't spuriously reject across edges we know nothing about.
 8050332        return verdict ?? true;
 8050333    }
 334
 335    private static Path BuildPath(RoutingNetwork network, PathTree tree, uint pointer)
 34336    {
 34337        var path = new Path(network);
 34338        var visit = tree.GetVisit(pointer);
 79339        while (true)
 79340        {
 79341            path.Prepend(visit.edge, visit.forward);
 113342            if (visit.previousPointer == uint.MaxValue) break;
 45343            visit = tree.GetVisit(visit.previousPointer);
 45344        }
 34345        return path;
 34346    }
 347}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

.ctor()
.ctor()
Clear()
get_Edge()
get_Default()
RunAsync()
PushTerminal(...)
Step()
TryMeet(...)
TurnCostAtMeeting(...)
IsMain(...)
BuildPath(...)