< 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:95
Uncovered lines:9
Coverable lines:104
Total lines:174
Line coverage:91.3% (95 of 104)
Covered branches:31
Total branches:40
Branch coverage:77.5% (31 of 40)
Tag:232_15462506344

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
ForNetwork(...)100%1100%
RunAsync()77.5%4087.32%
.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.Threading;
 4using System.Threading.Tasks;
 5using Itinero.Network;
 6using Itinero.Network.Enumerators.Edges;
 7using Itinero.Routes.Paths;
 8using Itinero.Routing.Costs;
 9using Itinero.Snapping;
 10
 11namespace Itinero.Routing.Flavours.Dijkstra.Bidirectional;
 12
 13
 14internal class BidirectionalDijkstra
 15{
 16    private readonly RoutingNetwork _routingNetwork;
 17    private readonly BidirectionalDijkstraForward _forward;
 18    private readonly BidirectionalDijkstraBackward _backward;
 19    private ICostFunction _costFunction;
 20
 921    internal BidirectionalDijkstra(RoutingNetwork routingNetwork)
 922    {
 923        _routingNetwork = routingNetwork;
 24
 925        _backward = new BidirectionalDijkstraBackward(this);
 926        _forward = new BidirectionalDijkstraForward(this);
 927    }
 28
 929    public static BidirectionalDijkstra ForNetwork(RoutingNetwork routingNetwork) => new(routingNetwork);
 30
 31    public async Task<(Path? path, double cost)> RunAsync(SnapPoint origin,
 32        SnapPoint destination, ICostFunction costFunction, Func<VertexId, Task<bool>>? settled = null,
 33        Func<VertexId, Task<bool>>? queued = null, CancellationToken cancellationToken = default)
 934    {
 935        _costFunction = costFunction;
 36
 937        (uint forward, uint backward, double cost, Path? singleHopPath) best = (uint.MaxValue, uint.MaxValue, double.Max
 938        if (_routingNetwork.TrySingleHop(origin, destination, costFunction, out var singleHopPath, out var singleHopCost
 739        {
 740            best = (uint.MaxValue, uint.MaxValue, singleHopCost, singleHopPath);
 741        }
 42
 943        _backward.Push(costFunction, destination, false);
 944        _forward.Push(costFunction, origin, true);
 45
 946        var forwardDone = false;
 947        var backwardDone = false;
 948        var forwardCost = 0d;
 949        var backwardCost = 0d;
 2050        while (!forwardDone || !backwardDone)
 2051        {
 2052            cancellationToken.ThrowIfCancellationRequested();
 53
 2054            if (!forwardDone)
 2055            {
 2056                var (p, v, c) = _forward.Pop();
 2057                forwardCost = c;
 2058                if (p != uint.MaxValue)
 2059                {
 2060                    if (_backward.TryGetVisit(v.vertex, out var backwardVisit))
 961                    {
 962                        var cost = c + backwardVisit.cost;
 963                        if (cost < best.cost)
 064                        {
 065                            best = (p, backwardVisit.p, cost, null);
 066                        }
 967                    }
 68
 3569                    if (settled != null) await settled(v.vertex);
 70
 2071                    if (!_forward.Step(p, v, c)) forwardDone = true;
 2072                }
 73                else
 074                {
 075                    forwardDone = true;
 076                }
 2077            }
 2078            if (!backwardDone)
 2079            {
 2080                var (p, v, c) = _backward.Pop();
 2081                backwardCost = c;
 2082                if (p != uint.MaxValue)
 2083                {
 2084                    if (_forward.TryGetVisit(v.vertex, out var forwardVisit))
 1185                    {
 1186                        var cost = c + forwardVisit.cost;
 1187                        if (cost < best.cost)
 288                        {
 289                            best = (forwardVisit.p, p, cost, null);
 290                        }
 1191                    }
 92
 3593                    if (settled != null) await settled(v.vertex);
 94
 2095                    if (!_backward.Step(p, v, c)) backwardDone = true;
 2096                }
 97                else
 098                {
 099                    backwardDone = true;
 0100                }
 20101            }
 102
 29103            if (best.cost < (forwardCost + backwardCost)) break;
 11104        }
 105
 9106        if (best.cost >= double.MaxValue) return (null, double.MaxValue);
 16107        if (best.forward == uint.MaxValue) return (best.singleHopPath, best.cost);
 108
 2109        var forwardPath = _forward.GetPathToVisit(best.forward);
 2110        var backwardPath = _backward.GetPathToVisit(best.backward);
 2111        forwardPath.Append(backwardPath.InvertDirection());
 112
 2113        forwardPath.Offset1 = forwardPath.First.direction ? origin.Offset : (ushort)(ushort.MaxValue - origin.Offset);
 2114        forwardPath.Offset2 = forwardPath.Last.direction
 2115            ? destination.Offset
 2116            : (ushort)(ushort.MaxValue - destination.Offset);
 117
 2118        return (forwardPath, best.cost);
 9119    }
 120
 121    internal class BidirectionalDijkstraForward : DijkstraAlgorithm
 122    {
 123        private readonly BidirectionalDijkstra _bidirectionalDijkstra;
 124
 125        internal BidirectionalDijkstraForward(BidirectionalDijkstra bidirectionalDijkstra)
 9126            : base(bidirectionalDijkstra._routingNetwork)
 9127        {
 9128            _bidirectionalDijkstra = bidirectionalDijkstra;
 9129        }
 130
 131
 132        protected override bool OnQueued(uint visit, EdgeId edge, (double cost, double turnCost) edgeCost, VertexId vert
 2133        {
 2134            return true;
 2135        }
 136
 137        protected override bool OnSettled(uint visit, VertexId vertex, double cost)
 20138        {
 20139            return true;
 20140        }
 141
 142        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, IEnumerab
 2143        {
 2144            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, true, previousEdges);
 2145        }
 146    }
 147
 148    internal class BidirectionalDijkstraBackward : DijkstraAlgorithm
 149    {
 150        private readonly BidirectionalDijkstra _bidirectionalDijkstra;
 151
 152        internal BidirectionalDijkstraBackward(BidirectionalDijkstra bidirectionalDijkstra)
 9153            : base(bidirectionalDijkstra._routingNetwork)
 9154        {
 9155            _bidirectionalDijkstra = bidirectionalDijkstra;
 9156        }
 157
 158
 159        protected override bool OnQueued(uint visit, EdgeId edge, (double cost, double turnCost) edgeCost, VertexId vert
 2160        {
 2161            return true;
 2162        }
 163
 164        protected override bool OnSettled(uint visit, VertexId vertex, double cost)
 20165        {
 20166            return true;
 20167        }
 168
 169        protected override (double cost, double turnCost) GetCost(RoutingNetworkEdgeEnumerator edgeEnumerator, IEnumerab
 2170        {
 2171            return _bidirectionalDijkstra._costFunction.GetCost(edgeEnumerator, false, previousEdges);
 2172        }
 173    }
 174}
Generated by: ReportGenerator 4.8.2.0
06/05/2025 - 08:42:07
GitHub | www.palmmedia.de

Methods/Properties

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