< 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:218
Uncovered lines:47
Coverable lines:265
Total lines:453
Line coverage:82.2% (218 of 265)
Covered branches:111
Total branches:138
Branch coverage:80.4% (111 of 138)
Tag:224_14471318300

Metrics

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

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{
 2023    private readonly PathTree _tree = new();
 2024    private readonly HashSet<(EdgeId edgeId, VertexId vertexId)> _visits = new();
 2025    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,
 30        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 31        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null)
 032    {
 033        var paths = await this.RunAsync(network, (source, null), new[] { (target, (bool?)null) }, getDijkstraWeight,
 034            settled, queued);
 35
 036        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 037    }
 38
 39    public async Task<(Path? path, double cost)> RunAsync(RoutingNetwork network,
 40        (SnapPoint sp, bool? direction) source,
 41        (SnapPoint sp, bool? direction) target,
 42        DijkstraWeightFunc getDijkstraWeight,
 43        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 44        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null)
 1145    {
 1146        var paths = await this.RunAsync(network, source, new[] { target }, getDijkstraWeight, settled, queued);
 47
 1148        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 1149    }
 50
 51    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network, SnapPoint source,
 52        IReadOnlyList<SnapPoint> targets,
 53        DijkstraWeightFunc getDijkstraWeight,
 54        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 55        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null)
 756    {
 1457        return await this.RunAsync(network, (source, null), targets.Select(x => (x, (bool?)null)).ToArray(),
 758            getDijkstraWeight, settled, queued);
 759    }
 60
 61    /// <summary>
 62    ///
 63    /// </summary>
 64    /// <param name="network"></param>
 65    /// <param name="source"></param>
 66    /// <param name="targets"></param>
 67    /// <param name="getDijkstraWeight"></param>
 68    /// <param name="settled">This Callback is called for every edge for which the minimal cost is known. If this callba
 69    /// <param name="queued">This callback is called before an edge is loaded. Should not be used to influence route pla
 70    /// <returns></returns>
 71    /// <exception cref="Exception"></exception>
 72    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network,
 73        (SnapPoint sp, bool? direction) source,
 74        IReadOnlyList<(SnapPoint sp, bool? direction)> targets,
 75        DijkstraWeightFunc getDijkstraWeight,
 76        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 77        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null)
 2078    {
 79        static double GetWorst((uint pointer, double cost)[] targets)
 3080        {
 3081            var worst = 0d;
 12082            for (var i = 0; i < targets.Length; i++)
 4283            {
 4284                if (!(targets[i].cost > worst))
 985                {
 986                    continue;
 87                }
 88
 3389                worst = targets[i].cost;
 3390                if (worst >= double.MaxValue)
 1291                {
 1292                    break;
 93                }
 2194            }
 95
 3096            return worst;
 3097        }
 98
 2099        var enumerator = network.GetEdgeEnumerator();
 100
 20101        _tree.Clear();
 20102        _visits.Clear();
 20103        _heap.Clear();
 104
 105        // add sources.
 20106        var sourceForwardVisit = uint.MaxValue;
 20107        if (source.Forward())
 20108        {
 109            // add forward.
 20110            if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0111            {
 0112                throw new Exception($"Edge in source {source} not found!");
 113            }
 114
 20115            var sourceCostForward =
 20116                getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost;
 20117            if (sourceCostForward > 0)
 20118            {
 119                // can traverse edge in the forward direction.
 20120                var sourceOffsetCostForward = sourceCostForward * (1 - source.sp.OffsetFactor());
 20121                sourceForwardVisit =
 20122                    _tree.AddVisit(enumerator, uint.MaxValue);
 20123                _heap.Push(sourceForwardVisit, sourceOffsetCostForward);
 20124            }
 20125        }
 126
 20127        var sourceBackwardVisit = uint.MaxValue;
 20128        if (source.Backward())
 15129        {
 130            // add backward.
 15131            if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0132            {
 0133                throw new Exception($"Edge in source {source} not found!");
 134            }
 135
 15136            var sourceCostBackward =
 15137                getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost;
 15138            if (sourceCostBackward > 0)
 15139            {
 140                // can traverse edge in the backward direction.
 15141                var sourceOffsetCostBackward = sourceCostBackward * source.sp.OffsetFactor();
 15142                sourceBackwardVisit =
 15143                    _tree.AddVisit(enumerator, uint.MaxValue);
 15144                _heap.Push(sourceBackwardVisit, sourceOffsetCostBackward);
 15145            }
 15146        }
 147
 148        // add targets.
 20149        var bestTargets = new (uint pointer, double cost)[targets.Count];
 20150        var targetsPerVertex = new Dictionary<VertexId, List<int>>();
 92151        for (var t = 0; t < targets.Count; t++)
 26152        {
 26153            bestTargets[t] = (uint.MaxValue, double.MaxValue);
 26154            var target = targets[t];
 155
 26156            if (target.Forward())
 23157            {
 158                // add forward.
 23159                if (!enumerator.MoveTo(target.sp.EdgeId, true))
 0160                {
 0161                    throw new Exception($"Edge in target {target} not found!");
 162                }
 163
 23164                var targetCostForward = getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>())
 23165                    .cost;
 23166                if (targetCostForward > 0)
 23167                {
 23168                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 17169                    {
 17170                        targetsAtVertex = new List<int>();
 17171                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 17172                    }
 173
 23174                    targetsAtVertex.Add(t);
 23175                }
 23176            }
 177
 26178            if (target.Backward())
 24179            {
 180                // add backward.
 24181                if (!enumerator.MoveTo(target.sp.EdgeId, false))
 0182                {
 0183                    throw new Exception($"Edge in source {source} not found!");
 184                }
 185
 24186                var targetCostBackward =
 24187                    getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost;
 24188                if (targetCostBackward > 0)
 24189                {
 24190                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 18191                    {
 18192                        targetsAtVertex = new List<int>();
 18193                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 18194                    }
 195
 24196                    targetsAtVertex.Add(t);
 24197                }
 24198            }
 199
 200            // consider paths 'within' a single edge.
 26201            if (source.sp.EdgeId != target.sp.EdgeId)
 8202            {
 8203                continue;
 204            }
 205
 18206            if (source.sp.Offset == target.sp.Offset)
 1207            {
 208                // source and target are identical.
 1209                if (sourceForwardVisit != uint.MaxValue &&
 1210                    target.Forward())
 0211                {
 0212                    bestTargets[t] = (sourceForwardVisit, 0);
 0213                }
 1214                else if (sourceBackwardVisit != uint.MaxValue &&
 1215                         target.Backward())
 0216                {
 0217                    bestTargets[t] = (sourceForwardVisit, 0);
 0218                }
 1219            }
 17220            else if (source.sp.Offset < target.sp.Offset &&
 17221                     source.Forward() && target.Forward())
 11222            {
 223                // the source is earlier in the direction of the edge
 224                // and the edge can be traversed in this direction.
 11225                if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0226                {
 0227                    throw new Exception($"Edge in source {source} not found!");
 228                }
 229
 11230                var weight = getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost *
 11231                             (target.sp.OffsetFactor() - source.sp.OffsetFactor());
 11232                bestTargets[t] = (sourceForwardVisit, weight);
 11233            }
 6234            else if (source.sp.Offset > target.sp.Offset &&
 6235                     source.Backward() && target.Backward())
 3236            {
 237                // the source is earlier against the direction of the edge
 238                // and the edge can be traversed in this direction.
 3239                if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0240                {
 0241                    throw new Exception($"Edge in source {source} not found!");
 242                }
 243
 3244                var weight = getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost *
 3245                             (source.sp.OffsetFactor() - target.sp.OffsetFactor());
 3246                bestTargets[t] = (sourceBackwardVisit, weight);
 3247            }
 18248        }
 249
 250        // update worst target cost.
 20251        var worstTargetCost = GetWorst(bestTargets);
 252
 253        // keep going until heap is empty.
 68254        while (_heap.Count > 0)
 52255        {
 256            // dequeue new visit.
 52257            var currentPointer = _heap.Pop(out var currentCost);
 52258            var currentVisit = _tree.GetVisit(currentPointer);
 52259            while (_visits.Contains((currentVisit.edge, currentVisit.vertex)))
 0260            {
 261                // visited before, skip.
 0262                currentPointer = uint.MaxValue;
 0263                if (_heap.Count == 0)
 0264                {
 0265                    break;
 266                }
 267
 0268                currentPointer = _heap.Pop(out currentCost);
 0269                currentVisit = _tree.GetVisit(currentPointer);
 0270            }
 271
 52272            if (currentPointer == uint.MaxValue)
 0273            {
 0274                break;
 275            }
 276
 277            // log visit.
 52278            if (currentVisit.previousPointer != uint.MaxValue)
 17279            {
 17280                _visits.Add((currentVisit.edge, currentVisit.vertex));
 17281            }
 282
 52283            if (settled != null && await settled((currentVisit.edge, currentVisit.vertex)))
 0284            {
 285                // the best cost to this edge has already been found; current visit can not improve this anymore so we c
 0286                continue;
 287            }
 288
 289            // check if the search needs to stop.
 52290            if (currentCost > worstTargetCost)
 4291            {
 292                // impossible to improve on cost to any target.
 4293                break;
 294            }
 295
 296            // check neighbours.
 48297            if (!enumerator.MoveTo(currentVisit.vertex))
 0298            {
 299                // no edges, move on!
 0300                continue;
 301            }
 302
 303            // check if this is a target.
 48304            if (!targetsPerVertex.TryGetValue(currentVisit.vertex, out var targetsAtVertex))
 14305            {
 14306                targetsAtVertex = null;
 14307            }
 308
 116309            while (enumerator.MoveNext())
 68310            {
 311                // filter out if u-turns or visits on the same edge.
 68312                var neighbourEdge = enumerator.EdgeId;
 68313                if (neighbourEdge == currentVisit.edge)
 48314                {
 48315                    continue;
 316                }
 317
 318                // gets the cost of the current edge.
 20319                var (neighbourCost, turnCost) =
 20320                    getDijkstraWeight(enumerator, _tree.GetPreviousEdges(currentPointer));
 20321                if (neighbourCost is >= double.MaxValue or <= 0)
 0322                {
 0323                    continue;
 324                }
 325
 20326                if (turnCost is >= double.MaxValue or < 0)
 1327                {
 1328                    continue;
 329                }
 330
 331                // if the vertex has targets, check if this edge is a match.
 19332                var neighbourPointer = uint.MaxValue;
 19333                if (targetsAtVertex != null)
 11334                {
 335                    // only consider targets when found for the 'from' vertex.
 336                    // and when this in not a u-turn.
 61337                    foreach (var t in targetsAtVertex)
 14338                    {
 14339                        var target = targets[t];
 14340                        if (target.sp.EdgeId != neighbourEdge)
 4341                        {
 4342                            continue;
 343                        }
 344
 345                        // check directions.
 10346                        if (enumerator.Forward && !target.Forward())
 0347                        {
 0348                            continue;
 349                        }
 350
 10351                        if (!enumerator.Forward && !target.Backward())
 0352                        {
 0353                            continue;
 354                        }
 355
 356                        // there is a target on this edge, calculate the cost.
 357                        // calculate the cost from the 'from' vertex to the target.
 10358                        var targetCost = enumerator.Forward
 10359                            ? neighbourCost * target.sp.OffsetFactor()
 10360                            : neighbourCost * (1 - target.sp.OffsetFactor());
 361                        // this is the case where the target is on this edge
 362                        // and there is a path to 'from' before.
 10363                        targetCost += currentCost;
 364
 10365                        targetCost += turnCost;
 366
 367                        // if this is an improvement, use it!
 10368                        var targetBestCost = bestTargets[t].cost;
 10369                        if (!(targetCost < targetBestCost))
 0370                        {
 0371                            continue;
 372                        }
 373
 374                        // this is an improvement.
 10375                        neighbourPointer = _tree.AddVisit(enumerator, currentPointer);
 10376                        bestTargets[t] = (neighbourPointer, targetCost);
 377
 378                        // update worst.
 10379                        worstTargetCost = GetWorst(bestTargets);
 10380                    }
 11381                }
 382
 19383                if (queued != null &&
 19384                    await queued((enumerator.EdgeId, enumerator.Head)))
 0385                {
 386                    // don't queue this edge if the queued function returns true.
 0387                    continue;
 388                }
 389
 390                // add visit if not added yet.
 19391                if (neighbourPointer == uint.MaxValue)
 12392                {
 12393                    neighbourPointer =
 12394                        _tree.AddVisit(enumerator, currentPointer);
 12395                }
 396
 397                // add visit to heap.
 19398                _heap.Push(neighbourPointer, neighbourCost + currentCost + turnCost);
 19399            }
 48400        }
 401
 20402        var paths = new (Path? path, double cost)[targets.Count];
 92403        for (var p = 0; p < paths.Length; p++)
 26404        {
 26405            var bestTarget = bestTargets[p];
 26406            if (bestTarget.pointer == uint.MaxValue)
 3407            {
 3408                paths[p] = (null, double.MaxValue);
 3409                continue;
 410            }
 411
 412            // build resulting path.
 23413            var path = new Path(network);
 23414            var visit = _tree.GetVisit(bestTarget.pointer);
 415
 416            // path is at least two edges.
 42417            while (true)
 42418            {
 42419                if (visit.previousPointer == uint.MaxValue)
 23420                {
 23421                    enumerator.MoveTo(visit.edge);
 23422                    path.Prepend(visit.edge, visit.forward);
 23423                    break;
 424                }
 425
 19426                path.Prepend(visit.edge, visit.forward);
 19427                visit = _tree.GetVisit(visit.previousPointer);
 19428            }
 429
 430            // add the offsets.
 23431            var target = targets[p];
 23432            path.Offset1 = path.First.direction ? source.sp.Offset : (ushort)(ushort.MaxValue - source.sp.Offset);
 23433            path.Offset2 = path.Last.direction
 23434                ? target.sp.Offset
 23435                : (ushort)(ushort.MaxValue - target.sp.Offset);
 436
 23437            paths[p] = (path, bestTarget.cost);
 23438        }
 439
 20440        return paths;
 20441    }
 442
 443    /// <summary>
 444    /// Gets a default dijkstra instance.
 445    /// </summary>
 446    public static Dijkstra Default
 447    {
 448        get
 20449        {
 20450            return new Dijkstra();
 20451        }
 452    }
 453}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

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