< Summary

Class:Itinero.Routing.Corridors.RouteCorridorSearch
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Corridors/RouteCorridorSearch.cs
Covered lines:342
Uncovered lines:2
Coverable lines:344
Total lines:604
Line coverage:99.4% (342 of 344)
Covered branches:183
Total branches:204
Branch coverage:89.7% (183 of 204)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
RouteCorridorAsync()50%288.88%
RouteCorridorAsync()50%288.88%
Check(...)100%4100%
Corridor(...)100%1100%
get_Transitions()100%1100%
get_Relaxed()100%1100%
OnForward(...)100%1100%
OnBackward(...)100%1100%
Assemble(...)86.53%52100%
OrderAt(...)66.66%6100%
Trim(...)91.66%12100%
Distances(...)100%26100%
LocallyReasonable(...)90.9%22100%
Compact(...)100%2100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Corridors/RouteCorridorSearch.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.Network.Search.Reachability;
 8using Itinero.Routing.DataStructures;
 9using Itinero.Routing.Flavours.Dijkstra;
 10using Itinero.Routing.Flavours.Dijkstra.Bidirectional;
 11using Itinero.Snapping;
 12
 13namespace Itinero.Routing.Corridors;
 14
 15/// <summary>
 16/// Extracts a cost ellipse around a route: every edge that lies on some origin-to-destination
 17/// path costing no more than a multiple of the optimum.
 18/// </summary>
 19/// <remarks>
 20/// Out of the route's own search: its two halves meet in the middle, so neither spans the ellipse
 21/// alone, and lifting the ceiling to the budget keeps what the search would examine anyway.
 22/// </remarks>
 23public static class RouteCorridorSearch
 24{
 25    /// <summary>
 26    /// Resolves the route and extracts the corridor around it, in one search.
 27    /// </summary>
 28    /// <param name="costFactor">
 29    /// The budget as a multiple of the optimum. 1.0 admits only optimal paths.
 30    /// </param>
 31    /// <returns>
 32    /// The route and the corridor around it. The route is handed back because the caller needs
 33    /// the endpoints and cost functions that were actually used, and this call consumed them.
 34    /// </returns>
 35    /// <remarks>
 36    /// At termination <c>budget &lt;= forwardFrontier + backwardFrontier</c>, so one half or the
 37    /// other relaxed every transition of a within-budget path: their union prices them all.
 38    /// </remarks>
 39    public static async Task<Result<(ResolvedRoute Route, RouteCorridor Corridor)>> RouteCorridorAsync(
 40        this RoutingNetwork network,
 41        RoutingSettings settings,
 42        (double longitude, double latitude) origin,
 43        (double longitude, double latitude) destination,
 44        ReachabilityBounds bounds,
 45        double searchBoxMeters,
 46        double costFactor,
 47        CancellationToken cancellationToken = default,
 48        double maxLocalDetour = double.MaxValue)
 2549    {
 2550        Check(costFactor, maxLocalDetour);
 51
 2352        var collector = new TransitionCollector();
 2353        var resolved = await network.ResolveAsync(settings, origin, destination, bounds,
 2354            searchBoxMeters, costFactor, collector.OnForward, collector.OnBackward, cancellationToken);
 2355        if (resolved.IsError)
 056            return new Result<(ResolvedRoute, RouteCorridor)>(resolved.ErrorMessage);
 57
 2358        return Corridor(network, resolved.Value, costFactor, collector, maxLocalDetour, cancellationToken);
 2359    }
 60
 61    /// <summary>
 62    /// Extracts the corridor around a route between two points already snapped, in one search.
 63    /// </summary>
 64    /// <param name="costFactor">
 65    /// The budget as a multiple of the optimum. 1.0 admits only optimal paths.
 66    /// </param>
 67    /// <returns>The route and the corridor around it.</returns>
 68    /// <remarks>
 69    /// Takes the same engine the ordinary one-to-one route takes, so the corridor is around the
 70    /// route the router itself would return. Snapping is the caller's.
 71    /// </remarks>
 72    public static async Task<Result<(ResolvedRoute Route, RouteCorridor Corridor)>> RouteCorridorAsync(
 73        this RoutingNetwork network,
 74        RoutingSettings settings,
 75        SnapPoint source,
 76        SnapPoint target,
 77        double costFactor,
 78        CancellationToken cancellationToken = default,
 79        double maxLocalDetour = double.MaxValue)
 780    {
 781        Check(costFactor, maxLocalDetour);
 82
 783        var collector = new TransitionCollector();
 784        var resolved = await network.SearchAsync(settings, source, target, costFactor,
 785            collector.OnForward, collector.OnBackward, cancellationToken);
 786        if (resolved.IsError)
 087            return new Result<(ResolvedRoute, RouteCorridor)>(resolved.ErrorMessage);
 88
 789        return Corridor(network, resolved.Value, costFactor, collector, maxLocalDetour, cancellationToken);
 790    }
 91
 92    private static void Check(double costFactor, double maxLocalDetour)
 3293    {
 3394        if (costFactor < 1.0) throw new ArgumentOutOfRangeException(nameof(costFactor),
 195            "A corridor cannot be tighter than the optimum it is measured against.");
 3296        if (maxLocalDetour < 1.0) throw new ArgumentOutOfRangeException(nameof(maxLocalDetour),
 197            "A detour cannot be required to beat the stretch it replaces.");
 3098    }
 99
 100    private static Result<(ResolvedRoute Route, RouteCorridor Corridor)> Corridor(
 101        RoutingNetwork network, ResolvedRoute route, double costFactor,
 102        TransitionCollector collector, double maxLocalDetour, CancellationToken cancellationToken)
 30103    {
 30104        return new Result<(ResolvedRoute, RouteCorridor)>((route, Assemble(network, route,
 30105            route.Cost * costFactor, collector.Transitions, collector.Relaxed, maxLocalDetour,
 30106            cancellationToken)));
 30107    }
 108
 109    /// <summary>
 110    /// Collects the states the two halves relaxed, in path order.
 111    /// </summary>
 112    /// <remarks>
 113    /// Arrive at Turn over Prev, then traverse Next. Neither half reports in that convention, so
 114    /// take the state triple only and price it later; the halves' overlap then dedupes free.
 115    /// </remarks>
 116    private sealed class TransitionCollector
 117    {
 696118        public HashSet<(EdgeId Prev, VertexId Turn, EdgeId Next)> Transitions { get; } = new();
 119
 1302120        public int Relaxed { get; private set; }
 121
 122        public void OnForward(EdgeId fromEdge, VertexId turnVertex, EdgeId toEdge)
 318123        {
 318124            this.Relaxed++;
 318125            this.Transitions.Add((fromEdge, turnVertex, toEdge));
 318126        }
 127
 128        public void OnBackward(EdgeId fromEdge, VertexId turnVertex, EdgeId toEdge)
 318129        {
 130            // Against travel the roles swap: in path order the route arrives at turnVertex over
 131            // the edge being relaxed onto, and leaves over the one the half arrived by.
 318132            this.Relaxed++;
 318133            this.Transitions.Add((toEdge, turnVertex, fromEdge));
 318134        }
 135    }
 136
 137    /// <summary>
 138    /// Prices every transition in path order, then applies the corridor's own filter and trim.
 139    /// </summary>
 140    private static RouteCorridor Assemble(
 141        RoutingNetwork network,
 142        ResolvedRoute route,
 143        double budget,
 144        HashSet<(EdgeId Prev, VertexId Turn, EdgeId Next)> transitions,
 145        int relaxed,
 146        double maxLocalDetour,
 147        CancellationToken cancellationToken = default)
 30148    {
 30149        var probe = network.GetEdgeEnumerator();
 30150        var orders = network.GetEdgeEnumerator();
 30151        var costFunction = route.ForwardCostFunction;
 30152        var lengths = new Dictionary<EdgeId, double>();
 153
 30154        var states = new List<CorridorState?> { null, null };
 30155        var nodes = new Dictionary<(EdgeId, VertexId), int>();
 30156        var byVertex = new Dictionary<VertexId, List<int>>();
 30157        var tails = new List<int>(transitions.Count);
 30158        var heads = new List<int>(transitions.Count);
 30159        var costs = new List<double>(transitions.Count);
 160
 30161        var priced = 0;
 922162        foreach (var (prev, turn, next) in transitions)
 416163        {
 164            // As long as the search that produced it, so a cancelled request must not keep
 165            // pricing. Masked: the check is cheap but this runs millions of times.
 445166            if ((priced++ & 0x3FF) == 0) cancellationToken.ThrowIfCancellationRequested();
 167
 168            // Position on Next with Turn as its tail: that is the direction the path travels it.
 416169            if (!probe.MoveTo(next, true)) continue;
 416170            if (probe.Tail != turn && !(probe.MoveTo(next, false) && probe.Tail == turn)) continue;
 171
 416172            var prevOrder = OrderAt(orders, prev, turn);
 416173            var previous = prevOrder.HasValue
 416174                ? PreviousEdgeEnumerable.ForEdge(prev, prevOrder)
 416175                : default;
 416176            var (canAccess, _, _, cost, turnCost) =
 416177                costFunction.Get(probe, tailToHead: true, previous);
 416178            if (!canAccess || cost is >= double.MaxValue or <= 0) continue;
 416179            if (turnCost is >= double.MaxValue or < 0) continue;
 180
 181            // Which way Prev was travelled follows from where it ends, and it ends at the turn.
 416182            var prevForward = orders.MoveTo(prev, true) && orders.Head == turn;
 416183            Add(Node(new CorridorState(prev, prevForward, turn)),
 416184                Node(new CorridorState(next, probe.Forward, probe.Head)),
 416185                cost + turnCost);
 416186        }
 187
 30188        var sourcePartials = AddSourcePartials();
 30189        var destinationPartials = AddDestinationPartials();
 190
 30191        var fromOrigin = Distances(tails, heads, costs, states.Count, budget,
 30192            RouteCorridor.SourceNode, forwards: true);
 30193        var toDestination = Distances(tails, heads, costs, states.Count, budget,
 30194            RouteCorridor.TargetNode, forwards: false);
 195
 196        // Edges reachable only by a detour absurd for what it replaces; the trip-wide budget
 197        // cannot see those. Both fields are recomputed after, since they are published as exact.
 30198        bool[]? alive = null;
 30199        if (maxLocalDetour < double.MaxValue)
 2200        {
 2201            alive = LocallyReasonable(tails, heads, costs, states.Count, fromOrigin, toDestination,
 2202                maxLocalDetour);
 2203            fromOrigin = Distances(tails, heads, costs, states.Count, budget,
 2204                RouteCorridor.SourceNode, forwards: true, alive);
 2205            toDestination = Distances(tails, heads, costs, states.Count, budget,
 2206                RouteCorridor.TargetNode, forwards: false, alive);
 2207        }
 208
 30209        var surviving = new List<int>();
 30210        var originEdges = 0;
 30211        var interiorEdges = 0;
 30212        var destinationEdges = 0;
 1118213        for (var i = 0; i < tails.Count; i++)
 529214        {
 533215            if (alive != null && !alive[i]) continue;
 216
 525217            var before = fromOrigin[tails[i]];
 525218            var after = toDestination[heads[i]];
 771219            if (double.IsPositiveInfinity(before) || double.IsPositiveInfinity(after)) continue;
 303220            if (before + costs[i] + after > budget) continue;
 221
 284222            if (tails[i] == RouteCorridor.SourceNode) originEdges++;
 255223            else if (heads[i] == RouteCorridor.TargetNode) destinationEdges++;
 197224            else interiorEdges++;
 255225            surviving.Add(i);
 255226        }
 227
 30228        var connected = Trim(tails, heads, surviving, states.Count);
 30229        var edges = new List<CorridorEdge>(connected.Count);
 855230        foreach (var i in connected) edges.Add(Materialise(i));
 30231        var (compactStates, compactEdges, compactFromOrigin, compactToDestination) =
 30232            Compact(states, edges, fromOrigin, toDestination);
 233
 30234        var optimalLength = 0d;
 440235        foreach (var (edge, _, offset1, offset2) in route.Path)
 175236        {
 175237            optimalLength += Length(edge) * ((offset2 - offset1) / (double)ushort.MaxValue);
 175238        }
 239
 30240        return new RouteCorridor(compactStates, compactEdges, route.Cost, optimalLength,
 30241            route.Settled, relaxed, surviving.Count - connected.Count,
 30242            originEdges, interiorEdges, destinationEdges, compactFromOrigin, compactToDestination);
 243
 244        // Rebuilt rather than captured from the seeds: a candidate retry re-seeds, and those
 245        // seeds belong to a snap point this route no longer uses.
 246        HashSet<int> AddSourcePartials()
 30247        {
 30248            var partials = new HashSet<int>();
 210249            foreach (var forward in new[] { true, false })
 60250            {
 60251                if (!probe.MoveTo(route.Source.EdgeId, forward)) continue;
 252
 60253                var (canAccess, _, _, cost, _) = costFunction.Get(probe, tailToHead: true);
 60254                if (!canAccess || cost <= 0) continue;
 255
 60256                partials.Add(tails.Count);
 60257                Add(RouteCorridor.SourceNode,
 60258                    Node(new CorridorState(route.Source.EdgeId, probe.Forward, probe.Head)),
 60259                    cost * (forward ? 1 - route.Source.OffsetFactor() : route.Source.OffsetFactor()));
 60260            }
 261
 30262            return partials;
 30263        }
 264
 265        // Into the destination, from every state that can turn onto the target edge. The turn is
 266        // charged here because it exists only once the two sides are composed.
 267        Dictionary<int, bool> AddDestinationPartials()
 30268        {
 30269            var partials = new Dictionary<int, bool>();
 30270            var backwardCostFunction = route.BackwardCostFunction;
 210271            foreach (var forward in new[] { true, false })
 60272            {
 60273                if (!probe.MoveTo(route.Target.EdgeId, forward)) continue;
 274
 60275                var (canAccess, _, _, cost, _) = backwardCostFunction.Get(probe, tailToHead: false);
 60276                if (!canAccess || cost <= 0) continue;
 277
 60278                var at = probe.Head;
 60279                if (!byVertex.TryGetValue(at, out var arrivals)) continue;
 280
 60281                var partialCost =
 60282                    cost * (forward ? 1 - route.Target.OffsetFactor() : route.Target.OffsetFactor());
 406283                foreach (var node in arrivals)
 113284                {
 113285                    var arrival = states[node]!.Value;
 173286                    if (arrival.Edge == route.Target.EdgeId) continue; // U-turn onto the target.
 287
 53288                    var turnCost = SearchHalf.TurnCostBetween(orders, backwardCostFunction,
 53289                        arrival.Edge, OrderAt(orders, arrival.Edge, at), route.Target.EdgeId, forward);
 53290                    if (turnCost is >= double.MaxValue or < 0) continue;
 291
 53292                    partials[tails.Count] = forward;
 53293                    Add(node, RouteCorridor.TargetNode, partialCost + turnCost);
 53294                }
 60295            }
 296
 30297            return partials;
 30298        }
 299
 300        CorridorEdge Materialise(int i)
 255301        {
 255302            if (destinationPartials.TryGetValue(i, out var intoForward))
 29303            {
 304                // intoForward is the orientation the backward half probed the target edge with,
 305                // and it reached the turn at that edge's head â€” so travel runs the other way.
 29306                return new CorridorEdge(tails[i], heads[i], costs[i],
 29307                    Partial(route.Target.EdgeId, intoForward, route.Target),
 29308                    route.Target.EdgeId, !intoForward,
 29309                    intoForward ? CorridorHalf.TargetBackwardFromHead : CorridorHalf.TargetForwardFromTail);
 310            }
 311
 226312            var state = states[heads[i]]!.Value;
 226313            if (sourcePartials.Contains(i))
 29314            {
 29315                return new CorridorEdge(tails[i], heads[i], costs[i],
 29316                    Partial(state.Edge, state.Forward, route.Source), state.Edge, state.Forward,
 29317                    state.Forward ? CorridorHalf.SourceForwardToHead : CorridorHalf.SourceBackwardToTail);
 318            }
 319
 197320            return new CorridorEdge(tails[i], heads[i], costs[i], Length(state.Edge),
 197321                state.Edge, state.Forward, CorridorHalf.None);
 255322        }
 323
 324        void Add(int tail, int head, double cost)
 529325        {
 529326            tails.Add(tail);
 529327            heads.Add(head);
 529328            costs.Add(cost);
 529329        }
 330
 331        int Node(CorridorState state)
 892332        {
 892333            var key = (state.Edge, state.Vertex);
 1358334            if (nodes.TryGetValue(key, out var index)) return index;
 335
 426336            index = states.Count;
 426337            states.Add(state);
 426338            nodes[key] = index;
 426339            if (!byVertex.TryGetValue(state.Vertex, out var at))
 249340            {
 249341                at = new List<int>(2);
 249342                byVertex[state.Vertex] = at;
 249343            }
 426344            at.Add(index);
 426345            return index;
 892346        }
 347
 348        double Length(EdgeId edge)
 430349        {
 657350            if (lengths.TryGetValue(edge, out var length)) return length;
 351
 203352            length = probe.MoveTo(edge, true) ? probe.EdgeLength() : 0d;
 203353            lengths[edge] = length;
 203354            return length;
 430355        }
 356
 357        // The same fraction of the edge the partial's cost was scaled by.
 358        double Partial(EdgeId edge, bool towardHead, SnapPoint snap) =>
 58359            Length(edge) * (towardHead ? 1 - snap.OffsetFactor() : snap.OffsetFactor());
 30360    }
 361
 362    /// The order of <paramref name="edge"/> at <paramref name="vertex"/>, whichever end that is.
 363    private static byte? OrderAt(
 364        RoutingNetworkEdgeEnumerator enumerator, EdgeId edge, VertexId vertex)
 469365    {
 469366        if (!enumerator.MoveTo(edge, true)) return null;
 367
 469368        return enumerator.Head == vertex ? enumerator.HeadOrder
 469369            : enumerator.Tail == vertex ? enumerator.TailOrder
 469370            : null;
 469371    }
 372
 373    /// <summary>
 374    /// Drops every edge that does not lie on some origin-to-destination path inside the corridor.
 375    /// </summary>
 376    /// <remarks>
 377    /// The cost filter proves a continuation exists in the network, not in the corridor, so a
 378    /// transition can price inside the budget with nothing to continue into. Not visibly wrong.
 379    /// </remarks>
 380    private static List<int> Trim(
 381        List<int> tails, List<int> heads, List<int> candidates, int nodeCount)
 30382    {
 30383        var outgoing = new List<int>[nodeCount];
 30384        var incoming = new List<int>[nodeCount];
 600385        foreach (var e in candidates)
 255386        {
 255387            (outgoing[tails[e]] ??= new List<int>()).Add(e);
 255388            (incoming[heads[e]] ??= new List<int>()).Add(e);
 255389        }
 390
 30391        var fromOrigin = Reach(RouteCorridor.SourceNode, outgoing, forwards: true);
 30392        var toDestination = Reach(RouteCorridor.TargetNode, incoming, forwards: false);
 393
 30394        var kept = new List<int>(candidates.Count);
 600395        foreach (var e in candidates)
 255396        {
 510397            if (fromOrigin[tails[e]] && toDestination[heads[e]]) kept.Add(e);
 255398        }
 399
 30400        return kept;
 401
 402        bool[] Reach(int start, List<int>[] adjacency, bool forwards)
 60403        {
 60404            var seen = new bool[nodeCount];
 60405            var stack = new Stack<int>();
 60406            seen[start] = true;
 60407            stack.Push(start);
 554408            while (stack.Count > 0)
 494409            {
 2502410                foreach (var e in adjacency[stack.Pop()] ?? [])
 510411                {
 510412                    var next = forwards ? heads[e] : tails[e];
 586413                    if (seen[next]) continue;
 414
 434415                    seen[next] = true;
 434416                    stack.Push(next);
 434417                }
 494418            }
 419
 60420            return seen;
 60421        }
 30422    }
 423
 424    /// <summary>
 425    /// Shortest paths over the traced graph, out of a node or into it.
 426    /// </summary>
 427    /// <remarks>
 428    /// Over the traced graph, not either half's settled costs: each may only enter the pocket it
 429    /// started in, but their union holds every within-budget path in full.
 430    /// </remarks>
 431    private static double[] Distances(
 432        List<int> tails, List<int> heads, List<double> costs, int nodeCount, double budget,
 433        int start, bool forwards, bool[]? alive = null)
 64434    {
 64435        var adjacency = new List<int>[nodeCount];
 2380436        for (var e = 0; e < tails.Count; e++)
 1126437        {
 1134438            if (alive != null && !alive[e]) continue;
 439
 1118440            (adjacency[forwards ? tails[e] : heads[e]] ??= new List<int>()).Add(e);
 1118441        }
 442
 64443        var distances = new double[nodeCount];
 64444        Array.Fill(distances, double.PositiveInfinity);
 64445        distances[start] = 0;
 446
 64447        var queue = new BinaryHeap<int>();
 64448        queue.Push(start, 0);
 64449        var settled = new bool[nodeCount];
 450
 853451        while (queue.Count > 0)
 789452        {
 789453            var node = queue.Pop(out var cost);
 824454            if (settled[node]) continue;
 455
 754456            settled[node] = true;
 754457            if (cost > budget) break;
 458
 3910459            foreach (var e in adjacency[node] ?? [])
 824460            {
 824461                var next = forwards ? heads[e] : tails[e];
 824462                var candidate = cost + costs[e];
 923463                if (candidate >= distances[next] || candidate > budget) continue;
 464
 725465                distances[next] = candidate;
 725466                queue.Push(next, candidate);
 725467            }
 754468        }
 469
 64470        return distances;
 64471    }
 472
 473
 474    /// <summary>
 475    /// Which edges are reachable without a local detour worse than <paramref name="maxDetour"/>
 476    /// times the stretch it replaces. Per edge, so a flow model with no single path can use it.
 477    /// </summary>
 478    /// <remarks>
 479    /// O(1) an edge: its cheapest path leaves the optimum at A and rejoins at B, both on the
 480    /// optimum, so the replaced stretch costs <c>d_D(A) - d_D(B)</c> with no path walked.
 481    /// </remarks>
 482    private static bool[] LocallyReasonable(
 483        List<int> tails, List<int> heads, List<double> costs, int nodeCount,
 484        double[] fromOrigin, double[] toDestination, double maxDetour)
 2485    {
 2486        var alive = new bool[tails.Count];
 2487        Array.Fill(alive, true);
 488
 489        // The predecessor and successor each field's descent would pick, per node.
 2490        var toward = new int[nodeCount];
 2491        var onward = new int[nodeCount];
 2492        Array.Fill(toward, -1);
 2493        Array.Fill(onward, -1);
 72494        for (var e = 0; e < tails.Count; e++)
 34495        {
 58496            if (Realises(fromOrigin, heads[e], tails[e], costs[e])) toward[heads[e]] = e;
 54497            if (Realises(toDestination, tails[e], heads[e], costs[e])) onward[tails[e]] = e;
 34498        }
 499
 500        // The optimum: descend to the destination from the origin. Its nodes are the ones a
 501        // detour can be measured against.
 2502        var onOptimum = new bool[nodeCount];
 2503        var at = RouteCorridor.SourceNode;
 28504        for (var guard = 0; at != RouteCorridor.TargetNode && guard <= tails.Count; guard++)
 12505        {
 12506            onOptimum[at] = true;
 12507            var step = onward[at];
 12508            if (step < 0) return alive; // no optimum to compare against; keep everything
 509
 12510            at = heads[step];
 12511        }
 512
 2513        onOptimum[RouteCorridor.TargetNode] = true;
 514
 2515        var ancestor = Nearest(toward, tails, heads, onOptimum, towardOrigin: true);
 2516        var descendant = Nearest(onward, tails, heads, onOptimum, towardOrigin: false);
 517
 72518        for (var e = 0; e < tails.Count; e++)
 34519        {
 34520            var a = ancestor[tails[e]];
 34521            var b = descendant[heads[e]];
 52522            if (a < 0 || b < 0) continue;
 523
 16524            var replaced = toDestination[a] - toDestination[b];
 16525            var detour = (fromOrigin[tails[e]] - fromOrigin[a]) + costs[e]
 16526                         + (toDestination[heads[e]] - toDestination[b]);
 16527            if (detour <= 0) continue;
 528
 529            // Leaving and rejoining at the same point replaces nothing, which no factor excuses.
 16530            alive[e] = replaced > 0 && detour <= replaced * maxDetour;
 16531        }
 532
 2533        return alive;
 534
 535        static bool Realises(double[] field, int from, int to, double cost) =>
 68536            !double.IsPositiveInfinity(field[from]) && !double.IsPositiveInfinity(field[to]) &&
 68537            Math.Abs(field[to] + cost - field[from]) < 1e-6;
 538
 539        // Walk each node to the first optimum node its descent reaches, memoised, so the whole
 540        // map costs one pass rather than one walk per edge.
 541        int[] Nearest(int[] step, List<int> t, List<int> h, bool[] optimum, bool towardOrigin)
 4542        {
 4543            var nearest = new int[nodeCount];
 4544            Array.Fill(nearest, -2);
 212545            for (var n = 0; n < nodeCount; n++) Resolve(n);
 546
 4547            return nearest;
 548
 549            int Resolve(int node)
 88550            {
 108551                if (nearest[node] != -2) return nearest[node];
 96552                if (optimum[node]) return nearest[node] = node;
 553
 40554                nearest[node] = -1; // breaks a cycle rather than recursing into it
 40555                var e = step[node];
 60556                if (e < 0) return nearest[node] = -1;
 557
 20558                return nearest[node] = Resolve(towardOrigin ? t[e] : h[e]);
 88559            }
 4560        }
 2561    }
 562
 563    /// <summary>
 564    /// Renumbers the nodes the surviving edges actually use, dropping the rest.
 565    /// </summary>
 566    /// <remarks>
 567    /// Numbering happens while the trace is assembled, so most entries do not survive the filter;
 568    /// the gaps would otherwise make every caller walk nodes no edge refers to.
 569    /// </remarks>
 570    private static (List<CorridorState?> states, List<CorridorEdge> edges,
 571        List<double> fromOrigin, List<double> toDestination)
 572        Compact(List<CorridorState?> states, List<CorridorEdge> edges,
 573            double[] fromOrigin, double[] toDestination)
 30574    {
 30575        var renumbered = new int[states.Count];
 30576        Array.Fill(renumbered, -1);
 30577        renumbered[RouteCorridor.SourceNode] = RouteCorridor.SourceNode;
 30578        renumbered[RouteCorridor.TargetNode] = RouteCorridor.TargetNode;
 579
 30580        var compactStates = new List<CorridorState?> { null, null };
 30581        var compactFromOrigin = new List<double>
 30582            { fromOrigin[RouteCorridor.SourceNode], fromOrigin[RouteCorridor.TargetNode] };
 30583        var compactToDestination = new List<double>
 30584            { toDestination[RouteCorridor.SourceNode], toDestination[RouteCorridor.TargetNode] };
 30585        var compactEdges = new List<CorridorEdge>(edges.Count);
 600586        foreach (var edge in edges)
 255587        {
 255588            compactEdges.Add(edge with { Tail = Renumber(edge.Tail), Head = Renumber(edge.Head) });
 255589        }
 590
 30591        return (compactStates, compactEdges, compactFromOrigin, compactToDestination);
 592
 593        int Renumber(int node)
 510594        {
 832595            if (renumbered[node] >= 0) return renumbered[node];
 596
 188597            renumbered[node] = compactStates.Count;
 188598            compactStates.Add(states[node]);
 188599            compactFromOrigin.Add(fromOrigin[node]);
 188600            compactToDestination.Add(toDestination[node]);
 188601            return renumbered[node];
 510602        }
 30603    }
 604}