< 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:175
Uncovered lines:30
Coverable lines:205
Total lines:373
Line coverage:85.3% (175 of 205)
Covered branches:80
Total branches:100
Branch coverage:80% (80 of 100)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
RunAsync()50%2100%
RunAsync()78.88%9083.6%
get_Default()100%2100%

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/// A dijkstra implementation.
 20/// </summary>
 21internal class Dijkstra
 22{
 123    private readonly PathTree _tree = new();
 124    private readonly HashSet<VertexId> _visits = new();
 125    private readonly BinaryHeap<(uint pointer, VertexId vertex)> _heap = new();
 26
 27    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network, SnapPoint source,
 28        SnapPoint target,
 29        DijkstraWeightFunc getDijkstraWeight, Func<VertexId, Task<bool>>? settled = null,
 30        Func<VertexId, Task<bool>>? queued = null)
 831    {
 832        var paths = await this.RunAsync(network, source, new[] { target }, getDijkstraWeight, settled, queued);
 33
 834        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 835    }
 36
 37    /// <summary>
 38    /// Run a one-to-many Dijkstra search
 39    /// </summary>
 40    /// <param name="network"></param>
 41    /// <param name="source"></param>
 42    /// <param name="targets"></param>
 43    /// <param name="getDijkstraWeight"></param>
 44    /// <param name="settled"></param>
 45    /// <param name="queued">Queued notifies listeners when a vertex is queued. If this function returns false, the requ
 46    /// <returns></returns>
 47    /// <exception cref="Exception"></exception>
 48    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network, SnapPoint source,
 49        IReadOnlyList<SnapPoint> targets,
 50        DijkstraWeightFunc getDijkstraWeight, Func<VertexId, Task<bool>>? settled = null,
 51        Func<VertexId, Task<bool>>? queued = null, CancellationToken cancellationToken = default)
 1052    {
 53        // Returns the worst cost of all targets, i.e. the cost of the most costly target to reach
 54        // Will be Double.MAX_VALUE if at least one target hasn't been reached
 55        static double GetWorst((uint pointer, double cost)[] targets)
 1956        {
 1957            var worst = 0d;
 8658            for (var i = 0; i < targets.Length; i++)
 3159            {
 3160                if (!(targets[i].cost > worst))
 961                {
 962                    continue;
 63                }
 64
 2265                worst = targets[i].cost;
 2266                if (worst >= double.MaxValue)
 767                {
 768                    break;
 69                }
 1570            }
 71
 1972            return worst;
 1973        }
 74
 1075        var enumerator = network.GetEdgeEnumerator();
 76
 1077        _tree.Clear();
 1078        _visits.Clear();
 1079        _heap.Clear();
 80
 81        // add sources.
 82        // add forward.
 1083        if (!enumerator.MoveTo(source.EdgeId, true))
 084        {
 085            throw new Exception($"Edge in source {source} not found!");
 86        }
 87
 1088        var sourceCostForward = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost;
 1089        var sourceForwardVisit = uint.MaxValue;
 1090        if (sourceCostForward > 0)
 1091        {
 92            // can traverse edge in the forward direction.
 1093            var sourceOffsetCostForward = sourceCostForward * (1 - source.OffsetFactor());
 1094            sourceForwardVisit = _tree.AddVisit(enumerator, uint.MaxValue);
 1095            _heap.Push((sourceForwardVisit, enumerator.Head), sourceOffsetCostForward);
 1096        }
 97
 98        // add backward.
 1099        if (!enumerator.MoveTo(source.EdgeId, false))
 0100        {
 0101            throw new Exception($"Edge in source {source} not found!");
 102        }
 103
 10104        var sourceCostBackward = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost;
 10105        var sourceBackwardVisit = uint.MaxValue;
 10106        if (sourceCostBackward > 0)
 10107        {
 108            // can traverse edge in the backward direction.
 10109            var sourceOffsetCostBackward = sourceCostBackward * source.OffsetFactor();
 10110            sourceBackwardVisit = _tree.AddVisit(enumerator, uint.MaxValue);
 10111            _heap.Push((sourceBackwardVisit, enumerator.Head), sourceOffsetCostBackward);
 10112        }
 113
 114        // add targets.
 10115        var bestTargets = new (uint pointer, double cost)[targets.Count];
 10116        var targetsPerVertex = new Dictionary<VertexId, List<int>>();
 52117        for (var t = 0; t < targets.Count; t++)
 16118        {
 16119            bestTargets[t] = (uint.MaxValue, double.MaxValue);
 16120            var target = targets[t];
 121
 122            // add targets to vertices.
 16123            if (!enumerator.MoveTo(target.EdgeId, true))
 0124            {
 0125                throw new Exception($"Edge in target {target} not found!");
 126            }
 127
 16128            if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 10129            {
 10130                targetsAtVertex = new List<int>();
 10131                targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 10132            }
 133
 16134            targetsAtVertex.Add(t);
 16135            if (!targetsPerVertex.TryGetValue(enumerator.Head, out targetsAtVertex))
 10136            {
 10137                targetsAtVertex = new List<int>();
 10138                targetsPerVertex[enumerator.Head] = targetsAtVertex;
 10139            }
 140
 16141            targetsAtVertex.Add(t);
 142
 143            // consider paths 'within' a single edge.
 16144            if (source.EdgeId == target.EdgeId)
 9145            {
 146                // the source and target are on the same edge.
 9147                if (source.Offset == target.Offset)
 0148                {
 149                    // source and target are identical.
 0150                    bestTargets[t] = (sourceForwardVisit, 0);
 0151                }
 9152                else if (source.Offset < target.Offset &&
 9153                         sourceForwardVisit != uint.MaxValue)
 9154                {
 155                    // the source is earlier in the direction of the edge
 156                    // and the edge can be traversed in this direction.
 9157                    if (!enumerator.MoveTo(source.EdgeId, true))
 0158                    {
 0159                        throw new Exception($"Edge in source {source} not found!");
 160                    }
 161
 9162                    var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 9163                                 (target.OffsetFactor() - source.OffsetFactor());
 9164                    bestTargets[t] = (sourceForwardVisit, weight);
 9165                }
 0166                else if (sourceBackwardVisit != uint.MaxValue)
 0167                {
 168                    // the source is earlier against the direction of the edge
 169                    // and the edge can be traversed in this direction.
 0170                    if (!enumerator.MoveTo(source.EdgeId, false))
 0171                    {
 0172                        throw new Exception($"Edge in source {source} not found!");
 173                    }
 174
 0175                    var weight = getDijkstraWeight(enumerator, default(PreviousEdgeEnumerable)).cost *
 0176                                 (source.OffsetFactor() - target.OffsetFactor());
 0177                    bestTargets[t] = (sourceBackwardVisit, weight);
 0178                }
 9179            }
 16180        }
 181
 182        // update worst target cost.
 10183        var worstTargetCost = GetWorst(bestTargets);
 184
 185        // keep going until heap is empty.
 32186        while (_heap.Count > 0)
 31187        {
 31188            cancellationToken.ThrowIfCancellationRequested();
 189
 190            // dequeue new visit.
 31191            var currentEntry = _heap.Pop(out var currentCost);
 34192            while (_visits.Contains(currentEntry.vertex))
 6193            {
 194                // visited before, skip.
 6195                if (_heap.Count == 0)
 3196                {
 3197                    currentEntry = (uint.MaxValue, default);
 3198                    break;
 199                }
 200
 3201                currentEntry = _heap.Pop(out currentCost);
 3202            }
 203
 31204            var currentPointer = currentEntry.pointer;
 31205            if (currentPointer == uint.MaxValue)
 3206            {
 3207                break;
 208            }
 209
 210            // only call GetVisit after the visited check passes.
 28211            var currentVisit = _tree.GetVisit(currentPointer);
 212
 213            // log visit.
 28214            _visits.Add(currentVisit.vertex);
 215
 28216            if (settled != null && await settled(currentVisit.vertex))
 0217            {
 218                // break if requested.
 0219                break;
 220            }
 221
 222            // check if the search needs to stop.
 28223            if (currentCost >= worstTargetCost)
 6224            {
 225                // impossible to improve on cost to any target.
 6226                break;
 227            }
 228
 229            // check neighbours.
 22230            if (!enumerator.MoveTo(currentVisit.vertex))
 0231            {
 232                // no edges, move on!
 0233                continue;
 234            }
 235
 236            // check if this is a target.
 22237            if (!targetsPerVertex.TryGetValue(currentVisit.vertex, out var targetsAtVertex))
 9238            {
 9239                targetsAtVertex = null;
 9240            }
 241
 60242            while (enumerator.MoveNext())
 38243            {
 244                // filter out if u-turns or visits on the same edge.
 38245                var neighbourEdge = enumerator.EdgeId;
 38246                if (neighbourEdge == currentVisit.edge)
 22247                {
 22248                    continue;
 249                }
 250
 251                // gets the cost of the current edge.
 16252                var (neighbourCost, turnCost) =
 16253                    getDijkstraWeight(enumerator, new PreviousEdgeEnumerable(_tree, currentPointer));
 16254                if (neighbourCost is >= double.MaxValue or <= 0)
 0255                {
 0256                    continue;
 257                }
 258
 16259                if (turnCost is >= double.MaxValue or < 0)
 1260                {
 1261                    continue;
 262                }
 263
 264                // if the vertex has targets, check if this edge is a match.
 15265                var neighbourPointer = uint.MaxValue;
 15266                if (targetsAtVertex != null)
 10267                {
 268                    // We have found a target!
 269
 270                    // only consider targets when found for the 'from' vertex.
 271                    // and when this in not a u-turn.
 56272                    foreach (var t in targetsAtVertex)
 13273                    {
 13274                        var target = targets[t];
 13275                        if (target.EdgeId != neighbourEdge)
 4276                        {
 4277                            continue;
 278                        }
 279
 280                        // there is a target on this edge, calculate the cost.
 281                        // calculate the cost from the 'from' vertex to the target.
 9282                        var targetCost = enumerator.Forward
 9283                            ? neighbourCost * target.OffsetFactor()
 9284                            : neighbourCost * (1 - target.OffsetFactor());
 285                        // this is the case where the target is on this edge
 286                        // and there is a path to 'from' before.
 9287                        targetCost += currentCost;
 288
 289                        // add turn cost.
 9290                        targetCost += turnCost;
 291
 292                        // if this is an improvement, use it!
 9293                        var targetBestCost = bestTargets[t].cost;
 9294                        if (!(targetCost < targetBestCost))
 0295                        {
 0296                            continue;
 297                        }
 298
 299                        // this is an improvement.
 9300                        neighbourPointer = _tree.AddVisit(enumerator, currentPointer);
 9301                        bestTargets[t] = (neighbourPointer, targetCost);
 302
 303                        // update worst.
 9304                        worstTargetCost = GetWorst(bestTargets);
 9305                    }
 10306                }
 307
 15308                if (queued != null &&
 15309                    await queued(enumerator.Head))
 0310                {
 311                    // don't queue this vertex if the queued function returns true.
 0312                    continue;
 313                }
 314
 315                // add visit if not added yet.
 15316                if (neighbourPointer == uint.MaxValue)
 9317                {
 9318                    neighbourPointer = _tree.AddVisit(enumerator, currentPointer);
 9319                }
 320
 321                // add visit to heap.
 15322                _heap.Push((neighbourPointer, enumerator.Head), neighbourCost + currentCost + turnCost);
 15323            }
 22324        }
 325
 10326        var paths = new (Path? path, double cost)[targets.Count];
 52327        for (var p = 0; p < paths.Length; p++)
 16328        {
 16329            var bestTarget = bestTargets[p];
 16330            if (bestTarget.pointer == uint.MaxValue)
 1331            {
 1332                paths[p] = (null, double.MaxValue);
 1333                continue;
 334            }
 335
 336            // build resulting path.
 15337            var path = new Path(network);
 15338            var visit = _tree.GetVisit(bestTarget.pointer);
 339
 340            // path is at least two edges.
 31341            while (true)
 31342            {
 31343                if (visit.previousPointer == uint.MaxValue)
 15344                {
 15345                    path.Prepend(visit.edge, visit.forward);
 15346                    break;
 347                }
 348
 16349                path.Prepend(visit.edge, visit.forward);
 16350                visit = _tree.GetVisit(visit.previousPointer);
 16351            }
 352
 353            // add the offsets.
 15354            var target = targets[p];
 15355            path.Offset1 = path.First.direction ? source.Offset : (ushort)(ushort.MaxValue - source.Offset);
 15356            path.Offset2 = path.Last.direction
 15357                ? target.Offset
 15358                : (ushort)(ushort.MaxValue - target.Offset);
 359
 15360            paths[p] = (path, bestTarget.cost);
 15361        }
 362
 10363        return paths;
 10364    }
 365
 366    [ThreadStatic]
 367    private static Dijkstra? _default;
 368
 369    /// <summary>
 370    /// Gets a default dijkstra instance (reused per thread).
 371    /// </summary>
 10372    public static Dijkstra Default => _default ??= new Dijkstra();
 373}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

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