< Summary

Class:Itinero.Routing.Flavours.Dijkstra.Bidirectional.SearchHalf
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/SearchHalf.cs
Covered lines:153
Uncovered lines:32
Coverable lines:185
Total lines:458
Line coverage:82.7% (153 of 185)
Covered branches:95
Total branches:112
Branch coverage:84.8% (95 of 112)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_IsForwardHalf()100%1100%
get_OtherEndpointEdge()100%1100%
get_ReachedOtherEndpoint()100%1100%
.ctor(...)100%1100%
get_SawLocalAccess()100%1100%
get_LocalOnHeap()100%1100%
Clear()100%10%
PopCounted(...)100%2100%
PushCounted(...)100%2100%
PushTerminal(...)100%10100%
ReKey(...)85.71%14100%
EscapeLocalAsync()100%8100%
<EscapeLocalAsync()50%257.14%
ExpandAsync()0%40%
<ExpandAsync()0%20%
Probe(...)100%4100%
StepAsync()87.93%58100%
Potential(...)100%2100%
TurnCostBetween(...)75%4100%
IsMain(...)100%1100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/SearchHalf.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.Costs;
 9using Itinero.Routing.DataStructures;
 10using Itinero.Snapping;
 11
 12namespace Itinero.Routing.Flavours.Dijkstra.Bidirectional;
 13
 14/// <summary>
 15/// One side of a bidirectional search: everything reached so far from one endpoint, and
 16/// everywhere it could go next.
 17/// </summary>
 18/// <remarks>
 19/// A type of its own because a half outlives the call that created it: the half the snapper
 20/// expands to check reachability IS the half the search continues with.
 21/// </remarks>
 22internal sealed class SearchHalf
 23{
 24    /// <summary>
 25    /// Whether this half grows forward from an origin or backward from a destination; it decides
 26    /// which way edge costs are read, so it belongs to the half rather than to each step.
 27    /// </summary>
 545528    public bool IsForwardHalf { get; }
 29
 30
 31    /// <summary>
 32    /// The edge at the other end of the route. Set so this half can notice when it gets there.
 33    /// </summary>
 488234    public EdgeId? OtherEndpointEdge { get; set; }
 35
 36    /// <summary>
 37    /// Whether this half has settled a state on <see cref="OtherEndpointEdge"/>.
 38    /// </summary>
 39    /// <remarks>
 40    /// With an empty heap this separates "nowhere left to go" from "already there": no path
 41    /// exists, so the other half need not walk to the tile budget to find that out.
 42    /// </remarks>
 13443    public bool ReachedOtherEndpoint { get; private set; }
 44
 26845    public SearchHalf(bool isForwardHalf)
 26846    {
 26847        this.IsForwardHalf = isForwardHalf;
 26848    }
 49
 50    /// <summary>
 51    /// Whether this half has traversed a local-access edge. A closed component out in ordinary
 52    /// road network is an island and there is nothing more to learn about it; among
 53    /// access=destination edges it is worth a second opinion before rejecting a snap.
 54    /// </summary>
 1554455    public bool SawLocalAccess { get; private set; }
 56
 57    /// <summary>
 58    /// Local-access states pushed but not yet settled. Zero means the frontier has left the
 59    /// enclave rather than merely touched its edge.
 60    /// </summary>
 61    /// <remarks>
 62    /// Counted rather than scanned: asked after every step, so walking the heap would make
 63    /// escaping a pocket quadratic in its size.
 64    /// </remarks>
 41765    public int LocalOnHeap { get; private set; }
 66
 26867    public readonly PathTree Tree = new();
 68
 69    // Carries g because the heap is ordered by g + p; only the stopping rule uses the key.
 26870    public readonly BinaryHeap<(uint pointer, EdgeId edge, VertexId vertex, double g)> Heap = new();
 26871    public readonly HashSet<(EdgeId edge, VertexId vertex)> Settled = new();
 72
 73    // Per-vertex list of settled arrivals. Each entry records the incoming edge plus the head
 74    // order at this vertex for that edge — both are needed to query turn costs against this
 75    // label when the other half asks "can I meet you here?".
 26876    public readonly Dictionary<VertexId, List<SettledEntry>> SettledByVertex = new();
 77
 78    public void Clear()
 079    {
 080        Tree.Clear();
 081        Heap.Clear();
 082        Settled.Clear();
 083        SettledByVertex.Clear();
 084        this.SawLocalAccess = false;
 085        this.LocalOnHeap = 0;
 086        this.ReachedOtherEndpoint = false;
 087    }
 88
 89    /// Pops one state, keeping the local-frontier count in step.
 90    private (uint pointer, EdgeId edge, VertexId vertex, double g) PopCounted(out double key)
 461491    {
 461492        var entry = Heap.Pop(out key);
 461493        var (_, _, _, _, localAccess, _, _) = Tree.GetVisitWithState(entry.pointer);
 470894        if (localAccess) this.LocalOnHeap--;
 461495        return entry;
 461496    }
 97
 98    /// Pushes one state, keeping the local-frontier count in step.
 99    private void PushCounted((uint pointer, EdgeId edge, VertexId vertex, double g) entry,
 100        double key, bool localAccess)
 5293101    {
 5391102        if (localAccess) this.LocalOnHeap++;
 5293103        Heap.Push(entry, key);
 5293104    }
 105
 106    /// <summary>
 107    /// Seeds this half from a snapped point: the states you can be in having just started on
 108    /// that edge, at that offset.
 109    /// </summary>
 110    public void PushTerminal(
 111        RoutingNetworkEdgeEnumerator enumerator,
 112        SnapPoint snap,
 113        ICostFunction costFunction,
 114        HeuristicFunc? potential)
 238115    {
 116        // Forward half computes cost in the edge's natural direction, backward half against it,
 117        // so the backward half reaches "back toward the origin" with the right weights.
 1666118        foreach (var forward in new[] { true, false })
 476119        {
 476120            if (!enumerator.MoveTo(snap.EdgeId, forward)) continue;
 476121            var (canAccess, _, localAccess, cost, _) = costFunction.Get(enumerator, tailToHead: this.IsForwardHalf);
 510122            if (!canAccess || cost <= 0) continue;
 442123            var offsetCost = forward
 442124                ? cost * (1 - snap.OffsetFactor())
 442125                : cost * snap.OffsetFactor();
 442126            this.SawLocalAccess |= localAccess;
 442127            var p = Tree.AddVisit(enumerator, leftMain: false, localAccess: localAccess, uint.MaxValue);
 442128            this.PushCounted((p, enumerator.EdgeId, enumerator.Head, offsetCost),
 442129                offsetCost + Potential(potential, enumerator), localAccess);
 130
 442131        }
 238132    }
 133
 134    /// <summary>
 135    /// Rebuilds the frontier's ordering against a goal-direction potential.
 136    /// </summary>
 137    /// <remarks>
 138    /// An expansion with no goal keyed its frontier with p = 0; mixing that with potential-keyed
 139    /// states settles them out of order, which in a Dijkstra is a wrong answer, not a slow one.
 140    /// </remarks>
 141    public void ReKey(RoutingNetwork network, HeuristicFunc? potential)
 2142    {
 2143        if (potential == null || Heap.Count == 0) return;
 144
 2145        var entries = new List<(uint pointer, EdgeId edge, VertexId vertex, double g)>(Heap.Count);
 10146        while (Heap.Count > 0) entries.Add(Heap.Pop(out _));
 147
 2148        var enumerator = network.GetEdgeEnumerator();
 14149        foreach (var entry in entries)
 4150        {
 151            // Position on the arrival so the potential is taken at the state's own location,
 152            // matching how the key was formed when the search pushes normally.
 4153            var p = 0d;
 4154            if (enumerator.MoveTo(entry.edge, true))
 4155            {
 4156                p = enumerator.Head == entry.vertex
 4157                    ? Potential(potential, enumerator)
 4158                    : enumerator.MoveTo(entry.edge, false) ? Potential(potential, enumerator) : 0d;
 4159            }
 160
 4161            Heap.Push(entry, entry.g + p);
 4162        }
 2163    }
 164
 165    /// <summary>
 166    /// Expands out of a local-access enclave, stopping once it is properly clear of it.
 167    /// </summary>
 168    /// <param name="threshold">
 169    /// How much must be explored before clearing the enclave counts; without it, stepping onto
 170    /// the first ordinary road would stop the search having proven nothing.
 171    /// </param>
 172    /// <param name="ceiling">
 173    /// Work limit. Reaching it means the area is too big to treat as an enclave at all.
 174    /// </param>
 175    /// <remarks>
 176    /// Both halves of the stopping condition are load-bearing: the threshold alone can stop deep
 177    /// inside the enclave, the non-local frontier alone one edge out of a driveway.
 178    /// </remarks>
 179    public async Task<ReachabilityVerdict> EscapeLocalAsync(
 180        RoutingNetwork network,
 181        ICostFunction costFunction,
 182        int threshold,
 183        int ceiling,
 184        CancellationToken cancellationToken = default)
 8185    {
 8186        var expanded = 0;
 100187        while (Heap.Count > 0)
 98188        {
 98189            cancellationToken.ThrowIfCancellationRequested();
 190
 98191            await this.StepAsync(network, costFunction, isMainN: null, localAccessRule: true,
 98192                bestCost: double.MaxValue, settledCb: LoadTileFor, potential: null,
 98193                onReached: null, cancellationToken);
 194
 98195            expanded++;
 196
 197            // Too big to be an enclave. Not a statement that the search got out of anything —
 198            // a statement that there is nothing here to get out of.
 99199            if (expanded >= ceiling) return ReachabilityVerdict.BeyondBound;
 200
 102201            if (expanded >= threshold && this.LocalOnHeap == 0) return ReachabilityVerdict.BeyondBound;
 92202        }
 203
 204        // Ran out of network. Everything reachable from the enclave has been seen and it does
 205        // not lead anywhere, whether or not it ever got onto ordinary roads.
 2206        return ReachabilityVerdict.Island;
 207
 208        async Task<bool> LoadTileFor(VertexId v)
 98209        {
 98210            if (!network.UsageNotifier.IsVertexDataReady(network, v))
 0211            {
 0212                await network.UsageNotifier.NotifyVertex(network, v, cancellationToken);
 0213            }
 214
 98215            return false;
 98216        }
 8217    }
 218
 219    /// <summary>
 220    /// Expands until this half either runs out of network or has gone far enough to be believed —
 221    /// the reachability check a snap needs, done by the search that will continue from here.
 222    /// </summary>
 223    /// <param name="ceiling">
 224    /// States to expand before concluding the network is real. Running out first means the
 225    /// component is closed, which is an island whatever its size.
 226    /// </param>
 227    /// <remarks>
 228    /// No access rule here, deliberately: the question is what can be reached, not what route is
 229    /// legal, so a non-local road buried in an estate is crossed rather than refused.
 230    /// </remarks>
 231    public async Task<ReachabilityVerdict> ExpandAsync(
 232        RoutingNetwork network,
 233        ICostFunction costFunction,
 234        int ceiling,
 235        CancellationToken cancellationToken = default)
 0236    {
 0237        var expanded = 0;
 0238        while (Heap.Count > 0)
 0239        {
 0240            cancellationToken.ThrowIfCancellationRequested();
 241
 242            // The same access rule the search itself applies, and it has to be: these states
 243            // become the search's frontier, so anything allowed here the finished route may do.
 0244            await this.StepAsync(network, costFunction, isMainN: null, localAccessRule: true,
 0245                bestCost: double.MaxValue, settledCb: LoadTileFor, potential: null,
 0246                onReached: null, cancellationToken);
 247
 0248            expanded++;
 0249            if (expanded >= ceiling) return ReachabilityVerdict.BeyondBound;
 0250        }
 251
 252        // Ran out of network: everything reachable has been seen and none of it leaves.
 0253        return ReachabilityVerdict.Island;
 254
 255        // Pulls in a vertex's tile before expanding from it. Without this the walk stops at the
 256        // edge of whatever happens to be loaded and reports an island wherever the data ran out.
 257        async Task<bool> LoadTileFor(VertexId v)
 0258        {
 0259            if (!network.UsageNotifier.IsVertexDataReady(network, v))
 0260            {
 0261                await network.UsageNotifier.NotifyVertex(network, v, cancellationToken);
 0262            }
 263
 0264            return false;
 0265        }
 0266    }
 267
 268    private RoutingNetwork? _probeNetwork;
 269
 270    private RoutingNetworkEdgeEnumerator? _probe;
 271
 272    /// <summary>
 273    /// The edge enumerator this half expands with, created once and reused.
 274    /// </summary>
 275    /// <remarks>
 276    /// A fresh one per step was three allocations per settled state and the top two entries in
 277    /// the allocation profile. Safe because a half is never stepped concurrently with itself.
 278    /// </remarks>
 279    private RoutingNetworkEdgeEnumerator Probe(RoutingNetwork network)
 2373280    {
 4586281        if (_probe != null && ReferenceEquals(_probeNetwork, network)) return _probe;
 282
 160283        _probe = network.GetEdgeEnumerator();
 160284        _probeNetwork = network;
 285
 160286        return _probe;
 2373287    }
 288
 289    /// <summary>
 290    /// Settles the cheapest state on the frontier and relaxes its neighbours.
 291    /// </summary>
 292    /// <param name="onReached">
 293    /// Invoked for every state settled or queued; null when a half expands alone for a snapping
 294    /// check, because there is no other half yet.
 295    /// </param>
 296    /// <param name="bestCost">
 297    /// Cost of the best complete path so far, used to prune. No bound yet means MaxValue.
 298    /// </param>
 299    /// <returns>The key of the state settled, or of the last one popped if already settled.</returns>
 300    public async ValueTask<double?> StepAsync(
 301        RoutingNetwork network,
 302        ICostFunction costFunction,
 303        IsMainNFunc? isMainN,
 304        bool localAccessRule,
 305        double bestCost,
 306        Func<VertexId, Task<bool>>? settledCb,
 307        HeuristicFunc? potential,
 308        ReachedCallback? onReached,
 309        CancellationToken cancellationToken,
 310        RelaxedCallback? onRelaxed = null)
 2373311    {
 312        // Dequeue, skipping already-settled labels. `key` is g + p, `cost` is g.
 313        // PopCounted keeps LocalOnHeap in step: every pushed state is popped exactly once,
 314        // including the ones skipped here as already settled, so the count balances.
 2373315        var entry = this.PopCounted(out var key);
 4614316        while (Settled.Contains((entry.edge, entry.vertex)))
 2241317        {
 2241318            if (Heap.Count == 0) return key;
 2241319            entry = this.PopCounted(out key);
 2241320        }
 2373321        if (!Settled.Add((entry.edge, entry.vertex))) return key;
 322
 2373323        var cost = entry.g;
 324
 2373325        var (vertex, edge, forward, _, localAccess, headOrder, _) = Tree.GetVisitWithState(entry.pointer);
 2373326        this.SawLocalAccess |= localAccess;
 327
 2373328        if (this.OtherEndpointEdge.HasValue && edge == this.OtherEndpointEdge.Value)
 90329        {
 90330            this.ReachedOtherEndpoint = true;
 90331        }
 332
 333        // Record in per-vertex settled multimap for meeting checks initiated by the other half.
 2373334        if (!SettledByVertex.TryGetValue(vertex, out var list))
 1282335        {
 1282336            list = new List<SettledEntry>(2);
 1282337            SettledByVertex[vertex] = list;
 1282338        }
 2373339        list.Add(new SettledEntry(edge, forward, headOrder, entry.pointer, cost));
 340
 341        // Settled callback semantics match the unidirectional edge-based: returning true
 342        // means "stop expanding from this vertex" (e.g. outside the max-distance box).
 2373343        if (settledCb != null && await settledCb(vertex)) return key;
 2373344        if (cancellationToken.IsCancellationRequested) return key;
 345
 2373346        onReached?.Invoke(edge, forward, headOrder, entry.pointer, cost, vertex);
 347
 348        // Expand neighbours.
 2373349        var probe = this.Probe(network);
 2373350        if (!probe.MoveTo(vertex)) return key;
 9725351        while (probe.MoveNext())
 7352352        {
 7352353            var neighbourEdge = probe.EdgeId;
 9725354            if (neighbourEdge == edge) continue; // no U-turn
 355
 356            // Cost in this half's direction. Forward uses tailToHead=true, backward uses false.
 357            // PreviousEdgeEnumerable provides turn-cost context from the path so far.
 4979358            var prev = new PreviousEdgeEnumerable(Tree, entry.pointer);
 4979359            var (canAccess, _, neighbourLocalAccess, neighbourCost, turnCost) =
 4979360                costFunction.Get(probe, tailToHead: this.IsForwardHalf, prev);
 4979361            if (!canAccess || neighbourCost is >= double.MaxValue or <= 0) continue;
 5001362            if (turnCost is >= double.MaxValue or < 0) continue;
 4957363            this.SawLocalAccess |= neighbourLocalAccess;
 364
 365            // A local-access edge may only be reached from another, so each half stays inside its
 366            // own pocket and cannot use access=destination streets as a shortcut between roads.
 4957367            if (localAccessRule)
 766368            {
 369                // L to L, L to N, N to N. Never N to L: a half leaves its pocket once and never
 370                // enters another, so the composed path is pocket, network, pocket.
 767371                if (neighbourLocalAccess && !localAccess) continue;
 765372            }
 373            // Per-half access-aware rule: reject prev_main && !curr_main in this half's direction.
 4191374            else if (isMainN != null)
 4181375            {
 4181376                var prevMain = IsMain(edge, localAccess, isMainN);
 4181377                var currMain = IsMain(neighbourEdge, neighbourLocalAccess, isMainN);
 4185378                if (prevMain && !currMain) continue;
 4177379            }
 380
 4952381            var totalCost = cost + neighbourCost + turnCost;
 5053382            if (totalCost >= bestCost) continue;
 383
 4851384            var neighbourPointer = Tree.AddVisit(probe, leftMain: false, localAccess: neighbourLocalAccess, entry.pointe
 385
 386            // Meeting check against the other half's settled set BEFORE pushing — mirrors the
 387            // existing vertex-based pattern's OnQueued hook.
 4851388            onReached?.Invoke(neighbourEdge, probe.Forward, probe.HeadOrder, neighbourPointer,
 4851389                totalCost, probe.Head);
 4851390            onRelaxed?.Invoke(edge, vertex, neighbourEdge);
 391
 4851392            this.PushCounted((neighbourPointer, neighbourEdge, probe.Head, totalCost),
 4851393                totalCost + Potential(potential, probe), neighbourLocalAccess);
 4851394        }
 395
 2373396        return key;
 2373397    }
 398
 399    /// The half's potential at the edge's head; 0 without one. HeadLocation is memoised.
 400    private static double Potential(HeuristicFunc? potential, RoutingNetworkEdgeEnumerator enumerator)
 5297401    {
 10570402        if (potential == null) return 0d;
 403
 24404        var (longitude, latitude, _) = enumerator.HeadLocation;
 24405        return potential(longitude, latitude);
 5297406    }
 407
 408    /// <summary>
 409    /// The turn where one half's arrival continues into the other's. Neither half charged it: the
 410    /// turn only exists once the two are composed, which also inverts pathOutgoing's direction.
 411    /// </summary>
 412    /// <returns><see cref="double.MaxValue"/> when the turn is forbidden or the edge is gone.</returns>
 413    internal static double TurnCostBetween(
 414        RoutingNetworkEdgeEnumerator enumerator,
 415        ICostFunction costFunction,
 416        EdgeId pathIncoming,
 417        byte? pathIncomingHeadOrder,
 418        EdgeId pathOutgoing,
 419        bool pathOutgoingForwardFromOther)
 151420    {
 421        // Position at the outgoing edge in path-outgoing direction (the shared vertex is tail).
 151422        if (!enumerator.MoveTo(pathOutgoing, !pathOutgoingForwardFromOther)) return double.MaxValue;
 423
 151424        var previous = pathIncomingHeadOrder.HasValue
 151425            ? PreviousEdgeEnumerable.ForEdge(pathIncoming, pathIncomingHeadOrder)
 151426            : default;
 151427        var (_, _, _, _, turnCost) = costFunction.Get(enumerator, tailToHead: true, previous);
 151428        return turnCost;
 151429    }
 430
 431    private static bool IsMain(EdgeId edgeId, bool localAccess, IsMainNFunc isMainN)
 8362432    {
 8362433        var verdict = isMainN(edgeId, localAccess);
 434        // Without a leftMain state-bit the bidirectional defaults unknown to "main": the per-half
 435        // rule then doesn't spuriously reject across edges we know nothing about.
 8362436        return verdict ?? true;
 8362437    }
 438}
 439
 440/// <summary>
 441/// Notifies that a half has reached a state — settled it, or queued it.
 442/// </summary>
 443internal delegate void ReachedCallback(
 444    EdgeId edge, bool forward, byte? headOrder, uint pointer, double cost, VertexId vertex);
 445
 446/// <summary>
 447/// Invoked for every relaxation, improving or not: filtering to improvements would describe a
 448/// tree rather than a graph. By value, since a path-tree pointer means nothing to an outside
 449/// caller, and without costs, which the two halves measure in opposite directions.
 450/// </summary>
 451/// <param name="turnVertex">Where the two edges meet, in this half's direction of travel.</param>
 452internal delegate void RelaxedCallback(EdgeId fromEdge, VertexId turnVertex, EdgeId toEdge);
 453
 454/// <summary>
 455/// One arrival at a vertex, recorded so the other half can ask whether it may meet here.
 456/// </summary>
 457internal readonly record struct SettledEntry(
 458    EdgeId Edge, bool Forward, byte? HeadOrder, uint Pointer, double Cost);