< Summary

Class:Itinero.Routing.Flavours.Dijkstra.Bidirectional.DijkstraAlgorithm
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/DijkstraAlgorithm.cs
Covered lines:94
Uncovered lines:1
Coverable lines:95
Total lines:181
Line coverage:98.9% (94 of 95)
Covered branches:49
Total branches:58
Branch coverage:84.4% (49 of 58)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
get_RoutingNetwork()100%1100%
TryGetVisit(...)100%1100%
Clear()100%1100%
GetVisit(...)100%1100%
Push(...)50%2100%
Pop()100%6100%
GetPreviousEdges()75%4100%
CanTurn(...)79.16%2496.29%
Step(...)90.9%22100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/DijkstraAlgorithm.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using Itinero.Network;
 5using Itinero.Network.Enumerators.Edges;
 6using Itinero.Routing.DataStructures;
 7
 8namespace Itinero.Routing.Flavours.Dijkstra.Bidirectional;
 9
 10internal abstract class DijkstraAlgorithm
 11{
 5412    private readonly PathTree _tree = new();
 5413    private readonly Dictionary<VertexId, (uint p, double cost)> _settled = [];
 5414    private readonly BinaryHeap<(uint pointer, VertexId vertex)> _heap = new();
 15    protected readonly RoutingNetworkEdgeEnumerator _enumerator;
 16    protected readonly RoutingNetwork _network;
 17
 5418    protected DijkstraAlgorithm(RoutingNetwork network)
 5419    {
 5420        _network = network;
 21
 5422        _enumerator = network.GetEdgeEnumerator();
 5423    }
 24
 13625    internal RoutingNetwork RoutingNetwork => _network;
 26
 27    protected abstract bool OnQueued(uint visit, EdgeId edge, (double cost, double turnCost) edgeCost, VertexId vertex, 
 28
 29    protected abstract bool OnSettled(uint visit, VertexId vertex, double cost);
 30
 31    protected abstract (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator,
 32        PreviousEdgeEnumerable previousEdges);
 33
 34    protected abstract (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator,
 35        IEnumerable<(EdgeId edge, byte? turn)> previousEdges);
 36
 37    internal bool TryGetVisit(VertexId vertex, out (uint p, double cost) visit)
 193638    {
 193639        return _settled.TryGetValue(vertex, out visit);
 193640    }
 41
 42    internal void Clear()
 11843    {
 11844        _heap.Clear();
 11845        _tree.Clear();
 11846        _settled.Clear();
 11847    }
 48
 49    internal (VertexId vertex, EdgeId edge, bool forward, byte? head, uint previousPointer) GetVisit(uint pointer)
 12950    {
 12951        return _tree.GetVisit(pointer);
 12952    }
 53
 54    internal uint Push(EdgeId edgeId, bool forward, double cost)
 19855    {
 19856        if (!_enumerator.MoveTo(edgeId, forward)) throw new Exception($"Edge not found!");
 57
 19858        var v = _tree.AddVisit(_enumerator, uint.MaxValue);
 19859        _heap.Push((v, _enumerator.Head), cost);
 19860        return v;
 19861    }
 62
 63    internal (uint pointer, (VertexId vertex, EdgeId edge, bool forward, byte? head, uint previousPointer) visit, double
 62464    {
 62465        var currentEntry = _heap.Pop(out var currentCost);
 125866        while (!_settled.TryAdd(currentEntry.vertex, (currentEntry.pointer, currentCost)))
 64067        {
 64068            if (_heap.Count == 0)
 669            {
 670                currentEntry = (uint.MaxValue, default);
 671                break;
 72            }
 73
 63474            currentEntry = _heap.Pop(out currentCost);
 63475        }
 76
 62477        if (currentEntry.pointer == uint.MaxValue)
 678        {
 679            return (uint.MaxValue, default, currentCost);
 80        }
 81
 82        // only call GetVisit after the settled check passes.
 61883        var currentVisit = _tree.GetVisit(currentEntry.pointer);
 61884        return (currentEntry.pointer, currentVisit, currentCost);
 62485    }
 86
 87    internal IEnumerable<(EdgeId edge, byte? turn)> GetPreviousEdges(uint pointer, int maxCount = 16)
 3088    {
 3089        using var previous = _tree.GetPreviousEdges(pointer).GetEnumerator();
 6590        while (previous.MoveNext())
 3591        {
 3592            if (maxCount <= 0) yield break;
 3593            maxCount--;
 94
 3595            yield return previous.Current;
 3596        }
 3097    }
 98
 99    internal bool CanTurn(VertexId vertex,
 100        IReadOnlyList<(EdgeId edge, byte? turn)> previousEdges, IReadOnlyList<EdgeId> nextEdges)
 15101    {
 15102        if (nextEdges.Count == 0) throw new Exception("Not a turn");
 15103        if (previousEdges.Count == 0) throw new Exception("Not a turn");
 104
 105        // no U-turns
 16106        if (nextEdges[0] == previousEdges[0].edge) return false;
 107
 108        // check neighbours.
 14109        var nextChecked = 0;
 14110        var edges = previousEdges.ToList();
 20111        while (nextChecked < nextEdges.Count)
 14112        {
 14113            var nextEdge = nextEdges[nextChecked];
 14114            var edgeFound = false;
 115
 14116            if (!_enumerator.MoveTo(vertex)) return false;
 16117            while (_enumerator.MoveNext())
 16118            {
 119                // filter out if U-turns or visits on the same edge.
 16120                var neighbourEdge = _enumerator.EdgeId;
 18121                if (neighbourEdge != nextEdge) continue;
 122
 123                // gets the cost of the current edge.
 14124                var (_, turnCost) = this.GetCost(_enumerator, edges);
 125
 22126                if (turnCost is >= double.MaxValue or < 0) return false;
 127
 6128                edges.Add((_enumerator.EdgeId, _enumerator.HeadOrder));
 6129                vertex = _enumerator.Head;
 6130                edgeFound = true;
 6131                break;
 132            }
 133
 6134            if (!edgeFound) return false;
 135
 6136            nextChecked++;
 6137        }
 138
 139        // if all edges are checked, the turn is possible.
 12140        if (nextChecked >= nextEdges.Count) return true;
 141
 142        // target edge not found as neighbour.
 0143        return false;
 15144    }
 145
 146    internal bool Step(uint pointer, (VertexId vertex, EdgeId edge, bool forward, byte? head, uint previousPointer) visi
 618147    {
 148        // log settled and see if we need to continue.
 618149        if (!this.OnSettled(pointer, visit.vertex, cost)) return false;
 150
 151        // check neighbours.
 618152        if (!_enumerator.MoveTo(visit.vertex)) return true;
 2673153        while (_enumerator.MoveNext())
 2055154        {
 155            // filter out if U-turns or visits on the same edge.
 2055156            var neighbourEdge = _enumerator.EdgeId;
 2673157            if (neighbourEdge == visit.edge) continue;
 158
 159            // gets the cost of the current edge.
 1437160            var (neighbourCost, turnCost) = this.GetCost(_enumerator, new PreviousEdgeEnumerable(_tree, pointer));
 161
 162            // ignore if cost is 0 or infinite.
 1541163            if (neighbourCost is >= double.MaxValue or <= 0) continue;
 1348164            if (turnCost is >= double.MaxValue or < 0) continue;
 165
 166            // check if the vertex has to be queued.
 1318167            var totalCost = neighbourCost + cost + turnCost;
 168
 169            // add visit if not added yet.
 1318170            var neighbourPointer = _tree.AddVisit(_enumerator, pointer);
 171
 172            // call the on queued method and allow checking for stopping conditions.
 1318173            if (!this.OnQueued(neighbourPointer, _enumerator.EdgeId, (neighbourCost, turnCost), _enumerator.Head, totalC
 174
 175            // add visit to heap.
 1318176            _heap.Push((neighbourPointer, _enumerator.Head), totalCost);
 1318177        }
 178
 618179        return true;
 618180    }
 181}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
get_RoutingNetwork()
TryGetVisit(...)
Clear()
GetVisit(...)
Push(...)
Pop()
GetPreviousEdges()
CanTurn(...)
Step(...)