< Summary

Class:Itinero.Routing.Flavours.Dijkstra.Dijkstra
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Dijkstra.cs
Covered lines:251
Uncovered lines:28
Coverable lines:279
Total lines:517
Line coverage:89.9% (251 of 279)
Covered branches:132
Total branches:150
Branch coverage:88% (132 of 150)
Tag:263_26948838820

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
RunAsync()0%20%
RunAsync()50%2100%
RunAsync()100%2100%
RunAsync()88.97%13690.37%
IsMain(...)100%2100%
get_Default()100%1100%

File(s)

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

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using System.Runtime.CompilerServices;
 5using System.Threading;
 6using System.Threading.Tasks;
 7using Itinero.Network;
 8using Itinero.Routes.Paths;
 9using Itinero.Routing.DataStructures;
 10using Itinero.Snapping;
 11
 12[assembly: InternalsVisibleTo("Itinero.Tests")]
 13[assembly: InternalsVisibleTo("Itinero.Tests.Benchmarks")]
 14[assembly: InternalsVisibleTo("Itinero.Tests.Functional")]
 15
 16namespace Itinero.Routing.Flavours.Dijkstra;
 17
 18/// <summary>
 19/// An edge-based dijkstra implementation.
 20///
 21/// When <c>isMainN</c> is supplied to <see cref="RunAsync"/>, the search is access-aware:
 22/// each label carries a sticky <c>leftMain</c> bit that flips true on the first
 23/// main → non-main transition, after which the search refuses to relax onto any
 24/// edge classified as main-N. This enforces the "L-edge is fine iff it is the
 25/// only route to destination/origin" rule structurally — main-N may only host
 26/// a contiguous middle segment of the path. See the design note for the five
 27/// valid path shapes this admits.
 28///
 29/// When <c>isMainN</c> is null the search reduces to the classic edge-based
 30/// Dijkstra: <c>leftMain</c> stays false everywhere and no relaxations are
 31/// rejected on access grounds.
 32/// </summary>
 33internal class Dijkstra
 34{
 1157135    private readonly PathTree _tree = new();
 1157136    private readonly HashSet<(EdgeId edgeId, VertexId vertexId, bool leftMain)> _visits = new();
 1157137    private readonly BinaryHeap<(uint pointer, EdgeId edgeId, VertexId vertexId, bool leftMain)> _heap = new();
 38
 39    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network, SnapPoint source,
 40        SnapPoint target,
 41        DijkstraWeightFunc getDijkstraWeight,
 42        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 43        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 44        CancellationToken cancellationToken = default,
 45        IsMainNFunc? isMainN = null)
 046    {
 047        var paths = await this.RunAsync(network, (source, null), new[] { (target, (bool?)null) }, getDijkstraWeight,
 048            settled, queued, cancellationToken, isMainN);
 49
 050        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 051    }
 52
 53    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network,
 54        (SnapPoint sp, bool? direction) source,
 55        (SnapPoint sp, bool? direction) target,
 56        DijkstraWeightFunc getDijkstraWeight,
 57        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 58        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 59        CancellationToken cancellationToken = default,
 60        IsMainNFunc? isMainN = null)
 2261    {
 2262        var paths = await this.RunAsync(network, source, new[] { target }, getDijkstraWeight, settled, queued, cancellat
 63
 2264        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 2265    }
 66
 67    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network, SnapPoint source,
 68        IReadOnlyList<SnapPoint> targets,
 69        DijkstraWeightFunc getDijkstraWeight,
 70        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 71        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 72        CancellationToken cancellationToken = default,
 73        IsMainNFunc? isMainN = null)
 1154274    {
 1154275        var directedTargets = new (SnapPoint sp, bool? direction)[targets.Count];
 40263676        for (var i = 0; i < targets.Count; i++)
 18977677        {
 18977678            directedTargets[i] = (targets[i], null);
 18977679        }
 80
 1154281        return await this.RunAsync(network, (source, null), directedTargets,
 1154282            getDijkstraWeight, settled, queued, cancellationToken, isMainN);
 1154283    }
 84
 85    /// <summary>
 86    ///
 87    /// </summary>
 88    /// <param name="network"></param>
 89    /// <param name="source"></param>
 90    /// <param name="targets"></param>
 91    /// <param name="getDijkstraWeight"></param>
 92    /// <param name="settled">This Callback is called for every edge for which the minimal cost is known. If this callba
 93    /// <param name="queued">This callback is called before an edge is loaded. Should not be used to influence route pla
 94    /// <param name="isMainN">Optional access-aware predicate. When supplied the search tracks a
 95    /// sticky <c>leftMain</c> bit and rejects any relaxation back onto a main-N edge after the
 96    /// first main → non-main transition.</param>
 97    /// <returns></returns>
 98    /// <exception cref="Exception"></exception>
 99    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network,
 100        (SnapPoint sp, bool? direction) source,
 101        IReadOnlyList<(SnapPoint sp, bool? direction)> targets,
 102        DijkstraWeightFunc getDijkstraWeight,
 103        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 104        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 105        CancellationToken cancellationToken = default,
 106        IsMainNFunc? isMainN = null)
 11571107    {
 108        static double GetWorst((uint pointer, double cost)[] targets)
 133845109        {
 133845110            var worst = 0d;
 776532111            for (var i = 0; i < targets.Length; i++)
 383953112            {
 383953113                if (!(targets[i].cost > worst))
 154873114                {
 154873115                    continue;
 116                }
 117
 229080118                worst = targets[i].cost;
 229080119                if (worst >= double.MaxValue)
 129532120                {
 129532121                    break;
 122                }
 99548123            }
 124
 133845125            return worst;
 133845126        }
 127
 11571128        var enumerator = network.GetEdgeEnumerator();
 129
 11571130        _tree.Clear();
 11571131        _visits.Clear();
 11571132        _heap.Clear();
 133
 134        // add sources. leftMain starts false on every source: the search has not yet
 135        // transitioned out of main-N (or has not yet entered, when source is non-main).
 11571136        var sourceForwardVisit = uint.MaxValue;
 11571137        if (source.Forward())
 11571138        {
 139            // add forward.
 11571140            if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0141            {
 0142                throw new Exception($"Edge in source {source} not found!");
 143            }
 144
 11571145            var sourceFwd = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable));
 11571146            if (sourceFwd.cost > 0)
 11571147            {
 148                // can traverse edge in the forward direction.
 11571149                var sourceOffsetCostForward = sourceFwd.cost * (1 - source.sp.OffsetFactor());
 11571150                sourceForwardVisit =
 11571151                    _tree.AddVisit(enumerator, leftMain: false, localAccess: sourceFwd.localAccess, uint.MaxValue);
 11571152                _heap.Push((sourceForwardVisit, enumerator.EdgeId, enumerator.Head, false), sourceOffsetCostForward);
 11571153            }
 11571154        }
 155
 11571156        var sourceBackwardVisit = uint.MaxValue;
 11571157        if (source.Backward())
 11566158        {
 159            // add backward.
 11566160            if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0161            {
 0162                throw new Exception($"Edge in source {source} not found!");
 163            }
 164
 11566165            var sourceBwd = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable));
 11566166            if (sourceBwd.cost > 0)
 8343167            {
 168                // can traverse edge in the backward direction.
 8343169                var sourceOffsetCostBackward = sourceBwd.cost * source.sp.OffsetFactor();
 8343170                sourceBackwardVisit =
 8343171                    _tree.AddVisit(enumerator, leftMain: false, localAccess: sourceBwd.localAccess, uint.MaxValue);
 8343172                _heap.Push((sourceBackwardVisit, enumerator.EdgeId, enumerator.Head, false), sourceOffsetCostBackward);
 8343173            }
 11566174        }
 175
 176        // add targets.
 11571177        var bestTargets = new (uint pointer, double cost)[targets.Count];
 11571178        var targetsPerVertex = new Dictionary<VertexId, List<int>>();
 402764179        for (var t = 0; t < targets.Count; t++)
 189811180        {
 189811181            bestTargets[t] = (uint.MaxValue, double.MaxValue);
 189811182            var target = targets[t];
 183
 189811184            if (target.Forward())
 189808185            {
 186                // add forward.
 189808187                if (!enumerator.MoveTo(target.sp.EdgeId, true))
 0188                {
 0189                    throw new Exception($"Edge in target {target} not found!");
 190                }
 191
 189808192                var targetCostForward = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable))
 189808193                    .cost;
 189808194                if (targetCostForward > 0)
 189808195                {
 189808196                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 110335197                    {
 110335198                        targetsAtVertex = new List<int>();
 110335199                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 110335200                    }
 201
 189808202                    targetsAtVertex.Add(t);
 189808203                }
 189808204            }
 205
 189811206            if (target.Backward())
 189809207            {
 208                // add backward.
 189809209                if (!enumerator.MoveTo(target.sp.EdgeId, false))
 0210                {
 0211                    throw new Exception($"Edge in source {source} not found!");
 212                }
 213
 189809214                var targetCostBackward =
 189809215                    getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost;
 189809216                if (targetCostBackward > 0)
 102031217                {
 102031218                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 68899219                    {
 68899220                        targetsAtVertex = new List<int>();
 68899221                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 68899222                    }
 223
 102031224                    targetsAtVertex.Add(t);
 102031225                }
 189809226            }
 227
 228            // consider paths 'within' a single edge.
 189811229            if (source.sp.EdgeId != target.sp.EdgeId)
 180026230            {
 180026231                continue;
 232            }
 233
 9785234            if (source.sp.Offset == target.sp.Offset)
 5092235            {
 236                // source and target are identical.
 5092237                if (sourceForwardVisit != uint.MaxValue &&
 5092238                    target.Forward())
 5091239                {
 5091240                    bestTargets[t] = (sourceForwardVisit, 0);
 5091241                }
 1242                else if (sourceBackwardVisit != uint.MaxValue &&
 1243                         target.Backward())
 0244                {
 0245                    bestTargets[t] = (sourceForwardVisit, 0);
 0246                }
 5092247            }
 4693248            else if (source.sp.Offset < target.sp.Offset &&
 4693249                     source.Forward() && target.Forward())
 2865250            {
 251                // the source is earlier in the direction of the edge
 252                // and the edge can be traversed in this direction.
 2865253                if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0254                {
 0255                    throw new Exception($"Edge in source {source} not found!");
 256                }
 257
 2865258                var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 2865259                             (target.sp.OffsetFactor() - source.sp.OffsetFactor());
 2865260                bestTargets[t] = (sourceForwardVisit, weight);
 2865261            }
 1828262            else if (source.sp.Offset > target.sp.Offset &&
 1828263                     source.Backward() && target.Backward())
 1825264            {
 265                // the source is earlier against the direction of the edge
 266                // and the edge can be traversed in this direction.
 1825267                if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0268                {
 0269                    throw new Exception($"Edge in source {source} not found!");
 270                }
 271
 1825272                var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 1825273                             (source.sp.OffsetFactor() - target.sp.OffsetFactor());
 1825274                bestTargets[t] = (sourceBackwardVisit, weight);
 1825275            }
 9785276        }
 277
 278        // update worst target cost.
 11571279        var worstTargetCost = GetWorst(bestTargets);
 280
 281        // keep going until heap is empty.
 313389282        while (_heap.Count > 0)
 306306283        {
 306306284            cancellationToken.ThrowIfCancellationRequested();
 285
 286            // dequeue new visit. Dedup includes leftMain because the same (edge,vertex)
 287            // is reachable both with leftMain=false and leftMain=true; the former is
 288            // strictly more permissive but both can occur in the search.
 306306289            var currentEntry = _heap.Pop(out var currentCost);
 394189290            while (_visits.Contains((currentEntry.edgeId, currentEntry.vertexId, currentEntry.leftMain)))
 89858291            {
 292                // visited before, skip.
 89858293                if (_heap.Count == 0)
 1975294                {
 1975295                    currentEntry = (uint.MaxValue, default, default, false);
 1975296                    break;
 297                }
 298
 87883299                currentEntry = _heap.Pop(out currentCost);
 87883300            }
 301
 306306302            var currentPointer = currentEntry.pointer;
 306306303            if (currentPointer == uint.MaxValue)
 1975304            {
 1975305                break;
 306            }
 307
 308            // only call GetVisitWithState after the visited check passes.
 304331309            var currentVisit = _tree.GetVisitWithState(currentPointer);
 310
 311            // log visit.
 304331312            if (currentVisit.previousPointer != uint.MaxValue)
 284971313            {
 284971314                _visits.Add((currentEntry.edgeId, currentEntry.vertexId, currentEntry.leftMain));
 284971315            }
 316
 304331317            if (settled != null && await settled((currentEntry.edgeId, currentEntry.vertexId)))
 51273318            {
 319                // the best cost to this edge has already been found; current visit can not improve this anymore so we c
 51273320                continue;
 321            }
 322
 323            // check if the search needs to stop.
 253058324            if (currentCost > worstTargetCost)
 2513325            {
 326                // impossible to improve on cost to any target.
 2513327                break;
 328            }
 329
 330            // check neighbours.
 250545331            if (!enumerator.MoveTo(currentVisit.vertex))
 0332            {
 333                // no edges, move on!
 0334                continue;
 335            }
 336
 337            // check if this is a target.
 250545338            if (!targetsPerVertex.TryGetValue(currentVisit.vertex, out var targetsAtVertex))
 111428339            {
 111428340                targetsAtVertex = null;
 111428341            }
 342
 1045507343            while (enumerator.MoveNext())
 794962344            {
 345                // filter out if u-turns or visits on the same edge.
 794962346                var neighbourEdge = enumerator.EdgeId;
 794962347                if (neighbourEdge == currentVisit.edge)
 250545348                {
 250545349                    continue;
 350                }
 351
 352                // gets the cost of the current edge.
 544417353                var (neighbourCost, turnCost, neighbourLocalAccess) =
 544417354                    getDijkstraWeight(enumerator, new PreviousEdgeEnumerable(_tree, currentPointer));
 544417355                if (neighbourCost is >= double.MaxValue or <= 0)
 154190356                {
 154190357                    continue;
 358                }
 359
 390227360                if (turnCost is >= double.MaxValue or < 0)
 11361                {
 11362                    continue;
 363                }
 364
 365                // Access-aware state-bit logic. When isMainN is null this block is a no-op:
 366                // newLeftMain stays false and no relaxation is rejected.
 390216367                var newLeftMain = false;
 390216368                if (isMainN != null)
 390195369                {
 390195370                    var prevMain = IsMain(currentVisit.edge, currentVisit.localAccess, currentVisit.leftMain, isMainN);
 390195371                    var neighbourMain = IsMain(neighbourEdge, neighbourLocalAccess, currentVisit.leftMain, isMainN);
 372
 373                    // Rule: once leftMain is true we may not relax onto a main-N edge again.
 374                    // That would mean re-entering main-N after having departed, i.e. an L-edge
 375                    // (or non-main-N pocket) used as through-traffic between two main-N segments.
 390196376                    if (currentVisit.leftMain && neighbourMain) continue;
 377
 378                    // newLeftMain is sticky and flips on the first main-N → non-main-N transition.
 390194379                    newLeftMain = currentVisit.leftMain || (prevMain && !neighbourMain);
 390194380                }
 381
 382                // if the vertex has targets, check if this edge is a match.
 390215383                var neighbourPointer = uint.MaxValue;
 390215384                if (targetsAtVertex != null)
 221010385                {
 386                    // only consider targets when found for the 'from' vertex.
 387                    // and when this in not a u-turn.
 1638960388                    foreach (var t in targetsAtVertex)
 487965389                    {
 487965390                        var target = targets[t];
 487965391                        if (target.sp.EdgeId != neighbourEdge)
 297180392                        {
 297180393                            continue;
 394                        }
 395
 396                        // check directions.
 190785397                        if (enumerator.Forward && !target.Forward())
 0398                        {
 0399                            continue;
 400                        }
 401
 190785402                        if (!enumerator.Forward && !target.Backward())
 0403                        {
 0404                            continue;
 405                        }
 406
 407                        // there is a target on this edge, calculate the cost.
 408                        // calculate the cost from the 'from' vertex to the target.
 190785409                        var targetCost = enumerator.Forward
 190785410                            ? neighbourCost * target.sp.OffsetFactor()
 190785411                            : neighbourCost * (1 - target.sp.OffsetFactor());
 412                        // this is the case where the target is on this edge
 413                        // and there is a path to 'from' before.
 190785414                        targetCost += currentCost;
 415
 190785416                        targetCost += turnCost;
 417
 418                        // if this is an improvement, use it!
 190785419                        var targetBestCost = bestTargets[t].cost;
 190785420                        if (!(targetCost < targetBestCost))
 68511421                        {
 68511422                            continue;
 423                        }
 424
 425                        // this is an improvement.
 122274426                        neighbourPointer = _tree.AddVisit(enumerator, newLeftMain, neighbourLocalAccess, currentPointer)
 122274427                        bestTargets[t] = (neighbourPointer, targetCost);
 428
 429                        // update worst.
 122274430                        worstTargetCost = GetWorst(bestTargets);
 122274431                    }
 221010432                }
 433
 390215434                if (queued != null &&
 390215435                    await queued((enumerator.EdgeId, enumerator.Head)))
 0436                {
 437                    // don't queue this edge if the queued function returns true.
 0438                    continue;
 439                }
 440
 441                // add visit if not added yet.
 390215442                if (neighbourPointer == uint.MaxValue)
 267944443                {
 267944444                    neighbourPointer =
 267944445                        _tree.AddVisit(enumerator, newLeftMain, neighbourLocalAccess, currentPointer);
 267944446                }
 447
 448                // add visit to heap.
 390215449                _heap.Push((neighbourPointer, enumerator.EdgeId, enumerator.Head, newLeftMain), neighbourCost + currentC
 390215450            }
 250545451        }
 452
 11571453        var paths = new (Path? path, double cost)[targets.Count];
 402764454        for (var p = 0; p < paths.Length; p++)
 189811455        {
 189811456            var bestTarget = bestTargets[p];
 189811457            if (bestTarget.pointer == uint.MaxValue)
 59497458            {
 59497459                paths[p] = (null, double.MaxValue);
 59497460                continue;
 461            }
 462
 463            // build resulting path.
 130314464            var path = new Path(network);
 130314465            var visit = _tree.GetVisit(bestTarget.pointer);
 466
 467            // path is at least two edges.
 711685468            while (true)
 711685469            {
 711685470                if (visit.previousPointer == uint.MaxValue)
 130314471                {
 130314472                    enumerator.MoveTo(visit.edge);
 130314473                    path.Prepend(visit.edge, visit.forward);
 130314474                    break;
 475                }
 476
 581371477                path.Prepend(visit.edge, visit.forward);
 581371478                visit = _tree.GetVisit(visit.previousPointer);
 581371479            }
 480
 481            // add the offsets.
 130314482            var target = targets[p];
 130314483            path.Offset1 = path.First.direction ? source.sp.Offset : (ushort)(ushort.MaxValue - source.sp.Offset);
 130314484            path.Offset2 = path.Last.direction
 130314485                ? target.sp.Offset
 130314486                : (ushort)(ushort.MaxValue - target.sp.Offset);
 487
 130314488            paths[p] = (path, bestTarget.cost);
 130314489        }
 490
 11571491        return paths;
 11571492    }
 493
 494    /// <summary>
 495    /// Hybrid "is main-N?" predicate. Consults <paramref name="isMainN"/> first; when that
 496    /// returns null (the tile isn't classified yet) falls back to <c>!leftMain</c>. The fallback
 497    /// is path-dependent: while we still believe we are in main (<c>leftMain == false</c>) an
 498    /// unclassified edge is treated as main, so no spurious leftMain transition fires; once we
 499    /// have left main, an unclassified edge is treated as non-main, so no spurious re-entry
 500    /// rejection fires.
 501    /// </summary>
 502    private static bool IsMain(EdgeId edgeId, bool localAccess, bool leftMain, IsMainNFunc isMainN)
 780390503    {
 780390504        var verdict = isMainN(edgeId, localAccess);
 780390505        return verdict ?? !leftMain;
 780390506    }
 507
 508    /// <summary>
 509    /// Gets a fresh Dijkstra instance for this call. Was previously a [ThreadStatic]
 510    /// reuse, but that's unsafe under async/await + ThreadPool reuse: thread A starts
 511    /// a routing call on instance D, awaits a callback, returns to the pool, picks up
 512    /// a second routing call — Default returns the same D, and now two routing calls
 513    /// mutate D's _heap/_visits/_tree concurrently → "concurrent update" crash.
 514    /// Allocating three small collections per call is cheap vs. the routing work.
 515    /// </summary>
 11571516    public static Dijkstra Default => new();
 517}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

.ctor()
RunAsync()
RunAsync()
RunAsync()
RunAsync()
IsMain(...)
get_Default()