< 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:259
Uncovered lines:30
Coverable lines:289
Total lines:546
Line coverage:89.6% (259 of 289)
Covered branches:135
Total branches:154
Branch coverage:87.6% (135 of 154)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
RunAsync()0%20%
RunAsync()50%2100%
RunAsync()100%2100%
RunAsync()88.97%13690.53%
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{
 2535    private readonly PathTree _tree = new();
 2536    private readonly HashSet<(EdgeId edgeId, VertexId vertexId, bool leftMain)> _visits = new();
 37    // Carries g (cost so far) because the heap is ordered by f = g + h; relaxation
 38    // and target costs need g, and recovering it at pop time would cost a tile lookup.
 2539    private readonly BinaryHeap<(uint pointer, EdgeId edgeId, VertexId vertexId, bool leftMain, double g)> _heap = new()
 40
 41    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network, SnapPoint source,
 42        SnapPoint target,
 43        DijkstraWeightFunc getDijkstraWeight,
 44        Func<(EdgeId edgeId, VertexId vertexId, double cost), Task<bool>>? settled = null,
 45        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 46        CancellationToken cancellationToken = default,
 47        IsMainNFunc? isMainN = null,
 48        HeuristicFunc? heuristic = null)
 049    {
 050        var paths = await this.RunAsync(network, (source, null), new[] { (target, (bool?)null) }, getDijkstraWeight,
 051            settled, queued, cancellationToken, isMainN, heuristic);
 52
 053        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 054    }
 55
 56    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network,
 57        (SnapPoint sp, bool? direction) source,
 58        (SnapPoint sp, bool? direction) target,
 59        DijkstraWeightFunc getDijkstraWeight,
 60        Func<(EdgeId edgeId, VertexId vertexId, double cost), Task<bool>>? settled = null,
 61        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 62        CancellationToken cancellationToken = default,
 63        IsMainNFunc? isMainN = null,
 64        HeuristicFunc? heuristic = null)
 2265    {
 2266        var paths = await this.RunAsync(network, source, new[] { target }, getDijkstraWeight, settled, queued, cancellat
 67
 2268        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 2269    }
 70
 71    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network, SnapPoint source,
 72        IReadOnlyList<SnapPoint> targets,
 73        DijkstraWeightFunc getDijkstraWeight,
 74        Func<(EdgeId edgeId, VertexId vertexId, double cost), Task<bool>>? settled = null,
 75        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 76        CancellationToken cancellationToken = default,
 77        IsMainNFunc? isMainN = null,
 78        HeuristicFunc? heuristic = null)
 1154279    {
 1154280        var directedTargets = new (SnapPoint sp, bool? direction)[targets.Count];
 40263681        for (var i = 0; i < targets.Count; i++)
 18977682        {
 18977683            directedTargets[i] = (targets[i], null);
 18977684        }
 85
 1154286        return await this.RunAsync(network, (source, null), directedTargets,
 1154287            getDijkstraWeight, settled, queued, cancellationToken, isMainN, heuristic);
 1154288    }
 89
 90    /// <summary>
 91    ///
 92    /// </summary>
 93    /// <param name="network"></param>
 94    /// <param name="source"></param>
 95    /// <param name="targets"></param>
 96    /// <param name="getDijkstraWeight"></param>
 97    /// <param name="settled">
 98    /// Called once per state whose minimal cost is final, with that cost. Return true to stop
 99    /// expanding from it — which is how a search is cut at a cost bound, as an isochrone does.
 100    /// </param>
 101    /// <param name="queued">This callback is called before an edge is loaded. Should not be used to influence route pla
 102    /// <param name="isMainN">Optional access-aware predicate. When supplied the search tracks a
 103    /// sticky <c>leftMain</c> bit and rejects any relaxation back onto a main-N edge after the
 104    /// first main → non-main transition.</param>
 105    /// <returns></returns>
 106    /// <exception cref="Exception"></exception>
 107    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network,
 108        (SnapPoint sp, bool? direction) source,
 109        IReadOnlyList<(SnapPoint sp, bool? direction)> targets,
 110        DijkstraWeightFunc getDijkstraWeight,
 111        Func<(EdgeId edgeId, VertexId vertexId, double cost), Task<bool>>? settled = null,
 112        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 113        CancellationToken cancellationToken = default,
 114        IsMainNFunc? isMainN = null,
 115        HeuristicFunc? heuristic = null)
 11588116    {
 117        static double GetWorst((uint pointer, double cost)[] targets)
 133862118        {
 119            // No targets means nothing to improve on, so there is no cost at which the search can
 120            // stop early: it runs until the heap empties or `settled` prunes it. That is the
 121            // isochrone case.
 133879122            if (targets.Length == 0) return double.MaxValue;
 123
 133845124            var worst = 0d;
 776532125            for (var i = 0; i < targets.Length; i++)
 383953126            {
 383953127                if (!(targets[i].cost > worst))
 154873128                {
 154873129                    continue;
 130                }
 131
 229080132                worst = targets[i].cost;
 229080133                if (worst >= double.MaxValue)
 129532134                {
 129532135                    break;
 136                }
 99548137            }
 138
 133845139            return worst;
 133862140        }
 141
 142        // Cost still to pay from the edge's head; 0 without a heuristic, making the
 143        // search plain Dijkstra. HeadLocation is memoised, so this adds no tile lookup.
 144        double Estimate(Itinero.Network.Enumerators.Edges.RoutingNetworkEdgeEnumerator e)
 422635145        {
 845270146            if (heuristic == null) return 0d;
 147
 0148            var (longitude, latitude, _) = e.HeadLocation;
 0149            return heuristic(longitude, latitude);
 422635150        }
 151
 11588152        var enumerator = network.GetEdgeEnumerator();
 153
 11588154        _tree.Clear();
 11588155        _visits.Clear();
 11588156        _heap.Clear();
 157
 158        // add sources. leftMain starts false on every source: the search has not yet
 159        // transitioned out of main-N (or has not yet entered, when source is non-main).
 11588160        var sourceForwardVisit = uint.MaxValue;
 11588161        if (source.Forward())
 11588162        {
 163            // add forward.
 11588164            if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0165            {
 0166                throw new Exception($"Edge in source {source} not found!");
 167            }
 168
 11588169            var sourceFwd = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable));
 11588170            if (sourceFwd.cost > 0)
 11588171            {
 172                // can traverse edge in the forward direction.
 11588173                var sourceOffsetCostForward = sourceFwd.cost * (1 - source.sp.OffsetFactor());
 11588174                sourceForwardVisit =
 11588175                    _tree.AddVisit(enumerator, leftMain: false, localAccess: sourceFwd.localAccess, uint.MaxValue);
 11588176                _heap.Push((sourceForwardVisit, enumerator.EdgeId, enumerator.Head, false, sourceOffsetCostForward),
 11588177                    sourceOffsetCostForward + Estimate(enumerator));
 11588178            }
 11588179        }
 180
 11588181        var sourceBackwardVisit = uint.MaxValue;
 11588182        if (source.Backward())
 11583183        {
 184            // add backward.
 11583185            if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0186            {
 0187                throw new Exception($"Edge in source {source} not found!");
 188            }
 189
 11583190            var sourceBwd = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable));
 11583191            if (sourceBwd.cost > 0)
 8360192            {
 193                // can traverse edge in the backward direction.
 8360194                var sourceOffsetCostBackward = sourceBwd.cost * source.sp.OffsetFactor();
 8360195                sourceBackwardVisit =
 8360196                    _tree.AddVisit(enumerator, leftMain: false, localAccess: sourceBwd.localAccess, uint.MaxValue);
 8360197                _heap.Push((sourceBackwardVisit, enumerator.EdgeId, enumerator.Head, false, sourceOffsetCostBackward),
 8360198                    sourceOffsetCostBackward + Estimate(enumerator));
 8360199            }
 11583200        }
 201
 202        // add targets.
 11588203        var bestTargets = new (uint pointer, double cost)[targets.Count];
 11588204        var targetsPerVertex = new Dictionary<VertexId, List<int>>();
 402798205        for (var t = 0; t < targets.Count; t++)
 189811206        {
 189811207            bestTargets[t] = (uint.MaxValue, double.MaxValue);
 189811208            var target = targets[t];
 209
 189811210            if (target.Forward())
 189808211            {
 212                // add forward.
 189808213                if (!enumerator.MoveTo(target.sp.EdgeId, true))
 0214                {
 0215                    throw new Exception($"Edge in target {target} not found!");
 216                }
 217
 189808218                var targetCostForward = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable))
 189808219                    .cost;
 189808220                if (targetCostForward > 0)
 189808221                {
 189808222                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 110335223                    {
 110335224                        targetsAtVertex = new List<int>();
 110335225                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 110335226                    }
 227
 189808228                    targetsAtVertex.Add(t);
 189808229                }
 189808230            }
 231
 189811232            if (target.Backward())
 189809233            {
 234                // add backward.
 189809235                if (!enumerator.MoveTo(target.sp.EdgeId, false))
 0236                {
 0237                    throw new Exception($"Edge in source {source} not found!");
 238                }
 239
 189809240                var targetCostBackward =
 189809241                    getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost;
 189809242                if (targetCostBackward > 0)
 102031243                {
 102031244                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 68899245                    {
 68899246                        targetsAtVertex = new List<int>();
 68899247                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 68899248                    }
 249
 102031250                    targetsAtVertex.Add(t);
 102031251                }
 189809252            }
 253
 254            // consider paths 'within' a single edge.
 189811255            if (source.sp.EdgeId != target.sp.EdgeId)
 180026256            {
 180026257                continue;
 258            }
 259
 9785260            if (source.sp.Offset == target.sp.Offset)
 5092261            {
 262                // source and target are identical.
 5092263                if (sourceForwardVisit != uint.MaxValue &&
 5092264                    target.Forward())
 5091265                {
 5091266                    bestTargets[t] = (sourceForwardVisit, 0);
 5091267                }
 1268                else if (sourceBackwardVisit != uint.MaxValue &&
 1269                         target.Backward())
 0270                {
 0271                    bestTargets[t] = (sourceForwardVisit, 0);
 0272                }
 5092273            }
 4693274            else if (source.sp.Offset < target.sp.Offset &&
 4693275                     source.Forward() && target.Forward())
 2865276            {
 277                // the source is earlier in the direction of the edge
 278                // and the edge can be traversed in this direction.
 2865279                if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0280                {
 0281                    throw new Exception($"Edge in source {source} not found!");
 282                }
 283
 2865284                var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 2865285                             (target.sp.OffsetFactor() - source.sp.OffsetFactor());
 2865286                bestTargets[t] = (sourceForwardVisit, weight);
 2865287            }
 1828288            else if (source.sp.Offset > target.sp.Offset &&
 1828289                     source.Backward() && target.Backward())
 1825290            {
 291                // the source is earlier against the direction of the edge
 292                // and the edge can be traversed in this direction.
 1825293                if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0294                {
 0295                    throw new Exception($"Edge in source {source} not found!");
 296                }
 297
 1825298                var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 1825299                             (source.sp.OffsetFactor() - target.sp.OffsetFactor());
 1825300                bestTargets[t] = (sourceBackwardVisit, weight);
 1825301            }
 9785302        }
 303
 304        // update worst target cost.
 11588305        var worstTargetCost = GetWorst(bestTargets);
 306
 307        // keep going until heap is empty.
 318597308        while (_heap.Count > 0)
 311513309        {
 311513310            cancellationToken.ThrowIfCancellationRequested();
 311
 312            // dequeue new visit. Dedup includes leftMain because the same (edge,vertex)
 313            // is reachable both with leftMain=false and leftMain=true; the former is
 314            // strictly more permissive but both can occur in the search.
 311513315            var currentEntry = _heap.Pop(out var currentCost);
 406695316            while (_visits.Contains((currentEntry.edgeId, currentEntry.vertexId, currentEntry.leftMain)))
 97173317            {
 318                // visited before, skip.
 97173319                if (_heap.Count == 0)
 1991320                {
 1991321                    currentEntry = (uint.MaxValue, default, default, false, 0d);
 1991322                    break;
 323                }
 324
 95182325                currentEntry = _heap.Pop(out currentCost);
 95182326            }
 327
 311513328            var currentPointer = currentEntry.pointer;
 311513329            if (currentPointer == uint.MaxValue)
 1991330            {
 1991331                break;
 332            }
 333
 334            // only call GetVisitWithState after the visited check passes.
 309522335            var currentVisit = _tree.GetVisitWithState(currentPointer);
 336
 337            // log visit.
 309522338            if (currentVisit.previousPointer != uint.MaxValue)
 290128339            {
 290128340                _visits.Add((currentEntry.edgeId, currentEntry.vertexId, currentEntry.leftMain));
 290128341            }
 342
 309522343            if (settled != null && await settled((currentEntry.edgeId, currentEntry.vertexId, currentCost)))
 52058344            {
 345                // the best cost to this edge has already been found; current visit can not improve this anymore so we c
 52058346                continue;
 347            }
 348
 349            // check if the search needs to stop.
 257464350            if (currentCost > worstTargetCost)
 2513351            {
 352                // impossible to improve on cost to any target.
 2513353                break;
 354            }
 355
 356            // check neighbours.
 254951357            if (!enumerator.MoveTo(currentVisit.vertex))
 0358            {
 359                // no edges, move on!
 0360                continue;
 361            }
 362
 363            // check if this is a target.
 254951364            if (!targetsPerVertex.TryGetValue(currentVisit.vertex, out var targetsAtVertex))
 115834365            {
 115834366                targetsAtVertex = null;
 115834367            }
 368
 1066791369            while (enumerator.MoveNext())
 811840370            {
 371                // filter out if u-turns or visits on the same edge.
 811840372                var neighbourEdge = enumerator.EdgeId;
 811840373                if (neighbourEdge == currentVisit.edge)
 254951374                {
 254951375                    continue;
 376                }
 377
 378                // gets the cost of the current edge.
 556889379                var (neighbourCost, turnCost, neighbourLocalAccess) =
 556889380                    getDijkstraWeight(enumerator, new PreviousEdgeEnumerable(_tree, currentPointer));
 556889381                if (neighbourCost is >= double.MaxValue or <= 0)
 154190382                {
 154190383                    continue;
 384                }
 385
 402699386                if (turnCost is >= double.MaxValue or < 0)
 11387                {
 11388                    continue;
 389                }
 390
 391                // Access-aware state-bit logic. When isMainN is null this block is a no-op:
 392                // newLeftMain stays false and no relaxation is rejected.
 402688393                var newLeftMain = false;
 402688394                if (isMainN != null)
 402667395                {
 402667396                    var prevMain = IsMain(currentVisit.edge, currentVisit.localAccess, currentVisit.leftMain, isMainN);
 402667397                    var neighbourMain = IsMain(neighbourEdge, neighbourLocalAccess, currentVisit.leftMain, isMainN);
 398
 399                    // Rule: once leftMain is true we may not relax onto a main-N edge again.
 400                    // That would mean re-entering main-N after having departed, i.e. an L-edge
 401                    // (or non-main-N pocket) used as through-traffic between two main-N segments.
 402668402                    if (currentVisit.leftMain && neighbourMain) continue;
 403
 404                    // newLeftMain is sticky and flips on the first main-N → non-main-N transition.
 402666405                    newLeftMain = currentVisit.leftMain || (prevMain && !neighbourMain);
 402666406                }
 407
 408                // if the vertex has targets, check if this edge is a match.
 402687409                var neighbourPointer = uint.MaxValue;
 402687410                if (targetsAtVertex != null)
 221010411                {
 412                    // only consider targets when found for the 'from' vertex.
 413                    // and when this in not a u-turn.
 1638960414                    foreach (var t in targetsAtVertex)
 487965415                    {
 487965416                        var target = targets[t];
 487965417                        if (target.sp.EdgeId != neighbourEdge)
 297180418                        {
 297180419                            continue;
 420                        }
 421
 422                        // check directions.
 190785423                        if (enumerator.Forward && !target.Forward())
 0424                        {
 0425                            continue;
 426                        }
 427
 190785428                        if (!enumerator.Forward && !target.Backward())
 0429                        {
 0430                            continue;
 431                        }
 432
 433                        // there is a target on this edge, calculate the cost.
 434                        // calculate the cost from the 'from' vertex to the target.
 190785435                        var targetCost = enumerator.Forward
 190785436                            ? neighbourCost * target.sp.OffsetFactor()
 190785437                            : neighbourCost * (1 - target.sp.OffsetFactor());
 438                        // this is the case where the target is on this edge
 439                        // and there is a path to 'from' before.
 190785440                        targetCost += currentEntry.g;
 441
 190785442                        targetCost += turnCost;
 443
 444                        // if this is an improvement, use it!
 190785445                        var targetBestCost = bestTargets[t].cost;
 190785446                        if (!(targetCost < targetBestCost))
 68511447                        {
 68511448                            continue;
 449                        }
 450
 451                        // this is an improvement.
 122274452                        neighbourPointer = _tree.AddVisit(enumerator, newLeftMain, neighbourLocalAccess, currentPointer)
 122274453                        bestTargets[t] = (neighbourPointer, targetCost);
 454
 455                        // update worst.
 122274456                        worstTargetCost = GetWorst(bestTargets);
 122274457                    }
 221010458                }
 459
 402687460                if (queued != null &&
 402687461                    await queued((enumerator.EdgeId, enumerator.Head)))
 0462                {
 463                    // don't queue this edge if the queued function returns true.
 0464                    continue;
 465                }
 466
 467                // add visit if not added yet.
 402687468                if (neighbourPointer == uint.MaxValue)
 280416469                {
 280416470                    neighbourPointer =
 280416471                        _tree.AddVisit(enumerator, newLeftMain, neighbourLocalAccess, currentPointer);
 280416472                }
 473
 474                // add visit to heap.
 402687475                var neighbourG = neighbourCost + currentEntry.g + turnCost;
 402687476                _heap.Push((neighbourPointer, enumerator.EdgeId, enumerator.Head, newLeftMain, neighbourG),
 402687477                    neighbourG + Estimate(enumerator));
 402687478            }
 254951479        }
 480
 11588481        var paths = new (Path? path, double cost)[targets.Count];
 402798482        for (var p = 0; p < paths.Length; p++)
 189811483        {
 189811484            var bestTarget = bestTargets[p];
 189811485            if (bestTarget.pointer == uint.MaxValue)
 59497486            {
 59497487                paths[p] = (null, double.MaxValue);
 59497488                continue;
 489            }
 490
 491            // build resulting path.
 130314492            var path = new Path(network);
 130314493            var visit = _tree.GetVisit(bestTarget.pointer);
 494
 495            // path is at least two edges.
 711685496            while (true)
 711685497            {
 711685498                if (visit.previousPointer == uint.MaxValue)
 130314499                {
 130314500                    enumerator.MoveTo(visit.edge);
 130314501                    path.Prepend(visit.edge, visit.forward);
 130314502                    break;
 503                }
 504
 581371505                path.Prepend(visit.edge, visit.forward);
 581371506                visit = _tree.GetVisit(visit.previousPointer);
 581371507            }
 508
 509            // add the offsets.
 130314510            var target = targets[p];
 130314511            path.Offset1 = path.First.direction ? source.sp.Offset : (ushort)(ushort.MaxValue - source.sp.Offset);
 130314512            path.Offset2 = path.Last.direction
 130314513                ? target.sp.Offset
 130314514                : (ushort)(ushort.MaxValue - target.sp.Offset);
 515
 130314516            paths[p] = (path, bestTarget.cost);
 130314517        }
 518
 519
 11588520        return paths;
 11588521    }
 522
 523    /// <summary>
 524    /// Hybrid "is main-N?" predicate. Consults <paramref name="isMainN"/> first; when that
 525    /// returns null (the tile isn't classified yet) falls back to <c>!leftMain</c>. The fallback
 526    /// is path-dependent: while we still believe we are in main (<c>leftMain == false</c>) an
 527    /// unclassified edge is treated as main, so no spurious leftMain transition fires; once we
 528    /// have left main, an unclassified edge is treated as non-main, so no spurious re-entry
 529    /// rejection fires.
 530    /// </summary>
 531    private static bool IsMain(EdgeId edgeId, bool localAccess, bool leftMain, IsMainNFunc isMainN)
 805334532    {
 805334533        var verdict = isMainN(edgeId, localAccess);
 805334534        return verdict ?? !leftMain;
 805334535    }
 536
 537    /// <summary>
 538    /// Gets a fresh Dijkstra instance for this call. Was previously a [ThreadStatic]
 539    /// reuse, but that's unsafe under async/await + ThreadPool reuse: thread A starts
 540    /// a routing call on instance D, awaits a callback, returns to the pool, picks up
 541    /// a second routing call — Default returns the same D, and now two routing calls
 542    /// mutate D's _heap/_visits/_tree concurrently → "concurrent update" crash.
 543    /// Allocating three small collections per call is cheap vs. the routing work.
 544    /// </summary>
 24545    public static Dijkstra Default => new();
 546}