< Summary

Class:Itinero.Routing.Flavours.Dijkstra.EdgeBased.Dijkstra
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/EdgeBased/Dijkstra.cs
Covered lines:241
Uncovered lines:28
Coverable lines:269
Total lines:464
Line coverage:89.5% (241 of 269)
Covered branches:125
Total branches:142
Branch coverage:88% (125 of 142)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
RunAsync()0%20%
RunAsync()50%2100%
RunAsync()100%2100%
RunAsync()89.06%12890.12%
get_Default()100%2100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/EdgeBased/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.EdgeBased;
 17
 18/// <summary>
 19/// An edge-based dijkstra implementation.
 20/// </summary>
 21internal class Dijkstra
 22{
 2123    private readonly PathTree _tree = new();
 2124    private readonly HashSet<(EdgeId edgeId, VertexId vertexId)> _visits = new();
 2125    private readonly BinaryHeap<(uint pointer, EdgeId edgeId, VertexId vertexId)> _heap = new();
 26
 27    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network, SnapPoint source,
 28        SnapPoint target,
 29        DijkstraWeightFunc getDijkstraWeight,
 30        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 31        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 32        CancellationToken cancellationToken = default)
 033    {
 034        var paths = await this.RunAsync(network, (source, null), new[] { (target, (bool?)null) }, getDijkstraWeight,
 035            settled, queued, cancellationToken);
 36
 037        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 038    }
 39
 40    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network,
 41        (SnapPoint sp, bool? direction) source,
 42        (SnapPoint sp, bool? direction) target,
 43        DijkstraWeightFunc getDijkstraWeight,
 44        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 45        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 46        CancellationToken cancellationToken = default)
 1547    {
 1548        var paths = await this.RunAsync(network, source, new[] { target }, getDijkstraWeight, settled, queued, cancellat
 49
 1550        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 1551    }
 52
 53    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network, SnapPoint source,
 54        IReadOnlyList<SnapPoint> targets,
 55        DijkstraWeightFunc getDijkstraWeight,
 56        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 57        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 58        CancellationToken cancellationToken = default)
 1129359    {
 1129360        var directedTargets = new (SnapPoint sp, bool? direction)[targets.Count];
 39721061        for (var i = 0; i < targets.Count; i++)
 18731262        {
 18731263            directedTargets[i] = (targets[i], null);
 18731264        }
 65
 1129366        return await this.RunAsync(network, (source, null), directedTargets,
 1129367            getDijkstraWeight, settled, queued, cancellationToken);
 1129368    }
 69
 70    /// <summary>
 71    ///
 72    /// </summary>
 73    /// <param name="network"></param>
 74    /// <param name="source"></param>
 75    /// <param name="targets"></param>
 76    /// <param name="getDijkstraWeight"></param>
 77    /// <param name="settled">This Callback is called for every edge for which the minimal cost is known. If this callba
 78    /// <param name="queued">This callback is called before an edge is loaded. Should not be used to influence route pla
 79    /// <returns></returns>
 80    /// <exception cref="Exception"></exception>
 81    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network,
 82        (SnapPoint sp, bool? direction) source,
 83        IReadOnlyList<(SnapPoint sp, bool? direction)> targets,
 84        DijkstraWeightFunc getDijkstraWeight,
 85        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 86        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 87        CancellationToken cancellationToken = default)
 1131088    {
 89        static double GetWorst((uint pointer, double cost)[] targets)
 13237590        {
 13237591            var worst = 0d;
 76659092            for (var i = 0; i < targets.Length; i++)
 37900493            {
 37900494                if (!(targets[i].cost > worst))
 15440295                {
 15440296                    continue;
 97                }
 98
 22460299                worst = targets[i].cost;
 224602100                if (worst >= double.MaxValue)
 128084101                {
 128084102                    break;
 103                }
 96518104            }
 105
 132375106            return worst;
 132375107        }
 108
 11310109        var enumerator = network.GetEdgeEnumerator();
 110
 11310111        _tree.Clear();
 11310112        _visits.Clear();
 11310113        _heap.Clear();
 114
 115        // add sources.
 11310116        var sourceForwardVisit = uint.MaxValue;
 11310117        if (source.Forward())
 11310118        {
 119            // add forward.
 11310120            if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0121            {
 0122                throw new Exception($"Edge in source {source} not found!");
 123            }
 124
 11310125            var sourceCostForward =
 11310126                getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost;
 11310127            if (sourceCostForward > 0)
 11310128            {
 129                // can traverse edge in the forward direction.
 11310130                var sourceOffsetCostForward = sourceCostForward * (1 - source.sp.OffsetFactor());
 11310131                sourceForwardVisit =
 11310132                    _tree.AddVisit(enumerator, uint.MaxValue);
 11310133                _heap.Push((sourceForwardVisit, enumerator.EdgeId, enumerator.Head), sourceOffsetCostForward);
 11310134            }
 11310135        }
 136
 11310137        var sourceBackwardVisit = uint.MaxValue;
 11310138        if (source.Backward())
 11305139        {
 140            // add backward.
 11305141            if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0142            {
 0143                throw new Exception($"Edge in source {source} not found!");
 144            }
 145
 11305146            var sourceCostBackward =
 11305147                getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost;
 11305148            if (sourceCostBackward > 0)
 8087149            {
 150                // can traverse edge in the backward direction.
 8087151                var sourceOffsetCostBackward = sourceCostBackward * source.sp.OffsetFactor();
 8087152                sourceBackwardVisit =
 8087153                    _tree.AddVisit(enumerator, uint.MaxValue);
 8087154                _heap.Push((sourceBackwardVisit, enumerator.EdgeId, enumerator.Head), sourceOffsetCostBackward);
 8087155            }
 11305156        }
 157
 158        // add targets.
 11310159        var bestTargets = new (uint pointer, double cost)[targets.Count];
 11310160        var targetsPerVertex = new Dictionary<VertexId, List<int>>();
 397290161        for (var t = 0; t < targets.Count; t++)
 187335162        {
 187335163            bestTargets[t] = (uint.MaxValue, double.MaxValue);
 187335164            var target = targets[t];
 165
 187335166            if (target.Forward())
 187332167            {
 168                // add forward.
 187332169                if (!enumerator.MoveTo(target.sp.EdgeId, true))
 0170                {
 0171                    throw new Exception($"Edge in target {target} not found!");
 172                }
 173
 187332174                var targetCostForward = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable))
 187332175                    .cost;
 187332176                if (targetCostForward > 0)
 187332177                {
 187332178                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 108951179                    {
 108951180                        targetsAtVertex = new List<int>();
 108951181                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 108951182                    }
 183
 187332184                    targetsAtVertex.Add(t);
 187332185                }
 187332186            }
 187
 187335188            if (target.Backward())
 187333189            {
 190                // add backward.
 187333191                if (!enumerator.MoveTo(target.sp.EdgeId, false))
 0192                {
 0193                    throw new Exception($"Edge in source {source} not found!");
 194                }
 195
 187333196                var targetCostBackward =
 187333197                    getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost;
 187333198                if (targetCostBackward > 0)
 100215199                {
 100215200                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 67461201                    {
 67461202                        targetsAtVertex = new List<int>();
 67461203                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 67461204                    }
 205
 100215206                    targetsAtVertex.Add(t);
 100215207                }
 187333208            }
 209
 210            // consider paths 'within' a single edge.
 187335211            if (source.sp.EdgeId != target.sp.EdgeId)
 177788212            {
 177788213                continue;
 214            }
 215
 9547216            if (source.sp.Offset == target.sp.Offset)
 5176217            {
 218                // source and target are identical.
 5176219                if (sourceForwardVisit != uint.MaxValue &&
 5176220                    target.Forward())
 5175221                {
 5175222                    bestTargets[t] = (sourceForwardVisit, 0);
 5175223                }
 1224                else if (sourceBackwardVisit != uint.MaxValue &&
 1225                         target.Backward())
 0226                {
 0227                    bestTargets[t] = (sourceForwardVisit, 0);
 0228                }
 5176229            }
 4371230            else if (source.sp.Offset < target.sp.Offset &&
 4371231                     source.Forward() && target.Forward())
 2622232            {
 233                // the source is earlier in the direction of the edge
 234                // and the edge can be traversed in this direction.
 2622235                if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0236                {
 0237                    throw new Exception($"Edge in source {source} not found!");
 238                }
 239
 2622240                var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 2622241                             (target.sp.OffsetFactor() - source.sp.OffsetFactor());
 2622242                bestTargets[t] = (sourceForwardVisit, weight);
 2622243            }
 1749244            else if (source.sp.Offset > target.sp.Offset &&
 1749245                     source.Backward() && target.Backward())
 1746246            {
 247                // the source is earlier against the direction of the edge
 248                // and the edge can be traversed in this direction.
 1746249                if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0250                {
 0251                    throw new Exception($"Edge in source {source} not found!");
 252                }
 253
 1746254                var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 1746255                             (source.sp.OffsetFactor() - target.sp.OffsetFactor());
 1746256                bestTargets[t] = (sourceBackwardVisit, weight);
 1746257            }
 9547258        }
 259
 260        // update worst target cost.
 11310261        var worstTargetCost = GetWorst(bestTargets);
 262
 263        // keep going until heap is empty.
 310589264        while (_heap.Count > 0)
 303725265        {
 303725266            cancellationToken.ThrowIfCancellationRequested();
 267
 268            // dequeue new visit.
 303725269            var currentEntry = _heap.Pop(out var currentCost);
 391279270            while (_visits.Contains((currentEntry.edgeId, currentEntry.vertexId)))
 89511271            {
 272                // visited before, skip.
 89511273                if (_heap.Count == 0)
 1957274                {
 1957275                    currentEntry = (uint.MaxValue, default, default);
 1957276                    break;
 277                }
 278
 87554279                currentEntry = _heap.Pop(out currentCost);
 87554280            }
 281
 303725282            var currentPointer = currentEntry.pointer;
 303725283            if (currentPointer == uint.MaxValue)
 1957284            {
 1957285                break;
 286            }
 287
 288            // only call GetVisit after the visited check passes.
 301768289            var currentVisit = _tree.GetVisit(currentPointer);
 290
 291            // log visit.
 301768292            if (currentVisit.previousPointer != uint.MaxValue)
 282917293            {
 282917294                _visits.Add((currentEntry.edgeId, currentEntry.vertexId));
 282917295            }
 296
 301768297            if (settled != null && await settled((currentEntry.edgeId, currentEntry.vertexId)))
 50421298            {
 299                // the best cost to this edge has already been found; current visit can not improve this anymore so we c
 50421300                continue;
 301            }
 302
 303            // check if the search needs to stop.
 251347304            if (currentCost > worstTargetCost)
 2489305            {
 306                // impossible to improve on cost to any target.
 2489307                break;
 308            }
 309
 310            // check neighbours.
 248858311            if (!enumerator.MoveTo(currentVisit.vertex))
 0312            {
 313                // no edges, move on!
 0314                continue;
 315            }
 316
 317            // check if this is a target.
 248858318            if (!targetsPerVertex.TryGetValue(currentVisit.vertex, out var targetsAtVertex))
 110948319            {
 110948320                targetsAtVertex = null;
 110948321            }
 322
 1038793323            while (enumerator.MoveNext())
 789935324            {
 325                // filter out if u-turns or visits on the same edge.
 789935326                var neighbourEdge = enumerator.EdgeId;
 789935327                if (neighbourEdge == currentVisit.edge)
 248858328                {
 248858329                    continue;
 330                }
 331
 332                // gets the cost of the current edge.
 541077333                var (neighbourCost, turnCost) =
 541077334                    getDijkstraWeight(enumerator, new PreviousEdgeEnumerable(_tree, currentPointer));
 541077335                if (neighbourCost is >= double.MaxValue or <= 0)
 153341336                {
 153341337                    continue;
 338                }
 339
 387736340                if (turnCost is >= double.MaxValue or < 0)
 5341                {
 5342                    continue;
 343                }
 344
 345                // if the vertex has targets, check if this edge is a match.
 387731346                var neighbourPointer = uint.MaxValue;
 387731347                if (targetsAtVertex != null)
 219176348                {
 349                    // only consider targets when found for the 'from' vertex.
 350                    // and when this in not a u-turn.
 1625248351                    foreach (var t in targetsAtVertex)
 483860352                    {
 483860353                        var target = targets[t];
 483860354                        if (target.sp.EdgeId != neighbourEdge)
 294651355                        {
 294651356                            continue;
 357                        }
 358
 359                        // check directions.
 189209360                        if (enumerator.Forward && !target.Forward())
 0361                        {
 0362                            continue;
 363                        }
 364
 189209365                        if (!enumerator.Forward && !target.Backward())
 0366                        {
 0367                            continue;
 368                        }
 369
 370                        // there is a target on this edge, calculate the cost.
 371                        // calculate the cost from the 'from' vertex to the target.
 189209372                        var targetCost = enumerator.Forward
 189209373                            ? neighbourCost * target.sp.OffsetFactor()
 189209374                            : neighbourCost * (1 - target.sp.OffsetFactor());
 375                        // this is the case where the target is on this edge
 376                        // and there is a path to 'from' before.
 189209377                        targetCost += currentCost;
 378
 189209379                        targetCost += turnCost;
 380
 381                        // if this is an improvement, use it!
 189209382                        var targetBestCost = bestTargets[t].cost;
 189209383                        if (!(targetCost < targetBestCost))
 68144384                        {
 68144385                            continue;
 386                        }
 387
 388                        // this is an improvement.
 121065389                        neighbourPointer = _tree.AddVisit(enumerator, currentPointer);
 121065390                        bestTargets[t] = (neighbourPointer, targetCost);
 391
 392                        // update worst.
 121065393                        worstTargetCost = GetWorst(bestTargets);
 121065394                    }
 219176395                }
 396
 387731397                if (queued != null &&
 387731398                    await queued((enumerator.EdgeId, enumerator.Head)))
 0399                {
 400                    // don't queue this edge if the queued function returns true.
 0401                    continue;
 402                }
 403
 404                // add visit if not added yet.
 387731405                if (neighbourPointer == uint.MaxValue)
 266669406                {
 266669407                    neighbourPointer =
 266669408                        _tree.AddVisit(enumerator, currentPointer);
 266669409                }
 410
 411                // add visit to heap.
 387731412                _heap.Push((neighbourPointer, enumerator.EdgeId, enumerator.Head), neighbourCost + currentCost + turnCos
 387731413            }
 248858414        }
 415
 11310416        var paths = new (Path? path, double cost)[targets.Count];
 397290417        for (var p = 0; p < paths.Length; p++)
 187335418        {
 187335419            var bestTarget = bestTargets[p];
 187335420            if (bestTarget.pointer == uint.MaxValue)
 58477421            {
 58477422                paths[p] = (null, double.MaxValue);
 58477423                continue;
 424            }
 425
 426            // build resulting path.
 128858427            var path = new Path(network);
 128858428            var visit = _tree.GetVisit(bestTarget.pointer);
 429
 430            // path is at least two edges.
 705558431            while (true)
 705558432            {
 705558433                if (visit.previousPointer == uint.MaxValue)
 128858434                {
 128858435                    enumerator.MoveTo(visit.edge);
 128858436                    path.Prepend(visit.edge, visit.forward);
 128858437                    break;
 438                }
 439
 576700440                path.Prepend(visit.edge, visit.forward);
 576700441                visit = _tree.GetVisit(visit.previousPointer);
 576700442            }
 443
 444            // add the offsets.
 128858445            var target = targets[p];
 128858446            path.Offset1 = path.First.direction ? source.sp.Offset : (ushort)(ushort.MaxValue - source.sp.Offset);
 128858447            path.Offset2 = path.Last.direction
 128858448                ? target.sp.Offset
 128858449                : (ushort)(ushort.MaxValue - target.sp.Offset);
 450
 128858451            paths[p] = (path, bestTarget.cost);
 128858452        }
 453
 11310454        return paths;
 11310455    }
 456
 457    [ThreadStatic]
 458    private static Dijkstra? _default;
 459
 460    /// <summary>
 461    /// Gets a default dijkstra instance (reused per thread).
 462    /// </summary>
 11310463    public static Dijkstra Default => _default ??= new Dijkstra();
 464}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

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