< 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:549
Line coverage:100% (330 of 330)
Covered branches:187
Total branches:212
Branch coverage:88.2% (187 of 212)
Tag:267_28791001112

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
ClassifyAsync()85.71%42100%
BuildForTileAsync()50%6100%
BuildForTileInsideSerialiserAsync()87.5%40100%
IsKnownIsland(...)66.66%6100%
.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    public static async Task<IslandStatus> ClassifyAsync(
 35        RoutingNetwork network,
 36        Profile profile,
 37        EdgeId seed,
 38        CancellationToken cancellationToken,
 39        IslandKind kind = IslandKind.Full)
 233640    {
 233641        var islands = network.IslandManager.GetIslandsFor(profile);
 233642        var dg = network.IslandManager.GetOrCreateDirectedGraph(profile, kind);
 233643        var maxIslandSize = network.IslandManager.MaxIslandSize;
 233644        var costFunction = IslandKindCostFunctions.GetFor(network, profile, kind);
 233645        var probe = network.GetEdgeEnumerator();
 233646        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 47
 48        // Pre-population secondary oracle for Full: any edge in the NonLocal
 49        // MainNet sentinel is guaranteed to be in Full MainNet too, since
 50        // N-only paths are valid Full paths.
 233651        IslandDirectedGraph? nonLocalDg = null;
 233652        if (kind == IslandKind.Full)
 119153        {
 119154            nonLocalDg = network.IslandManager.GetOrCreateDirectedGraph(profile, IslandKind.NonLocal);
 119155        }
 56
 57        // Oracle / cached-state short-circuits.
 233858        if (IsKnownIsland(seed, kind, islands)) return IslandStatus.Island;
 330459        if (dg.IsNotIsland(seed)) return IslandStatus.NotIsland;
 136460        if (nonLocalDg != null && nonLocalDg.IsNotIsland(seed))
 113261        {
 113262            dg.AddVertex(seed);
 113263            dg.CollapseToMainNetwork(seed);
 113264            return IslandStatus.NotIsland;
 65        }
 66
 67        // Edge must exist and be traversable in at least one direction.
 23268        if (!probe.MoveTo(seed, true)) return IslandStatus.Unknown;
 23269        var seedHead = probe.Head;
 23270        var seedTail = probe.Tail;
 23271        var canFwd = costFunction.GetIslandBuilderCost(probe);
 23272        if (!probe.MoveTo(seed, false)) return IslandStatus.Unknown;
 23273        var canBwd = costFunction.GetIslandBuilderCost(probe);
 23574        if (!canFwd && !canBwd) return IslandStatus.Unknown;
 75
 76        // Set up. Seed starts in both F and B (it is trivially reachable from itself in either direction).
 22977        dg.AddVertex(seed);
 22978        var ctx = new Ctx(network, dg, nonLocalDg, kind, islands, costFunction, maxIslandSize);
 22979        ctx.InForward.Add(dg.Find(seed));
 22980        ctx.InBackward.Add(dg.Find(seed));
 81
 82        // Process seed at both endpoints. Each AddDirectedLink inside
 83        // ProcessAtEndpointAsync updates inForward/inBackward and enqueues
 84        // newly-marked edges into the right queue.
 22985        await ProcessAtEndpointAsync(seed, seedHead, ctx, cancellationToken);
 22986        if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 22987        await ProcessAtEndpointAsync(seed, seedTail, ctx, cancellationToken);
 22988        if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 22989        dg.SetProcessed(seed);
 90
 91        // Main loop: termination checks are O(1) lookups on the sentinel.
 114892        while (true)
 114893        {
 94            // Graduation: if seed was absorbed into the sentinel by an eager
 95            // cycle-merge or size-threshold collapse, return immediately.
 134396            if (dg.IsNotIsland(seed)) return IslandStatus.NotIsland;
 97
 95398            var sentinelInF = ctx.InForward.Contains(sentinel);
 95399            var sentinelInB = ctx.InBackward.Contains(sentinel);
 953100            if (sentinelInF && sentinelInB)
 1101            {
 1102                dg.CollapseToMainNetwork(seed);
 1103                return IslandStatus.NotIsland;
 104            }
 952105            if (ctx.ForwardQueue.Count == 0 && !sentinelInF)
 29106            {
 29107                islands.SetEdgeOnIsland(seed, kind);
 29108                return IslandStatus.Island;
 109            }
 923110            if (ctx.BackwardQueue.Count == 0 && !sentinelInB)
 4111            {
 4112                islands.SetEdgeOnIsland(seed, kind);
 4113                return IslandStatus.Island;
 114            }
 115
 919116            if (ctx.ForwardQueue.Count > 0)
 919117            {
 919118                var e = ctx.ForwardQueue.Dequeue();
 919119                await ProcessEdgeAsync(e, ctx, cancellationToken);
 919120                if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 919121            }
 919122            if (ctx.BackwardQueue.Count > 0)
 917123            {
 917124                var e = ctx.BackwardQueue.Dequeue();
 917125                await ProcessEdgeAsync(e, ctx, cancellationToken);
 917126                if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 917127            }
 919128        }
 2336129    }
 130
 131    public static async Task BuildForTileAsync(
 132        RoutingNetwork network,
 133        Profile profile,
 134        uint tileId,
 135        CancellationToken cancellationToken)
 60136    {
 60137        if (cancellationToken.IsCancellationRequested) return;
 138
 60139        var islands = network.IslandManager.GetIslandsFor(profile);
 60140        if (islands.GetTileDone(tileId)) return;
 141
 142        // Serialise the entire classification+discard for this profile. The
 143        // dg-discard at the end of this method would otherwise be unsafe
 144        // against a concurrent BuildForTileAsync running for the same profile
 145        // on a different tile (it would wipe that other call's mid-flight
 146        // working state). Different profiles still classify in parallel.
 60147        var serialiser = network.IslandManager.GetBuildSerialiser(profile.Name);
 60148        await serialiser.WaitAsync(cancellationToken);
 149        try
 60150        {
 151            // Recheck the done flag now that we hold the serialiser — a
 152            // previous holder may have classified this tile while we waited.
 60153            if (islands.GetTileDone(tileId)) return;
 60154            await BuildForTileInsideSerialiserAsync(network, profile, tileId, islands, cancellationToken);
 60155        }
 156        finally
 60157        {
 60158            serialiser.Release();
 60159        }
 60160    }
 161
 162    private static async Task BuildForTileInsideSerialiserAsync(
 163        RoutingNetwork network,
 164        Profile profile,
 165        uint tileId,
 166        Islands islands,
 167        CancellationToken cancellationToken)
 60168    {
 169        // Use the Full cost function to enumerate traversable edges and to
 170        // detect L-tagged ones (NonLocalCostFunction masks L away — we need
 171        // the raw tag here for both edge-gathering and L-set computation).
 60172        var fullCostFunction = IslandKindCostFunctions.GetFor(network, profile, IslandKind.Full);
 60173        await network.UsageNotifier.NotifyVertex(network, new VertexId(tileId, 0), cancellationToken);
 60174        if (cancellationToken.IsCancellationRequested) return;
 60175        var tile = network.GetTileForRead(tileId);
 60176        if (tile == null) return;
 177
 60178        var probe = network.GetEdgeEnumerator();
 60179        var tileEnum = new NetworkTileEnumerator();
 60180        tileEnum.MoveTo(tile);
 60181        var v = new VertexId(tileId, 0);
 60182        var edges = new List<EdgeId>();
 60183        var lEdges = new HashSet<EdgeId>();
 774184        while (tileEnum.MoveTo(v))
 714185        {
 3005186            while (tileEnum.MoveNext())
 2291187            {
 3441188                if (!tileEnum.Forward) continue;
 1141189                var edgeId = tileEnum.EdgeId;
 1141190                if (!probe.MoveTo(edgeId, true)) continue;
 1141191                var fwd = fullCostFunction.Get(probe, true);
 1141192                var canFwd = fwd is { canAccess: true, turnCost: < double.MaxValue };
 1141193                if (!probe.MoveTo(edgeId, false)) continue;
 1141194                var bwd = fullCostFunction.Get(probe, true);
 1141195                var canBwd = bwd is { canAccess: true, turnCost: < double.MaxValue };
 2282196                if (canFwd || canBwd) edges.Add(edgeId);
 1143197                if (fwd.localAccess || bwd.localAccess) lEdges.Add(edgeId);
 1141198            }
 714199            v = new VertexId(tileId, v.LocalId + 1);
 714200        }
 201
 202        // NonLocal pass first — classifies the N-only subgraph. L-tagged
 203        // seeds are masked out by NonLocalCostFunction and return Unknown.
 2462204        foreach (var edge in edges)
 1141205        {
 1141206            if (cancellationToken.IsCancellationRequested) return;
 1141207            await ClassifyAsync(network, profile, edge, cancellationToken, IslandKind.NonLocal);
 1141208        }
 209
 210        // Full pass — reuses NonLocal MainNet as a positive oracle to short-
 211        // circuit edges already known to be in N-mainland.
 2462212        foreach (var edge in edges)
 1141213        {
 1141214            if (cancellationToken.IsCancellationRequested) return;
 1141215            await ClassifyAsync(network, profile, edge, cancellationToken, IslandKind.Full);
 1141216        }
 217
 218        // Locals = NonLocal-Island ∩ Full-NotIsland ∩ non-L. These are the
 219        // non-L edges only reachable from main-N through an L-edge first.
 220        // L-tagged edges and Full-Island edges are excluded.
 2462221        foreach (var edge in edges)
 1141222        {
 1143223            if (lEdges.Contains(edge)) continue;
 1141224            if (islands.IsEdgeOnIsland(edge)) continue;
 2268225            if (!islands.IsEdgeOnIsland(edge, IslandKind.NonLocal)) continue;
 6226            islands.SetEdgeLocal(edge);
 6227        }
 228
 60229        islands.ClearNonLocalIslandEdges();
 60230        islands.SetTileDone(tileId);
 231
 232        // Per the island-detection spec ("Tile-based batching and persistence",
 233        // step 3): once a tile is committed, discard the tile-local dg
 234        // vertices so the dg never accumulates per-tile edge ids. Without
 235        // this the dg grew unboundedly in long-lived processes, eventually
 236        // making AddDirectedLink's O(V+E) BFS over the dg run for minutes.
 60237        network.IslandManager.GetOrCreateDirectedGraph(profile, IslandKind.Full)
 60238            .DiscardAllExceptSentinel();
 60239        network.IslandManager.GetOrCreateDirectedGraph(profile, IslandKind.NonLocal)
 60240            .DiscardAllExceptSentinel();
 60241    }
 242
 243    /// <summary>
 244    /// Kind-aware "known island" oracle. For Full this is the persistent
 245    /// Full-Islands set. For NonLocal an edge is known to be a NonLocal-Island
 246    /// if it is in Full-Islands (Full-Island ⟹ NonLocal-Island), in
 247    /// <c>_localEdges</c> (Local edges are unreachable via N-only paths), or
 248    /// in the transient <c>_nonLocalIslandEdges</c> set written during the
 249    /// current NonLocal pass.
 250    /// </summary>
 251    private static bool IsKnownIsland(EdgeId edgeId, IslandKind kind, Islands islands)
 71094252    {
 71094253        if (kind == IslandKind.NonLocal)
 69622254        {
 69622255            if (islands.IsEdgeOnIsland(edgeId)) return true;
 69622256            if (islands.IsEdgeLocal(edgeId)) return true;
 69622257            return islands.IsEdgeOnIsland(edgeId, IslandKind.NonLocal);
 258        }
 1472259        return islands.IsEdgeOnIsland(edgeId);
 71094260    }
 261
 262    /// <summary>
 263    /// Per-classification working state. Owns the two queues, the per-queue
 264    /// dedup sets, and the F/B sticky sets used to track per-component
 265    /// reachability to/from the seed in the dg.
 266    /// </summary>
 267    private sealed class Ctx
 268    {
 269        public readonly RoutingNetwork Network;
 270        public readonly IslandDirectedGraph Dg;
 271        public readonly IslandDirectedGraph? NonLocalDg;
 272        public readonly IslandKind Kind;
 273        public readonly Islands Islands;
 274        public readonly ICostFunction CostFunction;
 275        public readonly int MaxIslandSize;
 229276        public readonly Queue<EdgeId> ForwardQueue = new();
 229277        public readonly Queue<EdgeId> BackwardQueue = new();
 229278        public readonly HashSet<EdgeId> QueuedForward = new();
 229279        public readonly HashSet<EdgeId> QueuedBackward = new();
 229280        public readonly HashSet<EdgeId> InForward = new();
 229281        public readonly HashSet<EdgeId> InBackward = new();
 282
 229283        public Ctx(RoutingNetwork network, IslandDirectedGraph dg,
 229284            IslandDirectedGraph? nonLocalDg, IslandKind kind, Islands islands,
 229285            ICostFunction costFunction, int maxIslandSize)
 229286        {
 229287            Network = network;
 229288            Dg = dg;
 229289            NonLocalDg = nonLocalDg;
 229290            Kind = kind;
 229291            Islands = islands;
 229292            CostFunction = costFunction;
 229293            MaxIslandSize = maxIslandSize;
 229294        }
 295    }
 296
 297    private static async Task ProcessEdgeAsync(EdgeId edgeId, Ctx ctx, CancellationToken cancellationToken)
 1836298    {
 2756299        if (ctx.Dg.IsProcessed(edgeId)) return;
 916300        var probe = ctx.Network.GetEdgeEnumerator();
 916301        if (!probe.MoveTo(edgeId, true)) { ctx.Dg.SetProcessed(edgeId); return; }
 916302        var head = probe.Head;
 916303        var tail = probe.Tail;
 916304        await ProcessAtEndpointAsync(edgeId, head, ctx, cancellationToken);
 916305        if (cancellationToken.IsCancellationRequested) return;
 916306        await ProcessAtEndpointAsync(edgeId, tail, ctx, cancellationToken);
 916307        ctx.Dg.SetProcessed(edgeId);
 1836308    }
 309
 310    private static async Task ProcessAtEndpointAsync(
 311        EdgeId edgeId, VertexId vertex, Ctx ctx, CancellationToken cancellationToken)
 2290312    {
 2290313        await ctx.Network.UsageNotifier.NotifyVertex(ctx.Network, vertex, cancellationToken);
 2290314        if (cancellationToken.IsCancellationRequested) return;
 315
 2290316        var edgeIdFrom = ctx.Network.GetEdgeEnumerator();
 2290317        if (!edgeIdFrom.MoveTo(edgeId, true)) return;
 2290318        var arrivalForward = edgeIdFrom.Head == vertex;
 2290319        if (!arrivalForward)
 1145320        {
 1145321            if (!edgeIdFrom.MoveTo(edgeId, false)) return;
 1145322        }
 2290323        var edgeIdTo = ctx.Network.GetEdgeEnumerator();
 2290324        if (!edgeIdTo.MoveTo(edgeId, !arrivalForward)) return;
 2290325        var neighborArriving = ctx.Network.GetEdgeEnumerator();
 326
 2290327        var enumerator = ctx.Network.GetEdgeEnumerator();
 2290328        if (!enumerator.MoveTo(vertex)) return;
 10473329        while (enumerator.MoveNext())
 8183330        {
 10473331            if (enumerator.EdgeId == edgeId) continue;
 5893332            var neighborId = enumerator.EdgeId;
 5893333            var iterationForward = enumerator.Forward;
 334
 5893335            var canGoTo = ctx.CostFunction.GetIslandBuilderCost(edgeIdFrom, enumerator);
 5893336            neighborArriving.MoveTo(neighborId, !iterationForward);
 5893337            var canComeFrom = ctx.CostFunction.GetIslandBuilderCost(neighborArriving, edgeIdTo);
 338
 5893339            enumerator.MoveTo(vertex);
 14382340            while (enumerator.MoveNext())
 14382341            {
 20275342                if (enumerator.EdgeId == neighborId) break;
 8489343            }
 344
 5906345            if (!canGoTo && !canComeFrom) continue;
 346
 347            // Oracle.
 348            EdgeId neighborDgVertex;
 349            bool isKnown;
 5880350            if (IsKnownIsland(neighborId, ctx.Kind, ctx.Islands))
 13351            {
 13352                ctx.Dg.AddVertex(neighborId);
 13353                neighborDgVertex = neighborId;
 13354                isKnown = true;
 13355            }
 5867356            else if (ctx.Dg.IsNotIsland(neighborId) ||
 5867357                     (ctx.NonLocalDg != null && ctx.NonLocalDg.IsNotIsland(neighborId)) ||
 5867358                     ctx.Islands.GetTileDone(neighborId.TileId))
 362359            {
 362360                neighborDgVertex = IslandDirectedGraph.MainNetworkSentinel;
 362361                isKnown = true;
 362362            }
 363            else
 5505364            {
 5505365                ctx.Dg.AddVertex(neighborId);
 5505366                neighborDgVertex = neighborId;
 5505367                isKnown = false;
 5505368            }
 369
 11678370            if (canGoTo) AddLinkAndPropagate(edgeId, neighborDgVertex, ctx);
 11684371            if (canComeFrom) AddLinkAndPropagate(neighborDgVertex, edgeId, ctx);
 372
 373            // The neighbour's queue assignment is handled by the propagation
 374            // (newly inForward → forwardQueue; newly inBackward → backwardQueue).
 375            // For known-island neighbours nothing needs to be queued; the dg
 376            // link still got added so cycle detection sees it.
 5880377            _ = isKnown;
 5880378        }
 2290379    }
 380
 381    /// <summary>
 382    /// Adds a directed link <c>a → b</c> to the dg and incrementally maintains
 383    /// the per-classification <see cref="Ctx.InForward"/> and
 384    /// <see cref="Ctx.InBackward"/> sets through any propagation the new link
 385    /// causes. Newly-marked components are enqueued to the appropriate queue.
 386    /// </summary>
 387    private static void AddLinkAndPropagate(EdgeId a, EdgeId b, Ctx ctx)
 11602388    {
 11602389        var aRootBefore = ctx.Dg.Find(a);
 11602390        var bRootBefore = ctx.Dg.Find(b);
 19884391        if (aRootBefore == bRootBefore) return;
 392
 393        // Capture F/B membership of both endpoints BEFORE the link is added.
 394        // If the call causes a cycle-merge, the original roots disappear and
 395        // we'll need to consolidate.
 3320396        var aInF = ctx.InForward.Contains(aRootBefore);
 3320397        var bInF = ctx.InForward.Contains(bRootBefore);
 3320398        var aInB = ctx.InBackward.Contains(aRootBefore);
 3320399        var bInB = ctx.InBackward.Contains(bRootBefore);
 400
 3320401        var merged = ctx.Dg.AddDirectedLink(a, b);
 4937402        if (merged) MaybeCollapse(ctx.Dg, a, ctx.MaxIslandSize);
 403
 3320404        if (merged)
 1617405        {
 406            // Cycle close: a and b (and possibly others) are now one component.
 407            // Combine F/B membership into the new root and propagate.
 1617408            RekeyAfterMerge(ctx);
 1617409            var newRoot = ctx.Dg.Find(a);
 1617410            var nowInF = aInF || bInF;
 1617411            var nowInB = aInB || bInB;
 412
 1617413            if (nowInF)
 1607414            {
 1607415                ctx.InForward.Add(newRoot);
 416                // The merge can absorb previously-isolated components whose
 417                // members were never queued (because they weren't in F yet).
 418                // Re-enqueue idempotently — `queuedForward` dedups.
 1607419                EnqueueMembers(newRoot, ctx.ForwardQueue, ctx.QueuedForward, ctx);
 420                // Outgoing chains from the new root may lead to components
 421                // that weren't in F before; propagate into each.
 5169422                foreach (var t in ctx.Dg.GetOutgoingRoots(newRoot))
 174423                {
 174424                    if (!ctx.InForward.Contains(ctx.Dg.Find(t))) PropagateForward(t, ctx);
 174425                }
 1607426            }
 1617427            if (nowInB)
 1608428            {
 1608429                ctx.InBackward.Add(newRoot);
 1608430                EnqueueMembers(newRoot, ctx.BackwardQueue, ctx.QueuedBackward, ctx);
 5180431                foreach (var s in ctx.Dg.GetIncomingRoots(newRoot))
 178432                {
 181433                    if (!ctx.InBackward.Contains(ctx.Dg.Find(s))) PropagateBackward(s, ctx);
 178434                }
 1608435            }
 1617436        }
 437        else
 1703438        {
 439            // Plain link added (no merge). Propagate F/B across it if applicable.
 440            //   - If a was in F, b's outgoing closure joins F.
 441            //   - If b was in B, a's incoming closure joins B.
 3321442            if (aInF && !bInF) PropagateForward(bRootBefore, ctx);
 1731443            if (bInB && !aInB) PropagateBackward(aRootBefore, ctx);
 1703444        }
 11602445    }
 446
 447    /// <summary>
 448    /// BFS from <paramref name="fromRoot"/> through <c>_outgoing</c> chains,
 449    /// marking newly-reached components as <c>inForward</c> and enqueueing
 450    /// their unprocessed members to the forward queue. Each component enters
 451    /// <c>inForward</c> at most once.
 452    /// </summary>
 453    private static void PropagateForward(EdgeId fromRoot, Ctx ctx)
 1618454    {
 1618455        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 1618456        var stack = new Stack<EdgeId>();
 1618457        stack.Push(fromRoot);
 3239458        while (stack.Count > 0)
 1621459        {
 1621460            var current = ctx.Dg.Find(stack.Pop());
 1621461            if (!ctx.InForward.Add(current)) continue;
 462
 1621463            if (current != sentinel)
 1503464            {
 1503465                EnqueueMembers(current, ctx.ForwardQueue, ctx.QueuedForward, ctx);
 1503466            }
 467
 4869468            foreach (var t in ctx.Dg.GetOutgoingRoots(current))
 3469            {
 6470                if (!ctx.InForward.Contains(ctx.Dg.Find(t))) stack.Push(t);
 3471            }
 1621472        }
 1618473    }
 474
 475    /// <summary>
 476    /// Mirror of <see cref="PropagateForward"/> walking <c>_incoming</c>.
 477    /// </summary>
 478    private static void PropagateBackward(EdgeId fromRoot, Ctx ctx)
 31479    {
 31480        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 31481        var stack = new Stack<EdgeId>();
 31482        stack.Push(fromRoot);
 75483        while (stack.Count > 0)
 44484        {
 44485            var current = ctx.Dg.Find(stack.Pop());
 44486            if (!ctx.InBackward.Add(current)) continue;
 487
 44488            if (current != sentinel)
 36489            {
 36490                EnqueueMembers(current, ctx.BackwardQueue, ctx.QueuedBackward, ctx);
 36491            }
 492
 158493            foreach (var s in ctx.Dg.GetIncomingRoots(current))
 13494            {
 26495                if (!ctx.InBackward.Contains(ctx.Dg.Find(s))) stack.Push(s);
 13496            }
 44497        }
 31498    }
 499
 500    private static void EnqueueMembers(EdgeId root, Queue<EdgeId> queue, HashSet<EdgeId> queued, Ctx ctx)
 4754501    {
 4754502        var members = ctx.Dg.GetMembers(root);
 5221503        if (members == null) return;
 542923504        foreach (var m in members)
 265031505        {
 467184506            if (ctx.Dg.IsProcessed(m)) continue;
 507            // Don't queue known-island members. They were added to the dg only
 508            // so cycle detection sees them; we never expand through them.
 62881509            if (IsKnownIsland(m, ctx.Kind, ctx.Islands)) continue;
 122586510            if (!queued.Add(m)) continue;
 3164511            queue.Enqueue(m);
 3164512        }
 4754513    }
 514
 515    /// <summary>
 516    /// Re-canonicalise the F and B sets after a merge. Each set's entries are
 517    /// component roots; a merge can collapse multiple of them into one. We
 518    /// replace stale entries with their current <see cref="Find"/> result and
 519    /// dedup.
 520    /// </summary>
 521    private static void RekeyAfterMerge(Ctx ctx)
 1617522    {
 1617523        Rekey(ctx.InForward, ctx.Dg);
 1617524        Rekey(ctx.InBackward, ctx.Dg);
 1617525    }
 526
 527    private static void Rekey(HashSet<EdgeId> set, IslandDirectedGraph dg)
 3234528    {
 3234529        if (set.Count == 0) return;
 3234530        var fresh = new HashSet<EdgeId>(set.Count);
 25536531        foreach (var r in set) fresh.Add(dg.Find(r));
 4528532        if (fresh.Count == set.Count && SetEquals(fresh, set)) return;
 1940533        set.Clear();
 12273534        foreach (var r in fresh) set.Add(r);
 3234535    }
 536
 537    private static bool SetEquals(HashSet<EdgeId> a, HashSet<EdgeId> b)
 1618538    {
 1618539        if (a.Count != b.Count) return false;
 10350540        foreach (var x in a) if (!b.Contains(x)) return false;
 1294541        return true;
 1618542    }
 543
 544    private static void MaybeCollapse(IslandDirectedGraph dg, EdgeId a, int maxIslandSize)
 1617545    {
 1617546        var size = dg.GetSize(dg.Find(a));
 1855547        if (size >= maxIslandSize) dg.CollapseToMainNetwork(a);
 1617548    }
 549}
Generated by: ReportGenerator 4.8.2.0
07/06/2026 - 12:21:39
GitHub | www.palmmedia.de

Methods/Properties

ClassifyAsync()
BuildForTileAsync()
BuildForTileInsideSerialiserAsync()
IsKnownIsland(...)
.ctor(...)
ProcessEdgeAsync()
ProcessAtEndpointAsync()
AddLinkAndPropagate(...)
PropagateForward(...)
PropagateBackward(...)
EnqueueMembers(...)
RekeyAfterMerge(...)
Rekey(...)
SetEquals(...)
MaybeCollapse(...)