< 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:112
Uncovered lines:3
Coverable lines:115
Total lines:188
Line coverage:97.3% (112 of 115)
Covered branches:40
Total branches:48
Branch coverage:83.3% (40 of 48)
Tag:238_19435726042

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
ForNetwork(...)100%1100%
RunAsync()86.36%4495.89%
CanTurn(...)50%4100%
.ctor(...)100%1100%
OnQueued(...)100%1100%
OnSettled(...)100%1100%
GetCost(...)100%1100%
.ctor(...)100%1100%
OnQueued(...)100%1100%
OnSettled(...)100%1100%
GetCost(...)100%1100%

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
 1422    internal BidirectionalDijkstra(RoutingNetwork routingNetwork)
 1423    {
 1424        _routingNetwork = routingNetwork;
 25
 1426        _backward = new BidirectionalDijkstraBackward(this);
 1427        _forward = new BidirectionalDijkstraForward(this);
 1428    }
 29
 1430    public static BidirectionalDijkstra ForNetwork(RoutingNetwork routingNetwork) => new(routingNetwork);
 31
 32    public async Task<(Path? path, double cost)> RunAsync(SnapPoint origin,
 33        SnapPoint destination, ICostFunction costFunction, Func<VertexId, Task<bool>>? settled = null,
 34        Func<VertexId, Task<bool>>? queued = null, CancellationToken cancellationToken = default)
 1435    {
 1436        _costFunction = costFunction;
 37
 1438        (uint forward, uint backward, double cost, Path? singleHopPath) best = (uint.MaxValue, uint.MaxValue, double.Max
 1439        if (_routingNetwork.TrySingleHop(origin, destination, costFunction, out var singleHopPath, out var singleHopCost
 740        {
 741            best = (uint.MaxValue, uint.MaxValue, singleHopCost, singleHopPath);
 742        }
 43
 1444        _backward.Push(costFunction, destination, false);
 1445        _forward.Push(costFunction, origin, true);
 46
 1447        var forwardDone = false;
 1448        var backwardDone = false;
 1449        var forwardCost = 0d;
 1450        var backwardCost = 0d;
 4551        while (!forwardDone || !backwardDone)
 4152        {
 4153            cancellationToken.ThrowIfCancellationRequested();
 54
 4155            if (!forwardDone)
 3756            {
 3757                var (p, v, c) = _forward.Pop();
 3758                forwardCost = c;
 3759                if (p != uint.MaxValue)
 3360                {
 3361                    if (_backward.TryGetVisit(v.vertex, out var backwardVisit))
 1062                    {
 1063                        var cost = c + backwardVisit.cost;
 1064                        if (cost < best.cost &&
 1065                            this.CanTurn(p, backwardVisit.p))
 066                        {
 067                            best = (p, backwardVisit.p, cost, null);
 068                        }
 1069                    }
 70
 4871                    if (settled != null) await settled(v.vertex);
 72
 3373                    if (!_forward.Step(p, v, c)) forwardDone = true;
 3374                }
 75                else
 476                {
 477                    forwardDone = true;
 478                }
 3779            }
 4180            if (!backwardDone)
 4181            {
 4182                var (p, v, c) = _backward.Pop();
 4183                backwardCost = c;
 4184                if (p != uint.MaxValue)
 3785                {
 3786                    if (_forward.TryGetVisit(v.vertex, out var forwardVisit))
 1787                    {
 1788                        var cost = c + forwardVisit.cost;
 1789                        if (cost < best.cost &&
 1790                            this.CanTurn(forwardVisit.p, p))
 391                        {
 392                            best = (forwardVisit.p, p, cost, null);
 393                        }
 1794                    }
 95
 5296                    if (settled != null) await settled(v.vertex);
 97
 3798                    if (!_backward.Step(p, v, c)) backwardDone = true;
 3799                }
 100                else
 4101                {
 4102                    backwardDone = true;
 4103                }
 41104            }
 105
 51106            if (best.cost < (forwardCost + backwardCost)) break;
 31107        }
 108
 18109        if (best.cost >= double.MaxValue) return (null, double.MaxValue);
 17110        if (best.forward == uint.MaxValue) return (best.singleHopPath, best.cost);
 111
 3112        var forwardPath = _forward.GetPathToVisit(best.forward);
 3113        var backwardPath = _backward.GetPathToVisit(best.backward);
 3114        forwardPath.Append(backwardPath.InvertDirection());
 115
 3116        forwardPath.Offset1 = forwardPath.First.direction ? origin.Offset : (ushort)(ushort.MaxValue - origin.Offset);
 3117        forwardPath.Offset2 = forwardPath.Last.direction
 3118            ? destination.Offset
 3119            : (ushort)(ushort.MaxValue - destination.Offset);
 120
 3121        return (forwardPath, best.cost);
 14122    }
 123
 124    private bool CanTurn(uint forwardPointer, uint backwardPointer)
 7125    {
 7126        var (vertex, _, _, _, _) = _forward.GetVisit(forwardPointer);
 7127        var forwardPrevious = _forward.GetPreviousEdges(forwardPointer).ToList();
 7128        if (forwardPrevious.Count == 0) return true; // not a turn.
 7129        var backwardPrevious = _backward.GetPreviousEdges(backwardPointer)
 20130            .Select(x => x.edge).ToList();
 7131        if (backwardPrevious.Count == 0) return true; // not a turn.
 7132        return _forward.CanTurn(vertex, forwardPrevious, backwardPrevious);
 7133    }
 134
 135    internal class BidirectionalDijkstraForward : DijkstraAlgorithm
 136    {
 137        private readonly BidirectionalDijkstra _bidirectionalDijkstra;
 138
 139        internal BidirectionalDijkstraForward(BidirectionalDijkstra bidirectionalDijkstra)
 14140            : base(bidirectionalDijkstra._routingNetwork)
 14141        {
 14142            _bidirectionalDijkstra = bidirectionalDijkstra;
 14143        }
 144
 145
 146        protected override bool OnQueued(uint visit, EdgeId edge, (double cost, double turnCost) edgeCost, VertexId vert
 6147        {
 6148            return true;
 6149        }
 150
 151        protected override bool OnSettled(uint visit, VertexId vertex, double cost)
 33152        {
 33153            return true;
 33154        }
 155
 156        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, IEnumerab
 18157        {
 18158            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, true, previousEdges);
 18159        }
 160    }
 161
 162    internal class BidirectionalDijkstraBackward : DijkstraAlgorithm
 163    {
 164        private readonly BidirectionalDijkstra _bidirectionalDijkstra;
 165
 166        internal BidirectionalDijkstraBackward(BidirectionalDijkstra bidirectionalDijkstra)
 14167            : base(bidirectionalDijkstra._routingNetwork)
 14168        {
 14169            _bidirectionalDijkstra = bidirectionalDijkstra;
 14170        }
 171
 172
 173        protected override bool OnQueued(uint visit, EdgeId edge, (double cost, double turnCost) edgeCost, VertexId vert
 10174        {
 10175            return true;
 10176        }
 177
 178        protected override bool OnSettled(uint visit, VertexId vertex, double cost)
 37179        {
 37180            return true;
 37181        }
 182
 183        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, IEnumerab
 14184        {
 14185            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, false, previousEdges);
 14186        }
 187    }
 188}
Generated by: ReportGenerator 4.8.2.0
11/17/2025 - 15:54:34
GitHub | www.palmmedia.de

Methods/Properties

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