< 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:209
Uncovered lines:57
Coverable lines:266
Total lines:459
Line coverage:78.5% (209 of 266)
Covered branches:107
Total branches:138
Branch coverage:77.5% (107 of 138)
Tag:232_15462506344

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
RunAsync()0%20%
RunAsync()50%2100%
RunAsync()100%10%
RunAsync()78.12%12879.39%
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{
 1323    private readonly PathTree _tree = new();
 1324    private readonly HashSet<(EdgeId edgeId, VertexId vertexId)> _visits = new();
 1325    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,
 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)
 1147    {
 1148        var paths = await this.RunAsync(network, source, new[] { target }, getDijkstraWeight, settled, queued, cancellat
 49
 1150        return paths.Length < 1 ? (null, double.MaxValue) : paths[0];
 1151    }
 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)
 059    {
 060        return await this.RunAsync(network, (source, null), targets.Select(x => (x, (bool?)null)).ToArray(),
 061            getDijkstraWeight, settled, queued, cancellationToken);
 062    }
 63
 64    /// <summary>
 65    ///
 66    /// </summary>
 67    /// <param name="network"></param>
 68    /// <param name="source"></param>
 69    /// <param name="targets"></param>
 70    /// <param name="getDijkstraWeight"></param>
 71    /// <param name="settled">This Callback is called for every edge for which the minimal cost is known. If this callba
 72    /// <param name="queued">This callback is called before an edge is loaded. Should not be used to influence route pla
 73    /// <returns></returns>
 74    /// <exception cref="Exception"></exception>
 75    public async Task<(Path? path, double cost)[]> RunAsync(RoutingNetwork network,
 76        (SnapPoint sp, bool? direction) source,
 77        IReadOnlyList<(SnapPoint sp, bool? direction)> targets,
 78        DijkstraWeightFunc getDijkstraWeight,
 79        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? settled = null,
 80        Func<(EdgeId edgeId, VertexId vertexId), Task<bool>>? queued = null,
 81        CancellationToken cancellationToken = default)
 1382    {
 83        static double GetWorst((uint pointer, double cost)[] targets)
 2284        {
 2285            var worst = 0d;
 9086            for (var i = 0; i < targets.Length; i++)
 3487            {
 3488                if (!(targets[i].cost > worst))
 989                {
 990                    continue;
 91                }
 92
 2593                worst = targets[i].cost;
 2594                if (worst >= double.MaxValue)
 1195                {
 1196                    break;
 97                }
 1498            }
 99
 22100            return worst;
 22101        }
 102
 13103        var enumerator = network.GetEdgeEnumerator();
 104
 13105        _tree.Clear();
 13106        _visits.Clear();
 13107        _heap.Clear();
 108
 109        // add sources.
 13110        var sourceForwardVisit = uint.MaxValue;
 13111        if (source.Forward())
 13112        {
 113            // add forward.
 13114            if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0115            {
 0116                throw new Exception($"Edge in source {source} not found!");
 117            }
 118
 13119            var sourceCostForward =
 13120                getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost;
 13121            if (sourceCostForward > 0)
 13122            {
 123                // can traverse edge in the forward direction.
 13124                var sourceOffsetCostForward = sourceCostForward * (1 - source.sp.OffsetFactor());
 13125                sourceForwardVisit =
 13126                    _tree.AddVisit(enumerator, uint.MaxValue);
 13127                _heap.Push(sourceForwardVisit, sourceOffsetCostForward);
 13128            }
 13129        }
 130
 13131        var sourceBackwardVisit = uint.MaxValue;
 13132        if (source.Backward())
 8133        {
 134            // add backward.
 8135            if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0136            {
 0137                throw new Exception($"Edge in source {source} not found!");
 138            }
 139
 8140            var sourceCostBackward =
 8141                getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost;
 8142            if (sourceCostBackward > 0)
 8143            {
 144                // can traverse edge in the backward direction.
 8145                var sourceOffsetCostBackward = sourceCostBackward * source.sp.OffsetFactor();
 8146                sourceBackwardVisit =
 8147                    _tree.AddVisit(enumerator, uint.MaxValue);
 8148                _heap.Push(sourceBackwardVisit, sourceOffsetCostBackward);
 8149            }
 8150        }
 151
 152        // add targets.
 13153        var bestTargets = new (uint pointer, double cost)[targets.Count];
 13154        var targetsPerVertex = new Dictionary<VertexId, List<int>>();
 64155        for (var t = 0; t < targets.Count; t++)
 19156        {
 19157            bestTargets[t] = (uint.MaxValue, double.MaxValue);
 19158            var target = targets[t];
 159
 19160            if (target.Forward())
 16161            {
 162                // add forward.
 16163                if (!enumerator.MoveTo(target.sp.EdgeId, true))
 0164                {
 0165                    throw new Exception($"Edge in target {target} not found!");
 166                }
 167
 16168                var targetCostForward = getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>())
 16169                    .cost;
 16170                if (targetCostForward > 0)
 16171                {
 16172                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 10173                    {
 10174                        targetsAtVertex = new List<int>();
 10175                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 10176                    }
 177
 16178                    targetsAtVertex.Add(t);
 16179                }
 16180            }
 181
 19182            if (target.Backward())
 17183            {
 184                // add backward.
 17185                if (!enumerator.MoveTo(target.sp.EdgeId, false))
 0186                {
 0187                    throw new Exception($"Edge in source {source} not found!");
 188                }
 189
 17190                var targetCostBackward =
 17191                    getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost;
 17192                if (targetCostBackward > 0)
 17193                {
 17194                    if (!targetsPerVertex.TryGetValue(enumerator.Tail, out var targetsAtVertex))
 11195                    {
 11196                        targetsAtVertex = new List<int>();
 11197                        targetsPerVertex[enumerator.Tail] = targetsAtVertex;
 11198                    }
 199
 17200                    targetsAtVertex.Add(t);
 17201                }
 17202            }
 203
 204            // consider paths 'within' a single edge.
 19205            if (source.sp.EdgeId != target.sp.EdgeId)
 7206            {
 7207                continue;
 208            }
 209
 12210            if (source.sp.Offset == target.sp.Offset)
 1211            {
 212                // source and target are identical.
 1213                if (sourceForwardVisit != uint.MaxValue &&
 1214                    target.Forward())
 0215                {
 0216                    bestTargets[t] = (sourceForwardVisit, 0);
 0217                }
 1218                else if (sourceBackwardVisit != uint.MaxValue &&
 1219                         target.Backward())
 0220                {
 0221                    bestTargets[t] = (sourceForwardVisit, 0);
 0222                }
 1223            }
 11224            else if (source.sp.Offset < target.sp.Offset &&
 11225                     source.Forward() && target.Forward())
 8226            {
 227                // the source is earlier in the direction of the edge
 228                // and the edge can be traversed in this direction.
 8229                if (!enumerator.MoveTo(source.sp.EdgeId, true))
 0230                {
 0231                    throw new Exception($"Edge in source {source} not found!");
 232                }
 233
 8234                var weight = getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost *
 8235                             (target.sp.OffsetFactor() - source.sp.OffsetFactor());
 8236                bestTargets[t] = (sourceForwardVisit, weight);
 8237            }
 3238            else if (source.sp.Offset > target.sp.Offset &&
 3239                     source.Backward() && target.Backward())
 0240            {
 241                // the source is earlier against the direction of the edge
 242                // and the edge can be traversed in this direction.
 0243                if (!enumerator.MoveTo(source.sp.EdgeId, false))
 0244                {
 0245                    throw new Exception($"Edge in source {source} not found!");
 246                }
 247
 0248                var weight = getDijkstraWeight(enumerator, Enumerable.Empty<(EdgeId edge, byte? turn)>()).cost *
 0249                             (source.sp.OffsetFactor() - target.sp.OffsetFactor());
 0250                bestTargets[t] = (sourceBackwardVisit, weight);
 0251            }
 12252        }
 253
 254        // update worst target cost.
 13255        var worstTargetCost = GetWorst(bestTargets);
 256
 257        // keep going until heap is empty.
 46258        while (_heap.Count > 0)
 37259        {
 37260            cancellationToken.ThrowIfCancellationRequested();
 261
 262            // dequeue new visit.
 37263            var currentPointer = _heap.Pop(out var currentCost);
 37264            var currentVisit = _tree.GetVisit(currentPointer);
 37265            while (_visits.Contains((currentVisit.edge, currentVisit.vertex)))
 0266            {
 267                // visited before, skip.
 0268                currentPointer = uint.MaxValue;
 0269                if (_heap.Count == 0)
 0270                {
 0271                    break;
 272                }
 273
 0274                currentPointer = _heap.Pop(out currentCost);
 0275                currentVisit = _tree.GetVisit(currentPointer);
 0276            }
 277
 37278            if (currentPointer == uint.MaxValue)
 0279            {
 0280                break;
 281            }
 282
 283            // log visit.
 37284            if (currentVisit.previousPointer != uint.MaxValue)
 16285            {
 16286                _visits.Add((currentVisit.edge, currentVisit.vertex));
 16287            }
 288
 37289            if (settled != null && await settled((currentVisit.edge, currentVisit.vertex)))
 0290            {
 291                // the best cost to this edge has already been found; current visit can not improve this anymore so we c
 0292                continue;
 293            }
 294
 295            // check if the search needs to stop.
 37296            if (currentCost > worstTargetCost)
 4297            {
 298                // impossible to improve on cost to any target.
 4299                break;
 300            }
 301
 302            // check neighbours.
 33303            if (!enumerator.MoveTo(currentVisit.vertex))
 0304            {
 305                // no edges, move on!
 0306                continue;
 307            }
 308
 309            // check if this is a target.
 33310            if (!targetsPerVertex.TryGetValue(currentVisit.vertex, out var targetsAtVertex))
 13311            {
 13312                targetsAtVertex = null;
 13313            }
 314
 85315            while (enumerator.MoveNext())
 52316            {
 317                // filter out if u-turns or visits on the same edge.
 52318                var neighbourEdge = enumerator.EdgeId;
 52319                if (neighbourEdge == currentVisit.edge)
 33320                {
 33321                    continue;
 322                }
 323
 324                // gets the cost of the current edge.
 19325                var (neighbourCost, turnCost) =
 19326                    getDijkstraWeight(enumerator, _tree.GetPreviousEdges(currentPointer));
 19327                if (neighbourCost is >= double.MaxValue or <= 0)
 0328                {
 0329                    continue;
 330                }
 331
 19332                if (turnCost is >= double.MaxValue or < 0)
 1333                {
 1334                    continue;
 335                }
 336
 337                // if the vertex has targets, check if this edge is a match.
 18338                var neighbourPointer = uint.MaxValue;
 18339                if (targetsAtVertex != null)
 10340                {
 341                    // only consider targets when found for the 'from' vertex.
 342                    // and when this in not a u-turn.
 56343                    foreach (var t in targetsAtVertex)
 13344                    {
 13345                        var target = targets[t];
 13346                        if (target.sp.EdgeId != neighbourEdge)
 4347                        {
 4348                            continue;
 349                        }
 350
 351                        // check directions.
 9352                        if (enumerator.Forward && !target.Forward())
 0353                        {
 0354                            continue;
 355                        }
 356
 9357                        if (!enumerator.Forward && !target.Backward())
 0358                        {
 0359                            continue;
 360                        }
 361
 362                        // there is a target on this edge, calculate the cost.
 363                        // calculate the cost from the 'from' vertex to the target.
 9364                        var targetCost = enumerator.Forward
 9365                            ? neighbourCost * target.sp.OffsetFactor()
 9366                            : neighbourCost * (1 - target.sp.OffsetFactor());
 367                        // this is the case where the target is on this edge
 368                        // and there is a path to 'from' before.
 9369                        targetCost += currentCost;
 370
 9371                        targetCost += turnCost;
 372
 373                        // if this is an improvement, use it!
 9374                        var targetBestCost = bestTargets[t].cost;
 9375                        if (!(targetCost < targetBestCost))
 0376                        {
 0377                            continue;
 378                        }
 379
 380                        // this is an improvement.
 9381                        neighbourPointer = _tree.AddVisit(enumerator, currentPointer);
 9382                        bestTargets[t] = (neighbourPointer, targetCost);
 383
 384                        // update worst.
 9385                        worstTargetCost = GetWorst(bestTargets);
 9386                    }
 10387                }
 388
 18389                if (queued != null &&
 18390                    await queued((enumerator.EdgeId, enumerator.Head)))
 0391                {
 392                    // don't queue this edge if the queued function returns true.
 0393                    continue;
 394                }
 395
 396                // add visit if not added yet.
 18397                if (neighbourPointer == uint.MaxValue)
 12398                {
 12399                    neighbourPointer =
 12400                        _tree.AddVisit(enumerator, currentPointer);
 12401                }
 402
 403                // add visit to heap.
 18404                _heap.Push(neighbourPointer, neighbourCost + currentCost + turnCost);
 18405            }
 33406        }
 407
 13408        var paths = new (Path? path, double cost)[targets.Count];
 64409        for (var p = 0; p < paths.Length; p++)
 19410        {
 19411            var bestTarget = bestTargets[p];
 19412            if (bestTarget.pointer == uint.MaxValue)
 3413            {
 3414                paths[p] = (null, double.MaxValue);
 3415                continue;
 416            }
 417
 418            // build resulting path.
 16419            var path = new Path(network);
 16420            var visit = _tree.GetVisit(bestTarget.pointer);
 421
 422            // path is at least two edges.
 34423            while (true)
 34424            {
 34425                if (visit.previousPointer == uint.MaxValue)
 16426                {
 16427                    enumerator.MoveTo(visit.edge);
 16428                    path.Prepend(visit.edge, visit.forward);
 16429                    break;
 430                }
 431
 18432                path.Prepend(visit.edge, visit.forward);
 18433                visit = _tree.GetVisit(visit.previousPointer);
 18434            }
 435
 436            // add the offsets.
 16437            var target = targets[p];
 16438            path.Offset1 = path.First.direction ? source.sp.Offset : (ushort)(ushort.MaxValue - source.sp.Offset);
 16439            path.Offset2 = path.Last.direction
 16440                ? target.sp.Offset
 16441                : (ushort)(ushort.MaxValue - target.sp.Offset);
 442
 16443            paths[p] = (path, bestTarget.cost);
 16444        }
 445
 13446        return paths;
 13447    }
 448
 449    /// <summary>
 450    /// Gets a default dijkstra instance.
 451    /// </summary>
 452    public static Dijkstra Default
 453    {
 454        get
 13455        {
 13456            return new Dijkstra();
 13457        }
 458    }
 459}
Generated by: ReportGenerator 4.8.2.0
06/05/2025 - 08:42:07
GitHub | www.palmmedia.de

Methods/Properties

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