< Summary

Class:Itinero.Routing.Flavours.Dijkstra.Bidirectional.SettledEntry
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Flavours/Dijkstra/Bidirectional/SearchHalf.cs
Covered lines:1
Uncovered lines:0
Coverable lines:1
Total lines:458
Line coverage:100% (1 of 1)
Covered branches:0
Total branches:0
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Edge()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>
 28    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>
 34    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>
 43    public bool ReachedOtherEndpoint { get; private set; }
 44
 45    public SearchHalf(bool isForwardHalf)
 46    {
 47        this.IsForwardHalf = isForwardHalf;
 48    }
 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>
 55    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>
 65    public int LocalOnHeap { get; private set; }
 66
 67    public readonly PathTree Tree = new();
 68
 69    // Carries g because the heap is ordered by g + p; only the stopping rule uses the key.
 70    public readonly BinaryHeap<(uint pointer, EdgeId edge, VertexId vertex, double g)> Heap = new();
 71    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?".
 76    public readonly Dictionary<VertexId, List<SettledEntry>> SettledByVertex = new();
 77
 78    public void Clear()
 79    {
 80        Tree.Clear();
 81        Heap.Clear();
 82        Settled.Clear();
 83        SettledByVertex.Clear();
 84        this.SawLocalAccess = false;
 85        this.LocalOnHeap = 0;
 86        this.ReachedOtherEndpoint = false;
 87    }
 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)
 91    {
 92        var entry = Heap.Pop(out key);
 93        var (_, _, _, _, localAccess, _, _) = Tree.GetVisitWithState(entry.pointer);
 94        if (localAccess) this.LocalOnHeap--;
 95        return entry;
 96    }
 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)
 101    {
 102        if (localAccess) this.LocalOnHeap++;
 103        Heap.Push(entry, key);
 104    }
 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)
 115    {
 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.
 118        foreach (var forward in new[] { true, false })
 119        {
 120            if (!enumerator.MoveTo(snap.EdgeId, forward)) continue;
 121            var (canAccess, _, localAccess, cost, _) = costFunction.Get(enumerator, tailToHead: this.IsForwardHalf);
 122            if (!canAccess || cost <= 0) continue;
 123            var offsetCost = forward
 124                ? cost * (1 - snap.OffsetFactor())
 125                : cost * snap.OffsetFactor();
 126            this.SawLocalAccess |= localAccess;
 127            var p = Tree.AddVisit(enumerator, leftMain: false, localAccess: localAccess, uint.MaxValue);
 128            this.PushCounted((p, enumerator.EdgeId, enumerator.Head, offsetCost),
 129                offsetCost + Potential(potential, enumerator), localAccess);
 130
 131        }
 132    }
 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)
 142    {
 143        if (potential == null || Heap.Count == 0) return;
 144
 145        var entries = new List<(uint pointer, EdgeId edge, VertexId vertex, double g)>(Heap.Count);
 146        while (Heap.Count > 0) entries.Add(Heap.Pop(out _));
 147
 148        var enumerator = network.GetEdgeEnumerator();
 149        foreach (var entry in entries)
 150        {
 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.
 153            var p = 0d;
 154            if (enumerator.MoveTo(entry.edge, true))
 155            {
 156                p = enumerator.Head == entry.vertex
 157                    ? Potential(potential, enumerator)
 158                    : enumerator.MoveTo(entry.edge, false) ? Potential(potential, enumerator) : 0d;
 159            }
 160
 161            Heap.Push(entry, entry.g + p);
 162        }
 163    }
 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)
 185    {
 186        var expanded = 0;
 187        while (Heap.Count > 0)
 188        {
 189            cancellationToken.ThrowIfCancellationRequested();
 190
 191            await this.StepAsync(network, costFunction, isMainN: null, localAccessRule: true,
 192                bestCost: double.MaxValue, settledCb: LoadTileFor, potential: null,
 193                onReached: null, cancellationToken);
 194
 195            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.
 199            if (expanded >= ceiling) return ReachabilityVerdict.BeyondBound;
 200
 201            if (expanded >= threshold && this.LocalOnHeap == 0) return ReachabilityVerdict.BeyondBound;
 202        }
 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.
 206        return ReachabilityVerdict.Island;
 207
 208        async Task<bool> LoadTileFor(VertexId v)
 209        {
 210            if (!network.UsageNotifier.IsVertexDataReady(network, v))
 211            {
 212                await network.UsageNotifier.NotifyVertex(network, v, cancellationToken);
 213            }
 214
 215            return false;
 216        }
 217    }
 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)
 236    {
 237        var expanded = 0;
 238        while (Heap.Count > 0)
 239        {
 240            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.
 244            await this.StepAsync(network, costFunction, isMainN: null, localAccessRule: true,
 245                bestCost: double.MaxValue, settledCb: LoadTileFor, potential: null,
 246                onReached: null, cancellationToken);
 247
 248            expanded++;
 249            if (expanded >= ceiling) return ReachabilityVerdict.BeyondBound;
 250        }
 251
 252        // Ran out of network: everything reachable has been seen and none of it leaves.
 253        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)
 258        {
 259            if (!network.UsageNotifier.IsVertexDataReady(network, v))
 260            {
 261                await network.UsageNotifier.NotifyVertex(network, v, cancellationToken);
 262            }
 263
 264            return false;
 265        }
 266    }
 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)
 280    {
 281        if (_probe != null && ReferenceEquals(_probeNetwork, network)) return _probe;
 282
 283        _probe = network.GetEdgeEnumerator();
 284        _probeNetwork = network;
 285
 286        return _probe;
 287    }
 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)
 311    {
 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.
 315        var entry = this.PopCounted(out var key);
 316        while (Settled.Contains((entry.edge, entry.vertex)))
 317        {
 318            if (Heap.Count == 0) return key;
 319            entry = this.PopCounted(out key);
 320        }
 321        if (!Settled.Add((entry.edge, entry.vertex))) return key;
 322
 323        var cost = entry.g;
 324
 325        var (vertex, edge, forward, _, localAccess, headOrder, _) = Tree.GetVisitWithState(entry.pointer);
 326        this.SawLocalAccess |= localAccess;
 327
 328        if (this.OtherEndpointEdge.HasValue && edge == this.OtherEndpointEdge.Value)
 329        {
 330            this.ReachedOtherEndpoint = true;
 331        }
 332
 333        // Record in per-vertex settled multimap for meeting checks initiated by the other half.
 334        if (!SettledByVertex.TryGetValue(vertex, out var list))
 335        {
 336            list = new List<SettledEntry>(2);
 337            SettledByVertex[vertex] = list;
 338        }
 339        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).
 343        if (settledCb != null && await settledCb(vertex)) return key;
 344        if (cancellationToken.IsCancellationRequested) return key;
 345
 346        onReached?.Invoke(edge, forward, headOrder, entry.pointer, cost, vertex);
 347
 348        // Expand neighbours.
 349        var probe = this.Probe(network);
 350        if (!probe.MoveTo(vertex)) return key;
 351        while (probe.MoveNext())
 352        {
 353            var neighbourEdge = probe.EdgeId;
 354            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.
 358            var prev = new PreviousEdgeEnumerable(Tree, entry.pointer);
 359            var (canAccess, _, neighbourLocalAccess, neighbourCost, turnCost) =
 360                costFunction.Get(probe, tailToHead: this.IsForwardHalf, prev);
 361            if (!canAccess || neighbourCost is >= double.MaxValue or <= 0) continue;
 362            if (turnCost is >= double.MaxValue or < 0) continue;
 363            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.
 367            if (localAccessRule)
 368            {
 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.
 371                if (neighbourLocalAccess && !localAccess) continue;
 372            }
 373            // Per-half access-aware rule: reject prev_main && !curr_main in this half's direction.
 374            else if (isMainN != null)
 375            {
 376                var prevMain = IsMain(edge, localAccess, isMainN);
 377                var currMain = IsMain(neighbourEdge, neighbourLocalAccess, isMainN);
 378                if (prevMain && !currMain) continue;
 379            }
 380
 381            var totalCost = cost + neighbourCost + turnCost;
 382            if (totalCost >= bestCost) continue;
 383
 384            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.
 388            onReached?.Invoke(neighbourEdge, probe.Forward, probe.HeadOrder, neighbourPointer,
 389                totalCost, probe.Head);
 390            onRelaxed?.Invoke(edge, vertex, neighbourEdge);
 391
 392            this.PushCounted((neighbourPointer, neighbourEdge, probe.Head, totalCost),
 393                totalCost + Potential(potential, probe), neighbourLocalAccess);
 394        }
 395
 396        return key;
 397    }
 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)
 401    {
 402        if (potential == null) return 0d;
 403
 404        var (longitude, latitude, _) = enumerator.HeadLocation;
 405        return potential(longitude, latitude);
 406    }
 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)
 420    {
 421        // Position at the outgoing edge in path-outgoing direction (the shared vertex is tail).
 422        if (!enumerator.MoveTo(pathOutgoing, !pathOutgoingForwardFromOther)) return double.MaxValue;
 423
 424        var previous = pathIncomingHeadOrder.HasValue
 425            ? PreviousEdgeEnumerable.ForEdge(pathIncoming, pathIncomingHeadOrder)
 426            : default;
 427        var (_, _, _, _, turnCost) = costFunction.Get(enumerator, tailToHead: true, previous);
 428        return turnCost;
 429    }
 430
 431    private static bool IsMain(EdgeId edgeId, bool localAccess, IsMainNFunc isMainN)
 432    {
 433        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.
 436        return verdict ?? true;
 437    }
 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(
 2055458    EdgeId Edge, bool Forward, byte? HeadOrder, uint Pointer, double Cost);

Methods/Properties

get_Edge()