< 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:176
Uncovered lines:30
Coverable lines:206
Total lines:372
Line coverage:85.4% (176 of 206)
Covered branches:78
Total branches:98
Branch coverage:79.5% (78 of 98)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
RunAsync()50%2100%
RunAsync()78.88%9083.51%
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/// A dijkstra implementation.
 20/// </summary>
 21internal class Dijkstra
 22{
 1023    private readonly PathTree _tree = new();
 1024    private readonly HashSet<VertexId> _visits = new();
 1025    private readonly BinaryHeap<uint> _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)
 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, Enumerable.Empty<(EdgeId edge, byte? turn)>()).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, 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, Enumerable.Empty<(EdgeId edge, byte? turn)>()).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, 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, Enumerable.Empty<(EdgeId edge, byte? turn)>()).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, Enumerable.Empty<(EdgeId edge, byte? turn)>()).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        {
 188            // dequeue new visit.
 31189            var currentPointer = _heap.Pop(out var currentCost);
 31190            var currentVisit = _tree.GetVisit(currentPointer);
 34191            while (_visits.Contains(currentVisit.vertex))
 6192            {
 193                // visited before, skip.
 6194                currentPointer = uint.MaxValue;
 6195                if (_heap.Count == 0)
 3196                {
 3197                    break;
 198                }
 199
 3200                currentPointer = _heap.Pop(out currentCost);
 3201                currentVisit = _tree.GetVisit(currentPointer);
 3202            }
 203
 31204            if (currentPointer == uint.MaxValue)
 3205            {
 3206                break;
 207            }
 208
 209            // log visit.
 28210            _visits.Add(currentVisit.vertex);
 211
 28212            if (settled != null && await settled(currentVisit.vertex))
 0213            {
 214                // break if requested.
 0215                break;
 216            }
 217
 218            // check if the search needs to stop.
 28219            if (currentCost >= worstTargetCost)
 6220            {
 221                // impossible to improve on cost to any target.
 6222                break;
 223            }
 224
 225            // check neighbours.
 22226            if (!enumerator.MoveTo(currentVisit.vertex))
 0227            {
 228                // no edges, move on!
 0229                continue;
 230            }
 231
 232            // check if this is a target.
 22233            if (!targetsPerVertex.TryGetValue(currentVisit.vertex, out var targetsAtVertex))
 9234            {
 9235                targetsAtVertex = null;
 9236            }
 237
 60238            while (enumerator.MoveNext())
 38239            {
 240                // filter out if u-turns or visits on the same edge.
 38241                var neighbourEdge = enumerator.EdgeId;
 38242                if (neighbourEdge == currentVisit.edge)
 22243                {
 22244                    continue;
 245                }
 246
 247                // gets the cost of the current edge.
 16248                var (neighbourCost, turnCost) =
 16249                    getDijkstraWeight(enumerator, _tree.GetPreviousEdges(currentPointer));
 16250                if (neighbourCost is >= double.MaxValue or <= 0)
 0251                {
 0252                    continue;
 253                }
 254
 16255                if (turnCost is >= double.MaxValue or < 0)
 1256                {
 1257                    continue;
 258                }
 259
 260                // if the vertex has targets, check if this edge is a match.
 15261                var neighbourPointer = uint.MaxValue;
 15262                if (targetsAtVertex != null)
 10263                {
 264                    // We have found a target!
 265
 266                    // only consider targets when found for the 'from' vertex.
 267                    // and when this in not a u-turn.
 56268                    foreach (var t in targetsAtVertex)
 13269                    {
 13270                        var target = targets[t];
 13271                        if (target.EdgeId != neighbourEdge)
 4272                        {
 4273                            continue;
 274                        }
 275
 276                        // there is a target on this edge, calculate the cost.
 277                        // calculate the cost from the 'from' vertex to the target.
 9278                        var targetCost = enumerator.Forward
 9279                            ? neighbourCost * target.OffsetFactor()
 9280                            : neighbourCost * (1 - target.OffsetFactor());
 281                        // this is the case where the target is on this edge
 282                        // and there is a path to 'from' before.
 9283                        targetCost += currentCost;
 284
 285                        // add turn cost.
 9286                        targetCost += turnCost;
 287
 288                        // if this is an improvement, use it!
 9289                        var targetBestCost = bestTargets[t].cost;
 9290                        if (!(targetCost < targetBestCost))
 0291                        {
 0292                            continue;
 293                        }
 294
 295                        // this is an improvement.
 9296                        neighbourPointer = _tree.AddVisit(enumerator, currentPointer);
 9297                        bestTargets[t] = (neighbourPointer, targetCost);
 298
 299                        // update worst.
 9300                        worstTargetCost = GetWorst(bestTargets);
 9301                    }
 10302                }
 303
 15304                if (queued != null &&
 15305                    await queued(enumerator.Head))
 0306                {
 307                    // don't queue this vertex if the queued function returns true.
 0308                    continue;
 309                }
 310
 311                // add visit if not added yet.
 15312                if (neighbourPointer == uint.MaxValue)
 9313                {
 9314                    neighbourPointer = _tree.AddVisit(enumerator, currentPointer);
 9315                }
 316
 317                // add visit to heap.
 15318                _heap.Push(neighbourPointer, neighbourCost + currentCost + turnCost);
 15319            }
 22320        }
 321
 10322        var paths = new (Path? path, double cost)[targets.Count];
 52323        for (var p = 0; p < paths.Length; p++)
 16324        {
 16325            var bestTarget = bestTargets[p];
 16326            if (bestTarget.pointer == uint.MaxValue)
 1327            {
 1328                paths[p] = (null, double.MaxValue);
 1329                continue;
 330            }
 331
 332            // build resulting path.
 15333            var path = new Path(network);
 15334            var visit = _tree.GetVisit(bestTarget.pointer);
 335
 336            // path is at least two edges.
 31337            while (true)
 31338            {
 31339                if (visit.previousPointer == uint.MaxValue)
 15340                {
 15341                    path.Prepend(visit.edge, visit.forward);
 15342                    break;
 343                }
 344
 16345                path.Prepend(visit.edge, visit.forward);
 16346                visit = _tree.GetVisit(visit.previousPointer);
 16347            }
 348
 349            // add the offsets.
 15350            var target = targets[p];
 15351            path.Offset1 = path.First.direction ? source.Offset : (ushort)(ushort.MaxValue - source.Offset);
 15352            path.Offset2 = path.Last.direction
 15353                ? target.Offset
 15354                : (ushort)(ushort.MaxValue - target.Offset);
 355
 15356            paths[p] = (path, bestTarget.cost);
 15357        }
 358
 10359        return paths;
 10360    }
 361
 362    /// <summary>
 363    /// Gets a default dijkstra instance.
 364    /// </summary>
 365    public static Dijkstra Default
 366    {
 367        get
 10368        {
 10369            return new Dijkstra();
 10370        }
 371    }
 372}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

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