< Summary

Class:Itinero.Network.Search.Islands.IslandClassifier
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/IslandClassifier.cs
Covered lines:330
Uncovered lines:0
Coverable lines:330
Total lines:596
Line coverage:100% (330 of 330)
Covered branches:190
Total branches:214
Branch coverage:88.7% (190 of 214)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
ClassifyAsync(...)100%2100%
ClassifyAsync()85.71%42100%
BuildForTileAsync(...)100%1100%
BuildForTileAsync()50%4100%
BuildForTileInsideSerialiserAsync()87.5%40100%
IsKnownIsland(...)66.66%6100%
SetIsland(...)100%2100%
.ctor(...)100%1100%
ProcessEdgeAsync()66.66%6100%
ProcessAtEndpointAsync()86.84%38100%
AddLinkAndPropagate(...)96.15%26100%
PropagateForward(...)100%10100%
PropagateBackward(...)100%10100%
EnqueueMembers(...)100%10100%
RekeyAfterMerge(...)100%1100%
Rekey(...)100%10100%
SetEquals(...)83.33%6100%
MaybeCollapse(...)100%2100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/IslandClassifier.cs

#LineLine coverage
 1using System.Collections.Generic;
 2using System.Threading;
 3using System.Threading.Tasks;
 4using Itinero.Network.Enumerators.Edges;
 5using Itinero.Network.Tiles;
 6using Itinero.Profiles;
 7using Itinero.Routing.Costs;
 8
 9namespace Itinero.Network.Search.Islands;
 10
 11/// <summary>
 12/// Per-edge island classifier. See <c>docs/island-detection-algorithm.md</c>
 13/// in publish-api for the spec. Short version:
 14///
 15/// We answer two reachability questions for the seed in the dg:
 16///   - Forward:  is there a path  seed ↝ sentinel  (seed reaches MainNet)?
 17///   - Backward: is there a path  sentinel ↝ seed  (MainNet reaches seed)?
 18///
 19/// NotIsland iff both are yes; Island iff either is no. Two BFS searches
 20/// (forward + backward) run concurrently. After every <see cref="IslandDirectedGraph.AddDirectedLink"/>
 21/// we propagate two per-component sticky sets:
 22///   - <c>inForward</c>  — components reachable from seed via <c>_outgoing</c>.
 23///   - <c>inBackward</c> — components reachable from seed via <c>_incoming</c>.
 24/// Each component enters each set at most once, so total propagation across
 25/// the classification is O(closure-size).
 26///
 27/// Termination:
 28///   - sentinel ∈ inForward ∩ inBackward  →  NotIsland.
 29///   - forwardQueue empty ∧ sentinel ∉ inForward  →  Island.
 30///   - backwardQueue empty ∧ sentinel ∉ inBackward →  Island.
 31/// </summary>
 32public static class IslandClassifier
 33{
 34    /// <summary>
 35    /// Classifies a single seed with its own graphs. For callers with no snapping
 36    /// request to borrow from — tests and diagnostics.
 37    /// </summary>
 38    public static Task<IslandStatus> ClassifyAsync(
 39        RoutingNetwork network,
 40        Profile profile,
 41        EdgeId seed,
 42        CancellationToken cancellationToken,
 43        IslandKind kind = IslandKind.Full) =>
 4344        ClassifyAsync(network, profile, seed, new IslandDirectedGraph(),
 4345            kind == IslandKind.Full ? new IslandDirectedGraph() : null,
 4346            new HashSet<EdgeId>(), cancellationToken, kind);
 47
 48    internal static async Task<IslandStatus> ClassifyAsync(
 49        RoutingNetwork network,
 50        Profile profile,
 51        EdgeId seed,
 52        IslandDirectedGraph dg,
 53        IslandDirectedGraph? nonLocalDg,
 54        ISet<EdgeId> nonLocalIslandEdges,
 55        CancellationToken cancellationToken,
 56        IslandKind kind = IslandKind.Full)
 233657    {
 233658        var islands = network.IslandManager.GetIslandsFor(profile);
 233659        var maxIslandSize = network.IslandManager.MaxIslandSize;
 233660        var costFunction = IslandKindCostFunctions.GetFor(network, profile, kind);
 233661        var probe = network.GetEdgeEnumerator();
 233662        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 63
 64        // Pre-population secondary oracle for Full: any edge in the NonLocal
 65        // MainNet sentinel is guaranteed to be in Full MainNet too, since
 66        // N-only paths are valid Full paths.
 348167        if (kind != IslandKind.Full) nonLocalDg = null;
 68
 69        // Oracle / cached-state short-circuits.
 233870        if (IsKnownIsland(seed, kind, islands, nonLocalIslandEdges)) return IslandStatus.Island;
 329571        if (dg.IsNotIsland(seed)) return IslandStatus.NotIsland;
 137372        if (nonLocalDg != null && nonLocalDg.IsNotIsland(seed))
 113273        {
 113274            dg.AddVertex(seed);
 113275            dg.CollapseToMainNetwork(seed);
 113276            return IslandStatus.NotIsland;
 77        }
 78
 79        // Edge must exist and be traversable in at least one direction.
 24180        if (!probe.MoveTo(seed, true)) return IslandStatus.Unknown;
 24181        var seedHead = probe.Head;
 24182        var seedTail = probe.Tail;
 24183        var canFwd = costFunction.GetIslandBuilderCost(probe);
 24184        if (!probe.MoveTo(seed, false)) return IslandStatus.Unknown;
 24185        var canBwd = costFunction.GetIslandBuilderCost(probe);
 24486        if (!canFwd && !canBwd) return IslandStatus.Unknown;
 87
 88        // Set up. Seed starts in both F and B (it is trivially reachable from itself in either direction).
 23889        dg.AddVertex(seed);
 23890        var ctx = new Ctx(network, dg, nonLocalDg, kind, islands, costFunction, maxIslandSize,
 23891            nonLocalIslandEdges);
 23892        ctx.InForward.Add(dg.Find(seed));
 23893        ctx.InBackward.Add(dg.Find(seed));
 94
 95        // Process seed at both endpoints. Each AddDirectedLink inside
 96        // ProcessAtEndpointAsync updates inForward/inBackward and enqueues
 97        // newly-marked edges into the right queue.
 23898        await ProcessAtEndpointAsync(seed, seedHead, ctx, cancellationToken);
 23899        if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 238100        await ProcessAtEndpointAsync(seed, seedTail, ctx, cancellationToken);
 238101        if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 238102        dg.SetProcessed(seed);
 103
 104        // Main loop: termination checks are O(1) lookups on the sentinel.
 1165105        while (true)
 1165106        {
 107            // Graduation: if seed was absorbed into the sentinel by an eager
 108            // cycle-merge or size-threshold collapse, return immediately.
 1368109            if (dg.IsNotIsland(seed)) return IslandStatus.NotIsland;
 110
 962111            var sentinelInF = ctx.InForward.Contains(sentinel);
 962112            var sentinelInB = ctx.InBackward.Contains(sentinel);
 962113            if (sentinelInF && sentinelInB)
 2114            {
 2115                dg.CollapseToMainNetwork(seed);
 2116                return IslandStatus.NotIsland;
 117            }
 960118            if (ctx.ForwardQueue.Count == 0 && !sentinelInF)
 29119            {
 29120                SetIsland(seed, kind, islands, nonLocalIslandEdges);
 29121                return IslandStatus.Island;
 122            }
 931123            if (ctx.BackwardQueue.Count == 0 && !sentinelInB)
 4124            {
 4125                SetIsland(seed, kind, islands, nonLocalIslandEdges);
 4126                return IslandStatus.Island;
 127            }
 128
 927129            if (ctx.ForwardQueue.Count > 0)
 927130            {
 927131                var e = ctx.ForwardQueue.Dequeue();
 927132                await ProcessEdgeAsync(e, ctx, cancellationToken);
 927133                if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 927134            }
 927135            if (ctx.BackwardQueue.Count > 0)
 927136            {
 927137                var e = ctx.BackwardQueue.Dequeue();
 927138                await ProcessEdgeAsync(e, ctx, cancellationToken);
 927139                if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 927140            }
 927141        }
 2336142    }
 143
 144    /// <summary>
 145    /// Classifies a tile with its own graphs. For callers with no snapping request to
 146    /// borrow from — tests and diagnostics. The snapping path passes its own pair so
 147    /// one request's tiles share resolved state.
 148    /// </summary>
 149    public static Task BuildForTileAsync(
 150        RoutingNetwork network,
 151        Profile profile,
 152        uint tileId,
 153        CancellationToken cancellationToken) =>
 53154        BuildForTileAsync(network, profile, tileId,
 53155            new IslandDirectedGraph(), new IslandDirectedGraph(), cancellationToken);
 156
 157    internal static async Task BuildForTileAsync(
 158        RoutingNetwork network,
 159        Profile profile,
 160        uint tileId,
 161        IslandDirectedGraph dgFull,
 162        IslandDirectedGraph dgNonLocal,
 163        CancellationToken cancellationToken)
 60164    {
 60165        if (cancellationToken.IsCancellationRequested) return;
 166
 60167        var islands = network.IslandManager.GetIslandsFor(profile);
 60168        if (islands.GetTileDone(tileId)) return;
 169
 170        // No serialiser. The graphs are owned by the calling request, so two
 171        // requests classifying different tiles have nothing to clobber, and two
 172        // asking for the SAME tile are already deduped upstream by the Lazy<Task>.
 60173        await BuildForTileInsideSerialiserAsync(network, profile, tileId, islands,
 60174            dgFull, dgNonLocal, cancellationToken);
 60175    }
 176
 177    private static async Task BuildForTileInsideSerialiserAsync(
 178        RoutingNetwork network,
 179        Profile profile,
 180        uint tileId,
 181        Islands islands,
 182        IslandDirectedGraph dgFull,
 183        IslandDirectedGraph dgNonLocal,
 184        CancellationToken cancellationToken)
 60185    {
 186        // Use the Full cost function to enumerate traversable edges and to
 187        // detect L-tagged ones (NonLocalCostFunction masks L away — we need
 188        // the raw tag here for both edge-gathering and L-set computation).
 60189        var fullCostFunction = IslandKindCostFunctions.GetFor(network, profile, IslandKind.Full);
 60190        await network.UsageNotifier.NotifyVertex(network, new VertexId(tileId, 0), cancellationToken);
 60191        if (cancellationToken.IsCancellationRequested) return;
 60192        var tile = network.GetTileForRead(tileId);
 60193        if (tile == null) return;
 194
 60195        var probe = network.GetEdgeEnumerator();
 60196        var tileEnum = new NetworkTileEnumerator();
 60197        tileEnum.MoveTo(tile);
 60198        var v = new VertexId(tileId, 0);
 60199        var edges = new List<EdgeId>();
 60200        var lEdges = new HashSet<EdgeId>();
 774201        while (tileEnum.MoveTo(v))
 714202        {
 3005203            while (tileEnum.MoveNext())
 2291204            {
 3441205                if (!tileEnum.Forward) continue;
 1141206                var edgeId = tileEnum.EdgeId;
 1141207                if (!probe.MoveTo(edgeId, true)) continue;
 1141208                var fwd = fullCostFunction.Get(probe, true);
 1141209                var canFwd = fwd is { canAccess: true, turnCost: < double.MaxValue };
 1141210                if (!probe.MoveTo(edgeId, false)) continue;
 1141211                var bwd = fullCostFunction.Get(probe, true);
 1141212                var canBwd = bwd is { canAccess: true, turnCost: < double.MaxValue };
 2282213                if (canFwd || canBwd) edges.Add(edgeId);
 1143214                if (fwd.localAccess || bwd.localAccess) lEdges.Add(edgeId);
 1141215            }
 714216            v = new VertexId(tileId, v.LocalId + 1);
 714217        }
 218
 219        // The NonLocal island set belongs to this tile's classification. It used to live on
 220        // the shared Islands and be cleared at the end of each tile, which only worked while
 221        // a semaphore guaranteed one classification at a time.
 60222        var nonLocalIslandEdges = new HashSet<EdgeId>();
 223
 224        // NonLocal pass first — classifies the N-only subgraph. L-tagged
 225        // seeds are masked out by NonLocalCostFunction and return Unknown.
 2462226        foreach (var edge in edges)
 1141227        {
 1141228            if (cancellationToken.IsCancellationRequested) return;
 1141229            await ClassifyAsync(network, profile, edge, dgNonLocal, null, nonLocalIslandEdges,
 1141230                cancellationToken, IslandKind.NonLocal);
 1141231        }
 232
 233        // Full pass — reuses NonLocal MainNet as a positive oracle to short-
 234        // circuit edges already known to be in N-mainland.
 2462235        foreach (var edge in edges)
 1141236        {
 1141237            if (cancellationToken.IsCancellationRequested) return;
 1141238            await ClassifyAsync(network, profile, edge, dgFull, dgNonLocal, nonLocalIslandEdges,
 1141239                cancellationToken, IslandKind.Full);
 1141240        }
 241
 242        // Locals = NonLocal-Island ∩ Full-NotIsland ∩ non-L. These are the
 243        // non-L edges only reachable from main-N through an L-edge first.
 244        // L-tagged edges and Full-Island edges are excluded.
 2462245        foreach (var edge in edges)
 1141246        {
 1143247            if (lEdges.Contains(edge)) continue;
 1141248            if (islands.IsEdgeOnIsland(edge)) continue;
 2268249            if (!nonLocalIslandEdges.Contains(edge)) continue;
 6250            islands.SetEdgeLocal(edge);
 6251        }
 252
 253        // Nothing shared to clear: the NonLocal set goes out of scope with this call.
 60254        islands.SetTileDone(tileId);
 255
 256        // No discard: the graphs belong to the request, not the process, so they
 257        // are bounded by the tiles one snap touches and are released with it. That
 258        // bound is what the per-tile wipe was standing in for — it existed because
 259        // a process-lifetime graph grew until AddDirectedLink's O(V+E) BFS took
 260        // minutes. Keeping them across the request's tiles is the point: an edge
 261        // resolved for one tile still answers for the next.
 60262    }
 263
 264    /// <summary>
 265    /// Kind-aware "known island" oracle. For Full this is the persistent
 266    /// Full-Islands set. For NonLocal an edge is known to be a NonLocal-Island
 267    /// if it is in Full-Islands (Full-Island ⟹ NonLocal-Island), in
 268    /// <c>_localEdges</c> (Local edges are unreachable via N-only paths), or
 269    /// in the transient <c>_nonLocalIslandEdges</c> set written during the
 270    /// current NonLocal pass.
 271    /// </summary>
 272    private static bool IsKnownIsland(EdgeId edgeId, IslandKind kind, Islands islands,
 273        ISet<EdgeId> nonLocalIslandEdges)
 71202274    {
 71202275        if (kind == IslandKind.NonLocal)
 69622276        {
 69622277            if (islands.IsEdgeOnIsland(edgeId)) return true;
 69622278            if (islands.IsEdgeLocal(edgeId)) return true;
 69622279            return nonLocalIslandEdges.Contains(edgeId);
 280        }
 1580281        return islands.IsEdgeOnIsland(edgeId);
 71202282    }
 283
 284    /// <summary>
 285    /// Full verdicts are durable and shared; NonLocal ones are the intermediate used to
 286    /// compute locals for this tile and belong to this classification alone. They used to
 287    /// live in Islands and be cleared at the end of each tile, which is safe only while
 288    /// one classification runs at a time — a concurrent tile's clear wiped them mid-pass.
 289    /// </summary>
 290    private static void SetIsland(EdgeId edge, IslandKind kind, Islands islands,
 291        ISet<EdgeId> nonLocalIslandEdges)
 33292    {
 33293        if (kind == IslandKind.NonLocal)
 11294        {
 11295            nonLocalIslandEdges.Add(edge);
 11296            return;
 297        }
 298
 22299        islands.SetEdgeOnIsland(edge);
 33300    }
 301
 302    /// <summary>
 303    /// Per-classification working state. Owns the two queues, the per-queue
 304    /// dedup sets, and the F/B sticky sets used to track per-component
 305    /// reachability to/from the seed in the dg.
 306    /// </summary>
 307    private sealed class Ctx
 308    {
 309        public readonly RoutingNetwork Network;
 310        public readonly IslandDirectedGraph Dg;
 311        public readonly IslandDirectedGraph? NonLocalDg;
 312        public readonly IslandKind Kind;
 313        public readonly Islands Islands;
 314        public readonly ICostFunction CostFunction;
 315        public readonly int MaxIslandSize;
 238316        public readonly Queue<EdgeId> ForwardQueue = new();
 238317        public readonly Queue<EdgeId> BackwardQueue = new();
 238318        public readonly HashSet<EdgeId> QueuedForward = new();
 238319        public readonly HashSet<EdgeId> QueuedBackward = new();
 238320        public readonly HashSet<EdgeId> InForward = new();
 238321        public readonly HashSet<EdgeId> InBackward = new();
 322
 323        // Scoped to one tile classification, not shared on Islands.
 324        public readonly ISet<EdgeId> NonLocalIslandEdges;
 325
 326        // Scratch for EnqueueMembers, so reading a component's members does not allocate.
 238327        public readonly List<EdgeId> MemberBuffer = new();
 328
 238329        public Ctx(RoutingNetwork network, IslandDirectedGraph dg,
 238330            IslandDirectedGraph? nonLocalDg, IslandKind kind, Islands islands,
 238331            ICostFunction costFunction, int maxIslandSize, ISet<EdgeId> nonLocalIslandEdges)
 238332        {
 238333            NonLocalIslandEdges = nonLocalIslandEdges;
 238334            Network = network;
 238335            Dg = dg;
 238336            NonLocalDg = nonLocalDg;
 238337            Kind = kind;
 238338            Islands = islands;
 238339            CostFunction = costFunction;
 238340            MaxIslandSize = maxIslandSize;
 238341        }
 342    }
 343
 344    private static async Task ProcessEdgeAsync(EdgeId edgeId, Ctx ctx, CancellationToken cancellationToken)
 1854345    {
 2784346        if (ctx.Dg.IsProcessed(edgeId)) return;
 924347        var probe = ctx.Network.GetEdgeEnumerator();
 924348        if (!probe.MoveTo(edgeId, true)) { ctx.Dg.SetProcessed(edgeId); return; }
 924349        var head = probe.Head;
 924350        var tail = probe.Tail;
 924351        await ProcessAtEndpointAsync(edgeId, head, ctx, cancellationToken);
 924352        if (cancellationToken.IsCancellationRequested) return;
 924353        await ProcessAtEndpointAsync(edgeId, tail, ctx, cancellationToken);
 924354        ctx.Dg.SetProcessed(edgeId);
 1854355    }
 356
 357    private static async Task ProcessAtEndpointAsync(
 358        EdgeId edgeId, VertexId vertex, Ctx ctx, CancellationToken cancellationToken)
 2324359    {
 2324360        await ctx.Network.UsageNotifier.NotifyVertex(ctx.Network, vertex, cancellationToken);
 2324361        if (cancellationToken.IsCancellationRequested) return;
 362
 2324363        var edgeIdFrom = ctx.Network.GetEdgeEnumerator();
 2324364        if (!edgeIdFrom.MoveTo(edgeId, true)) return;
 2324365        var arrivalForward = edgeIdFrom.Head == vertex;
 2324366        if (!arrivalForward)
 1162367        {
 1162368            if (!edgeIdFrom.MoveTo(edgeId, false)) return;
 1162369        }
 2324370        var edgeIdTo = ctx.Network.GetEdgeEnumerator();
 2324371        if (!edgeIdTo.MoveTo(edgeId, !arrivalForward)) return;
 2324372        var neighborArriving = ctx.Network.GetEdgeEnumerator();
 373
 2324374        var enumerator = ctx.Network.GetEdgeEnumerator();
 2324375        if (!enumerator.MoveTo(vertex)) return;
 10578376        while (enumerator.MoveNext())
 8254377        {
 10578378            if (enumerator.EdgeId == edgeId) continue;
 5930379            var neighborId = enumerator.EdgeId;
 5930380            var iterationForward = enumerator.Forward;
 381
 5930382            var canGoTo = ctx.CostFunction.GetIslandBuilderCost(edgeIdFrom, enumerator);
 5930383            neighborArriving.MoveTo(neighborId, !iterationForward);
 5930384            var canComeFrom = ctx.CostFunction.GetIslandBuilderCost(neighborArriving, edgeIdTo);
 385
 5930386            enumerator.MoveTo(vertex);
 14445387            while (enumerator.MoveNext())
 14445388            {
 20375389                if (enumerator.EdgeId == neighborId) break;
 8515390            }
 391
 5943392            if (!canGoTo && !canComeFrom) continue;
 393
 394            // Oracle.
 395            EdgeId neighborDgVertex;
 396            bool isKnown;
 5917397            if (IsKnownIsland(neighborId, ctx.Kind, ctx.Islands, ctx.NonLocalIslandEdges))
 13398            {
 13399                ctx.Dg.AddVertex(neighborId);
 13400                neighborDgVertex = neighborId;
 13401                isKnown = true;
 13402            }
 5904403            else if (ctx.Dg.IsNotIsland(neighborId) ||
 5904404                     (ctx.NonLocalDg != null && ctx.NonLocalDg.IsNotIsland(neighborId)) ||
 5904405                     ctx.Islands.GetTileDone(neighborId.TileId))
 359406            {
 359407                neighborDgVertex = IslandDirectedGraph.MainNetworkSentinel;
 359408                isKnown = true;
 359409            }
 410            else
 5545411            {
 5545412                ctx.Dg.AddVertex(neighborId);
 5545413                neighborDgVertex = neighborId;
 5545414                isKnown = false;
 5545415            }
 416
 11745417            if (canGoTo) AddLinkAndPropagate(edgeId, neighborDgVertex, ctx);
 11747418            if (canComeFrom) AddLinkAndPropagate(neighborDgVertex, edgeId, ctx);
 419
 420            // The neighbour's queue assignment is handled by the propagation
 421            // (newly inForward → forwardQueue; newly inBackward → backwardQueue).
 422            // For known-island neighbours nothing needs to be queued; the dg
 423            // link still got added so cycle detection sees it.
 5917424            _ = isKnown;
 5917425        }
 2324426    }
 427
 428    /// <summary>
 429    /// Adds a directed link <c>a → b</c> to the dg and incrementally maintains
 430    /// the per-classification <see cref="Ctx.InForward"/> and
 431    /// <see cref="Ctx.InBackward"/> sets through any propagation the new link
 432    /// causes. Newly-marked components are enqueued to the appropriate queue.
 433    /// </summary>
 434    private static void AddLinkAndPropagate(EdgeId a, EdgeId b, Ctx ctx)
 11658435    {
 11658436        var aRootBefore = ctx.Dg.Find(a);
 11658437        var bRootBefore = ctx.Dg.Find(b);
 19950438        if (aRootBefore == bRootBefore) return;
 439
 440        // Capture F/B membership of both endpoints BEFORE the link is added.
 441        // If the call causes a cycle-merge, the original roots disappear and
 442        // we'll need to consolidate.
 3366443        var aInF = ctx.InForward.Contains(aRootBefore);
 3366444        var bInF = ctx.InForward.Contains(bRootBefore);
 3366445        var aInB = ctx.InBackward.Contains(aRootBefore);
 3366446        var bInB = ctx.InBackward.Contains(bRootBefore);
 447
 3366448        var merged = ctx.Dg.AddDirectedLink(a, b);
 5002449        if (merged) MaybeCollapse(ctx.Dg, a, ctx.MaxIslandSize);
 450
 3366451        if (merged)
 1636452        {
 453            // Cycle close: a and b (and possibly others) are now one component.
 454            // Combine F/B membership into the new root and propagate.
 1636455            RekeyAfterMerge(ctx);
 1636456            var newRoot = ctx.Dg.Find(a);
 1636457            var nowInF = aInF || bInF;
 1636458            var nowInB = aInB || bInB;
 459
 1636460            if (nowInF)
 1624461            {
 1624462                ctx.InForward.Add(newRoot);
 463                // The merge can absorb previously-isolated components whose
 464                // members were never queued (because they weren't in F yet).
 465                // Re-enqueue idempotently — `queuedForward` dedups.
 1624466                EnqueueMembers(newRoot, ctx.ForwardQueue, ctx.QueuedForward, ctx);
 467                // Outgoing chains from the new root may lead to components
 468                // that weren't in F before; propagate into each.
 5228469                foreach (var t in ctx.Dg.GetOutgoingRoots(newRoot))
 178470                {
 178471                    if (!ctx.InForward.Contains(ctx.Dg.Find(t))) PropagateForward(t, ctx);
 178472                }
 1624473            }
 1636474            if (nowInB)
 1627475            {
 1627476                ctx.InBackward.Add(newRoot);
 1627477                EnqueueMembers(newRoot, ctx.BackwardQueue, ctx.QueuedBackward, ctx);
 5241478                foreach (var s in ctx.Dg.GetIncomingRoots(newRoot))
 180479                {
 183480                    if (!ctx.InBackward.Contains(ctx.Dg.Find(s))) PropagateBackward(s, ctx);
 180481                }
 1627482            }
 1636483        }
 484        else
 1730485        {
 486            // Plain link added (no merge). Propagate F/B across it if applicable.
 487            //   - If a was in F, b's outgoing closure joins F.
 488            //   - If b was in B, a's incoming closure joins B.
 3368489            if (aInF && !bInF) PropagateForward(bRootBefore, ctx);
 1760490            if (bInB && !aInB) PropagateBackward(aRootBefore, ctx);
 1730491        }
 11658492    }
 493
 494    /// <summary>
 495    /// BFS from <paramref name="fromRoot"/> through <c>_outgoing</c> chains,
 496    /// marking newly-reached components as <c>inForward</c> and enqueueing
 497    /// their unprocessed members to the forward queue. Each component enters
 498    /// <c>inForward</c> at most once.
 499    /// </summary>
 500    private static void PropagateForward(EdgeId fromRoot, Ctx ctx)
 1638501    {
 1638502        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 1638503        var stack = new Stack<EdgeId>();
 1638504        stack.Push(fromRoot);
 3279505        while (stack.Count > 0)
 1641506        {
 1641507            var current = ctx.Dg.Find(stack.Pop());
 1641508            if (!ctx.InForward.Add(current)) continue;
 509
 1641510            if (current != sentinel)
 1523511            {
 1523512                EnqueueMembers(current, ctx.ForwardQueue, ctx.QueuedForward, ctx);
 1523513            }
 514
 4929515            foreach (var t in ctx.Dg.GetOutgoingRoots(current))
 3516            {
 6517                if (!ctx.InForward.Contains(ctx.Dg.Find(t))) stack.Push(t);
 3518            }
 1641519        }
 1638520    }
 521
 522    /// <summary>
 523    /// Mirror of <see cref="PropagateForward"/> walking <c>_incoming</c>.
 524    /// </summary>
 525    private static void PropagateBackward(EdgeId fromRoot, Ctx ctx)
 33526    {
 33527        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 33528        var stack = new Stack<EdgeId>();
 33529        stack.Push(fromRoot);
 78530        while (stack.Count > 0)
 45531        {
 45532            var current = ctx.Dg.Find(stack.Pop());
 45533            if (!ctx.InBackward.Add(current)) continue;
 534
 45535            if (current != sentinel)
 41536            {
 41537                EnqueueMembers(current, ctx.BackwardQueue, ctx.QueuedBackward, ctx);
 41538            }
 539
 159540            foreach (var s in ctx.Dg.GetIncomingRoots(current))
 12541            {
 24542                if (!ctx.InBackward.Contains(ctx.Dg.Find(s))) stack.Push(s);
 12543            }
 45544        }
 33545    }
 546
 547    private static void EnqueueMembers(EdgeId root, Queue<EdgeId> queue, HashSet<EdgeId> queued, Ctx ctx)
 4815548    {
 549        // Reused buffer owned by the classification; EnqueueMembers is never nested.
 5300550        if (!ctx.Dg.GetMembersInto(root, ctx.MemberBuffer)) return;
 138888551        foreach (var m in ctx.MemberBuffer)
 62949552        {
 62949553            if (ctx.Dg.IsProcessed(m)) continue;
 554            // Don't queue known-island members. They were added to the dg only
 555            // so cycle detection sees them; we never expand through them.
 62957556            if (IsKnownIsland(m, ctx.Kind, ctx.Islands, ctx.NonLocalIslandEdges)) continue;
 122678557            if (!queued.Add(m)) continue;
 3204558            queue.Enqueue(m);
 3204559        }
 4815560    }
 561
 562    /// <summary>
 563    /// Re-canonicalise the F and B sets after a merge. Each set's entries are
 564    /// component roots; a merge can collapse multiple of them into one. We
 565    /// replace stale entries with their current <see cref="Find"/> result and
 566    /// dedup.
 567    /// </summary>
 568    private static void RekeyAfterMerge(Ctx ctx)
 1636569    {
 1636570        Rekey(ctx.InForward, ctx.Dg);
 1636571        Rekey(ctx.InBackward, ctx.Dg);
 1636572    }
 573
 574    private static void Rekey(HashSet<EdgeId> set, IslandDirectedGraph dg)
 3272575    {
 3272576        if (set.Count == 0) return;
 3272577        var fresh = new HashSet<EdgeId>(set.Count);
 25842578        foreach (var r in set) fresh.Add(dg.Find(r));
 4573579        if (fresh.Count == set.Count && SetEquals(fresh, set)) return;
 1971580        set.Clear();
 12480581        foreach (var r in fresh) set.Add(r);
 3272582    }
 583
 584    private static bool SetEquals(HashSet<EdgeId> a, HashSet<EdgeId> b)
 1640585    {
 1640586        if (a.Count != b.Count) return false;
 10497587        foreach (var x in a) if (!b.Contains(x)) return false;
 1301588        return true;
 1640589    }
 590
 591    private static void MaybeCollapse(IslandDirectedGraph dg, EdgeId a, int maxIslandSize)
 1636592    {
 1636593        var size = dg.GetSize(dg.Find(a));
 1884594        if (size >= maxIslandSize) dg.CollapseToMainNetwork(a);
 1636595    }
 596}