< Summary

Class:Itinero.Routing.Flavours.Dijkstra.Bidirectional.BidirectionalDijkstra
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/BidirectionalDijkstra.cs
Covered lines:145
Uncovered lines:6
Coverable lines:151
Total lines:244
Line coverage:96% (145 of 151)
Covered branches:58
Total branches:64
Branch coverage:90.6% (58 of 64)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
ForNetwork(...)100%4100%
RunAsync()90.9%4496%
CanTurn(...)50%4100%
.ctor(...)100%1100%
OnQueued(...)100%6100%
OnSettled(...)100%1100%
GetCost(...)100%1100%
GetCost(...)100%1100%
.ctor(...)100%1100%
OnQueued(...)100%6100%
OnSettled(...)100%1100%
GetCost(...)100%1100%
GetCost(...)100%10%

File(s)

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

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using System.Threading;
 5using System.Threading.Tasks;
 6using Itinero.Network;
 7using Itinero.Network.Enumerators.Edges;
 8using Itinero.Routes.Paths;
 9using Itinero.Routing.Costs;
 10using Itinero.Snapping;
 11
 12namespace Itinero.Routing.Flavours.Dijkstra.Bidirectional;
 13
 14
 15internal class BidirectionalDijkstra
 16{
 17    private readonly RoutingNetwork _routingNetwork;
 18    private readonly BidirectionalDijkstraForward _forward;
 19    private readonly BidirectionalDijkstraBackward _backward;
 20    private ICostFunction _costFunction;
 21    internal (uint forward, uint backward, double cost, Path? singleHopPath) _best;
 22
 2723    internal BidirectionalDijkstra(RoutingNetwork routingNetwork)
 2724    {
 2725        _routingNetwork = routingNetwork;
 26
 2727        _backward = new BidirectionalDijkstraBackward(this);
 2728        _forward = new BidirectionalDijkstraForward(this);
 2729    }
 30
 31    [ThreadStatic]
 32    private static BidirectionalDijkstra? _cached;
 33
 34    public static BidirectionalDijkstra ForNetwork(RoutingNetwork routingNetwork)
 5935    {
 5936        var cached = _cached;
 5937        if (cached != null && cached._routingNetwork == routingNetwork)
 3238        {
 3239            return cached;
 40        }
 41
 2742        cached = new BidirectionalDijkstra(routingNetwork);
 2743        _cached = cached;
 2744        return cached;
 5945    }
 46
 47    public async Task<(Path? path, double cost)> RunAsync(SnapPoint origin,
 48        SnapPoint destination, ICostFunction costFunction, Func<VertexId, Task<bool>>? settled = null,
 49        Func<VertexId, Task<bool>>? queued = null, CancellationToken cancellationToken = default)
 5950    {
 5951        _costFunction = costFunction;
 52
 5953        _forward.Clear();
 5954        _backward.Clear();
 55
 5956        _best = (uint.MaxValue, uint.MaxValue, double.MaxValue, null);
 5957        if (_routingNetwork.TrySingleHop(origin, destination, costFunction, out var singleHopPath, out var singleHopCost
 4758        {
 4759            _best = (uint.MaxValue, uint.MaxValue, singleHopCost, singleHopPath);
 4760        }
 61
 5962        _backward.Push(costFunction, destination, false);
 5963        _forward.Push(costFunction, origin, true);
 64
 5965        var forwardDone = false;
 5966        var backwardDone = false;
 5967        var forwardCost = 0d;
 5968        var backwardCost = 0d;
 31569        while (!forwardDone || !backwardDone)
 31270        {
 31271            cancellationToken.ThrowIfCancellationRequested();
 72
 31273            if (!forwardDone)
 31274            {
 31275                var (p, v, c) = _forward.Pop();
 31276                forwardCost = c;
 31277                if (p != uint.MaxValue)
 30978                {
 30979                    if (_backward.TryGetVisit(v.vertex, out var backwardVisit))
 2180                    {
 2181                        var cost = c + backwardVisit.cost;
 2182                        if (cost < _best.cost &&
 2183                            this.CanTurn(p, backwardVisit.p))
 084                        {
 085                            _best = (p, backwardVisit.p, cost, null);
 086                        }
 2187                    }
 88
 61389                    if (settled != null) await settled(v.vertex);
 90
 30991                    if (!_forward.Step(p, v, c)) forwardDone = true;
 30992                }
 93                else
 394                {
 395                    forwardDone = true;
 396                }
 31297            }
 31298            if (!backwardDone)
 31299            {
 312100                var (p, v, c) = _backward.Pop();
 312101                backwardCost = c;
 312102                if (p != uint.MaxValue)
 309103                {
 309104                    if (_forward.TryGetVisit(v.vertex, out var forwardVisit))
 66105                    {
 66106                        var cost = c + forwardVisit.cost;
 66107                        if (cost < _best.cost &&
 66108                            this.CanTurn(forwardVisit.p, p))
 6109                        {
 6110                            _best = (forwardVisit.p, p, cost, null);
 6111                        }
 66112                    }
 113
 613114                    if (settled != null) await settled(v.vertex);
 115
 309116                    if (!_backward.Step(p, v, c)) backwardDone = true;
 309117                }
 118                else
 3119                {
 3120                    backwardDone = true;
 3121                }
 312122            }
 123
 368124            if (_best.cost < (forwardCost + backwardCost)) break;
 256125        }
 126
 62127        if (_best.cost >= double.MaxValue) return (null, double.MaxValue);
 103128        if (_best.forward == uint.MaxValue) return (_best.singleHopPath, _best.cost);
 129
 9130        var forwardPath = _forward.GetPathToVisit(_best.forward);
 9131        var backwardPath = _backward.GetPathToVisit(_best.backward);
 9132        forwardPath.Append(backwardPath.InvertDirection());
 133
 9134        forwardPath.Offset1 = forwardPath.First.direction ? origin.Offset : (ushort)(ushort.MaxValue - origin.Offset);
 9135        forwardPath.Offset2 = forwardPath.Last.direction
 9136            ? destination.Offset
 9137            : (ushort)(ushort.MaxValue - destination.Offset);
 138
 9139        return (forwardPath, _best.cost);
 59140    }
 141
 142    private bool CanTurn(uint forwardPointer, uint backwardPointer)
 15143    {
 15144        var (vertex, _, _, _, _) = _forward.GetVisit(forwardPointer);
 15145        var forwardPrevious = _forward.GetPreviousEdges(forwardPointer).ToList();
 15146        if (forwardPrevious.Count == 0) return true; // not a turn.
 15147        var backwardPrevious = _backward.GetPreviousEdges(backwardPointer)
 32148            .Select(x => x.edge).ToList();
 15149        if (backwardPrevious.Count == 0) return true; // not a turn.
 15150        return _forward.CanTurn(vertex, forwardPrevious, backwardPrevious);
 15151    }
 152
 153    internal class BidirectionalDijkstraForward : DijkstraAlgorithm
 154    {
 155        private readonly BidirectionalDijkstra _bidirectionalDijkstra;
 156
 157        internal BidirectionalDijkstraForward(BidirectionalDijkstra bidirectionalDijkstra)
 27158            : base(bidirectionalDijkstra._routingNetwork)
 27159        {
 27160            _bidirectionalDijkstra = bidirectionalDijkstra;
 27161        }
 162
 163
 164        protected override bool OnQueued(uint visit, EdgeId edge, (double cost, double turnCost) edgeCost, VertexId vert
 660165        {
 166            // check if the neighbor vertex is already settled by the backward search
 660167            if (_bidirectionalDijkstra._backward.TryGetVisit(vertex, out var backwardVisit))
 29168            {
 169                // reject U-turns: forward and backward must not arrive via the same edge
 29170                var backwardEdge = _bidirectionalDijkstra._backward.GetVisit(backwardVisit.p).edge;
 38171                if (edge == backwardEdge) return true;
 172
 20173                var combinedCost = totalCost + backwardVisit.cost;
 20174                if (combinedCost < _bidirectionalDijkstra._best.cost)
 2175                {
 2176                    _bidirectionalDijkstra._best = (visit, backwardVisit.p, combinedCost, null);
 2177                }
 20178            }
 179
 651180            return true;
 660181        }
 182
 183        protected override bool OnSettled(uint visit, VertexId vertex, double cost)
 309184        {
 309185            return true;
 309186        }
 187
 188        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, PreviousE
 717189        {
 717190            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, true, previousEdges);
 717191        }
 192
 193        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, IEnumerab
 14194        {
 14195            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, true, previousEdges);
 14196        }
 197    }
 198
 199    internal class BidirectionalDijkstraBackward : DijkstraAlgorithm
 200    {
 201        private readonly BidirectionalDijkstra _bidirectionalDijkstra;
 202
 203        internal BidirectionalDijkstraBackward(BidirectionalDijkstra bidirectionalDijkstra)
 27204            : base(bidirectionalDijkstra._routingNetwork)
 27205        {
 27206            _bidirectionalDijkstra = bidirectionalDijkstra;
 27207        }
 208
 209
 210        protected override bool OnQueued(uint visit, EdgeId edge, (double cost, double turnCost) edgeCost, VertexId vert
 658211        {
 212            // check if the neighbor vertex is already settled by the forward search
 658213            if (_bidirectionalDijkstra._forward.TryGetVisit(vertex, out var forwardVisit))
 29214            {
 215                // reject U-turns: forward and backward must not arrive via the same edge
 29216                var forwardEdge = _bidirectionalDijkstra._forward.GetVisit(forwardVisit.p).edge;
 38217                if (edge == forwardEdge) return true;
 218
 20219                var combinedCost = totalCost + forwardVisit.cost;
 20220                if (combinedCost < _bidirectionalDijkstra._best.cost)
 1221                {
 1222                    _bidirectionalDijkstra._best = (forwardVisit.p, visit, combinedCost, null);
 1223                }
 20224            }
 225
 649226            return true;
 658227        }
 228
 229        protected override bool OnSettled(uint visit, VertexId vertex, double cost)
 309230        {
 309231            return true;
 309232        }
 233
 234        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, PreviousE
 720235        {
 720236            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, false, previousEdges);
 720237        }
 238
 239        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, IEnumerab
 0240        {
 0241            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, false, previousEdges);
 0242        }
 243    }
 244}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
ForNetwork(...)
RunAsync()
CanTurn(...)
.ctor(...)
OnQueued(...)
OnSettled(...)
GetCost(...)
GetCost(...)
.ctor(...)
OnQueued(...)
OnSettled(...)
GetCost(...)
GetCost(...)