< 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:315
Uncovered lines:0
Coverable lines:315
Total lines:512
Line coverage:100% (315 of 315)
Covered branches:186
Total branches:210
Branch coverage:88.5% (186 of 210)
Tag:263_26948838820

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
ClassifyAsync()85.71%42100%
BuildForTileAsync()84.09%44100%
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)
 213640    {
 213641        var islands = network.IslandManager.GetIslandsFor(profile);
 213642        var dg = network.IslandManager.GetOrCreateDirectedGraph(profile, kind);
 213643        var maxIslandSize = network.IslandManager.MaxIslandSize;
 213644        var costFunction = IslandKindCostFunctions.GetFor(network, profile, kind);
 213645        var probe = network.GetEdgeEnumerator();
 213646        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.
 213651        IslandDirectedGraph? nonLocalDg = null;
 213652        if (kind == IslandKind.Full)
 109153        {
 109154            nonLocalDg = network.IslandManager.GetOrCreateDirectedGraph(profile, IslandKind.NonLocal);
 109155        }
 56
 57        // Oracle / cached-state short-circuits.
 213858        if (IsKnownIsland(seed, kind, islands)) return IslandStatus.Island;
 305459        if (dg.IsNotIsland(seed)) return IslandStatus.NotIsland;
 121460        if (nonLocalDg != null && nonLocalDg.IsNotIsland(seed))
 103261        {
 103262            dg.AddVertex(seed);
 103263            dg.CollapseToMainNetwork(seed);
 103264            return IslandStatus.NotIsland;
 65        }
 66
 67        // Edge must exist and be traversable in at least one direction.
 18268        if (!probe.MoveTo(seed, true)) return IslandStatus.Unknown;
 18269        var seedHead = probe.Head;
 18270        var seedTail = probe.Tail;
 18271        var canFwd = costFunction.GetIslandBuilderCost(probe);
 18272        if (!probe.MoveTo(seed, false)) return IslandStatus.Unknown;
 18273        var canBwd = costFunction.GetIslandBuilderCost(probe);
 18574        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).
 17977        dg.AddVertex(seed);
 17978        var ctx = new Ctx(network, dg, nonLocalDg, kind, islands, costFunction, maxIslandSize);
 17979        ctx.InForward.Add(dg.Find(seed));
 17980        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.
 17985        await ProcessAtEndpointAsync(seed, seedHead, ctx, cancellationToken);
 17986        if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 17987        await ProcessAtEndpointAsync(seed, seedTail, ctx, cancellationToken);
 17988        if (cancellationToken.IsCancellationRequested) return IslandStatus.Unknown;
 17989        dg.SetProcessed(seed);
 90
 91        // Main loop: termination checks are O(1) lookups on the sentinel.
 109892        while (true)
 109893        {
 94            // Graduation: if seed was absorbed into the sentinel by an eager
 95            // cycle-merge or size-threshold collapse, return immediately.
 124396            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        }
 2136129    }
 130
 131    public static async Task BuildForTileAsync(
 132        RoutingNetwork network,
 133        Profile profile,
 134        uint tileId,
 135        CancellationToken cancellationToken)
 10136    {
 10137        if (cancellationToken.IsCancellationRequested) return;
 138
 10139        var islands = network.IslandManager.GetIslandsFor(profile);
 10140        if (islands.GetTileDone(tileId)) return;
 141
 142        // Use the Full cost function to enumerate traversable edges and to
 143        // detect L-tagged ones (NonLocalCostFunction masks L away — we need
 144        // the raw tag here for both edge-gathering and L-set computation).
 10145        var fullCostFunction = IslandKindCostFunctions.GetFor(network, profile, IslandKind.Full);
 10146        await network.UsageNotifier.NotifyVertex(network, new VertexId(tileId, 0), cancellationToken);
 10147        if (cancellationToken.IsCancellationRequested) return;
 10148        var tile = network.GetTileForRead(tileId);
 10149        if (tile == null) return;
 150
 10151        var probe = network.GetEdgeEnumerator();
 10152        var tileEnum = new NetworkTileEnumerator();
 10153        tileEnum.MoveTo(tile);
 10154        var v = new VertexId(tileId, 0);
 10155        var edges = new List<EdgeId>();
 10156        var lEdges = new HashSet<EdgeId>();
 574157        while (tileEnum.MoveTo(v))
 564158        {
 2655159            while (tileEnum.MoveNext())
 2091160            {
 3141161                if (!tileEnum.Forward) continue;
 1041162                var edgeId = tileEnum.EdgeId;
 1041163                if (!probe.MoveTo(edgeId, true)) continue;
 1041164                var fwd = fullCostFunction.Get(probe, true);
 1041165                var canFwd = fwd is { canAccess: true, turnCost: < double.MaxValue };
 1041166                if (!probe.MoveTo(edgeId, false)) continue;
 1041167                var bwd = fullCostFunction.Get(probe, true);
 1041168                var canBwd = bwd is { canAccess: true, turnCost: < double.MaxValue };
 2082169                if (canFwd || canBwd) edges.Add(edgeId);
 1043170                if (fwd.localAccess || bwd.localAccess) lEdges.Add(edgeId);
 1041171            }
 564172            v = new VertexId(tileId, v.LocalId + 1);
 564173        }
 174
 175        // NonLocal pass first — classifies the N-only subgraph. L-tagged
 176        // seeds are masked out by NonLocalCostFunction and return Unknown.
 2112177        foreach (var edge in edges)
 1041178        {
 1041179            if (cancellationToken.IsCancellationRequested) return;
 1041180            await ClassifyAsync(network, profile, edge, cancellationToken, IslandKind.NonLocal);
 1041181        }
 182
 183        // Full pass — reuses NonLocal MainNet as a positive oracle to short-
 184        // circuit edges already known to be in N-mainland.
 2112185        foreach (var edge in edges)
 1041186        {
 1041187            if (cancellationToken.IsCancellationRequested) return;
 1041188            await ClassifyAsync(network, profile, edge, cancellationToken, IslandKind.Full);
 1041189        }
 190
 191        // Locals = NonLocal-Island ∩ Full-NotIsland ∩ non-L. These are the
 192        // non-L edges only reachable from main-N through an L-edge first.
 193        // L-tagged edges and Full-Island edges are excluded.
 2112194        foreach (var edge in edges)
 1041195        {
 1043196            if (lEdges.Contains(edge)) continue;
 1041197            if (islands.IsEdgeOnIsland(edge)) continue;
 2068198            if (!islands.IsEdgeOnIsland(edge, IslandKind.NonLocal)) continue;
 6199            islands.SetEdgeLocal(edge);
 6200        }
 201
 10202        islands.ClearNonLocalIslandEdges();
 10203        islands.SetTileDone(tileId);
 10204    }
 205
 206    /// <summary>
 207    /// Kind-aware "known island" oracle. For Full this is the persistent
 208    /// Full-Islands set. For NonLocal an edge is known to be a NonLocal-Island
 209    /// if it is in Full-Islands (Full-Island ⟹ NonLocal-Island), in
 210    /// <c>_localEdges</c> (Local edges are unreachable via N-only paths), or
 211    /// in the transient <c>_nonLocalIslandEdges</c> set written during the
 212    /// current NonLocal pass.
 213    /// </summary>
 214    private static bool IsKnownIsland(EdgeId edgeId, IslandKind kind, Islands islands)
 70794215    {
 70794216        if (kind == IslandKind.NonLocal)
 69422217        {
 69422218            if (islands.IsEdgeOnIsland(edgeId)) return true;
 69422219            if (islands.IsEdgeLocal(edgeId)) return true;
 69422220            return islands.IsEdgeOnIsland(edgeId, IslandKind.NonLocal);
 221        }
 1372222        return islands.IsEdgeOnIsland(edgeId);
 70794223    }
 224
 225    /// <summary>
 226    /// Per-classification working state. Owns the two queues, the per-queue
 227    /// dedup sets, and the F/B sticky sets used to track per-component
 228    /// reachability to/from the seed in the dg.
 229    /// </summary>
 230    private sealed class Ctx
 231    {
 232        public readonly RoutingNetwork Network;
 233        public readonly IslandDirectedGraph Dg;
 234        public readonly IslandDirectedGraph? NonLocalDg;
 235        public readonly IslandKind Kind;
 236        public readonly Islands Islands;
 237        public readonly ICostFunction CostFunction;
 238        public readonly int MaxIslandSize;
 179239        public readonly Queue<EdgeId> ForwardQueue = new();
 179240        public readonly Queue<EdgeId> BackwardQueue = new();
 179241        public readonly HashSet<EdgeId> QueuedForward = new();
 179242        public readonly HashSet<EdgeId> QueuedBackward = new();
 179243        public readonly HashSet<EdgeId> InForward = new();
 179244        public readonly HashSet<EdgeId> InBackward = new();
 245
 179246        public Ctx(RoutingNetwork network, IslandDirectedGraph dg,
 179247            IslandDirectedGraph? nonLocalDg, IslandKind kind, Islands islands,
 179248            ICostFunction costFunction, int maxIslandSize)
 179249        {
 179250            Network = network;
 179251            Dg = dg;
 179252            NonLocalDg = nonLocalDg;
 179253            Kind = kind;
 179254            Islands = islands;
 179255            CostFunction = costFunction;
 179256            MaxIslandSize = maxIslandSize;
 179257        }
 258    }
 259
 260    private static async Task ProcessEdgeAsync(EdgeId edgeId, Ctx ctx, CancellationToken cancellationToken)
 1836261    {
 2756262        if (ctx.Dg.IsProcessed(edgeId)) return;
 916263        var probe = ctx.Network.GetEdgeEnumerator();
 916264        if (!probe.MoveTo(edgeId, true)) { ctx.Dg.SetProcessed(edgeId); return; }
 916265        var head = probe.Head;
 916266        var tail = probe.Tail;
 916267        await ProcessAtEndpointAsync(edgeId, head, ctx, cancellationToken);
 916268        if (cancellationToken.IsCancellationRequested) return;
 916269        await ProcessAtEndpointAsync(edgeId, tail, ctx, cancellationToken);
 916270        ctx.Dg.SetProcessed(edgeId);
 1836271    }
 272
 273    private static async Task ProcessAtEndpointAsync(
 274        EdgeId edgeId, VertexId vertex, Ctx ctx, CancellationToken cancellationToken)
 2190275    {
 2190276        await ctx.Network.UsageNotifier.NotifyVertex(ctx.Network, vertex, cancellationToken);
 2190277        if (cancellationToken.IsCancellationRequested) return;
 278
 2190279        var edgeIdFrom = ctx.Network.GetEdgeEnumerator();
 2190280        if (!edgeIdFrom.MoveTo(edgeId, true)) return;
 2190281        var arrivalForward = edgeIdFrom.Head == vertex;
 2190282        if (!arrivalForward)
 1095283        {
 1095284            if (!edgeIdFrom.MoveTo(edgeId, false)) return;
 1095285        }
 2190286        var edgeIdTo = ctx.Network.GetEdgeEnumerator();
 2190287        if (!edgeIdTo.MoveTo(edgeId, !arrivalForward)) return;
 2190288        var neighborArriving = ctx.Network.GetEdgeEnumerator();
 289
 2190290        var enumerator = ctx.Network.GetEdgeEnumerator();
 2190291        if (!enumerator.MoveTo(vertex)) return;
 10223292        while (enumerator.MoveNext())
 8033293        {
 10223294            if (enumerator.EdgeId == edgeId) continue;
 5843295            var neighborId = enumerator.EdgeId;
 5843296            var iterationForward = enumerator.Forward;
 297
 5843298            var canGoTo = ctx.CostFunction.GetIslandBuilderCost(edgeIdFrom, enumerator);
 5843299            neighborArriving.MoveTo(neighborId, !iterationForward);
 5843300            var canComeFrom = ctx.CostFunction.GetIslandBuilderCost(neighborArriving, edgeIdTo);
 301
 5843302            enumerator.MoveTo(vertex);
 14332303            while (enumerator.MoveNext())
 14332304            {
 20175305                if (enumerator.EdgeId == neighborId) break;
 8489306            }
 307
 5856308            if (!canGoTo && !canComeFrom) continue;
 309
 310            // Oracle.
 311            EdgeId neighborDgVertex;
 312            bool isKnown;
 5830313            if (IsKnownIsland(neighborId, ctx.Kind, ctx.Islands))
 13314            {
 13315                ctx.Dg.AddVertex(neighborId);
 13316                neighborDgVertex = neighborId;
 13317                isKnown = true;
 13318            }
 5817319            else if (ctx.Dg.IsNotIsland(neighborId) ||
 5817320                     (ctx.NonLocalDg != null && ctx.NonLocalDg.IsNotIsland(neighborId)) ||
 5817321                     ctx.Islands.GetTileDone(neighborId.TileId))
 362322            {
 362323                neighborDgVertex = IslandDirectedGraph.MainNetworkSentinel;
 362324                isKnown = true;
 362325            }
 326            else
 5455327            {
 5455328                ctx.Dg.AddVertex(neighborId);
 5455329                neighborDgVertex = neighborId;
 5455330                isKnown = false;
 5455331            }
 332
 11578333            if (canGoTo) AddLinkAndPropagate(edgeId, neighborDgVertex, ctx);
 11584334            if (canComeFrom) AddLinkAndPropagate(neighborDgVertex, edgeId, ctx);
 335
 336            // The neighbour's queue assignment is handled by the propagation
 337            // (newly inForward → forwardQueue; newly inBackward → backwardQueue).
 338            // For known-island neighbours nothing needs to be queued; the dg
 339            // link still got added so cycle detection sees it.
 5830340            _ = isKnown;
 5830341        }
 2190342    }
 343
 344    /// <summary>
 345    /// Adds a directed link <c>a → b</c> to the dg and incrementally maintains
 346    /// the per-classification <see cref="Ctx.InForward"/> and
 347    /// <see cref="Ctx.InBackward"/> sets through any propagation the new link
 348    /// causes. Newly-marked components are enqueued to the appropriate queue.
 349    /// </summary>
 350    private static void AddLinkAndPropagate(EdgeId a, EdgeId b, Ctx ctx)
 11502351    {
 11502352        var aRootBefore = ctx.Dg.Find(a);
 11502353        var bRootBefore = ctx.Dg.Find(b);
 19784354        if (aRootBefore == bRootBefore) return;
 355
 356        // Capture F/B membership of both endpoints BEFORE the link is added.
 357        // If the call causes a cycle-merge, the original roots disappear and
 358        // we'll need to consolidate.
 3220359        var aInF = ctx.InForward.Contains(aRootBefore);
 3220360        var bInF = ctx.InForward.Contains(bRootBefore);
 3220361        var aInB = ctx.InBackward.Contains(aRootBefore);
 3220362        var bInB = ctx.InBackward.Contains(bRootBefore);
 363
 3220364        var merged = ctx.Dg.AddDirectedLink(a, b);
 4787365        if (merged) MaybeCollapse(ctx.Dg, a, ctx.MaxIslandSize);
 366
 3220367        if (merged)
 1567368        {
 369            // Cycle close: a and b (and possibly others) are now one component.
 370            // Combine F/B membership into the new root and propagate.
 1567371            RekeyAfterMerge(ctx);
 1567372            var newRoot = ctx.Dg.Find(a);
 1567373            var nowInF = aInF || bInF;
 1567374            var nowInB = aInB || bInB;
 375
 1567376            if (nowInF)
 1557377            {
 1557378                ctx.InForward.Add(newRoot);
 379                // The merge can absorb previously-isolated components whose
 380                // members were never queued (because they weren't in F yet).
 381                // Re-enqueue idempotently — `queuedForward` dedups.
 1557382                EnqueueMembers(newRoot, ctx.ForwardQueue, ctx.QueuedForward, ctx);
 383                // Outgoing chains from the new root may lead to components
 384                // that weren't in F before; propagate into each.
 5019385                foreach (var t in ctx.Dg.GetOutgoingRoots(newRoot))
 174386                {
 174387                    if (!ctx.InForward.Contains(ctx.Dg.Find(t))) PropagateForward(t, ctx);
 174388                }
 1557389            }
 1567390            if (nowInB)
 1558391            {
 1558392                ctx.InBackward.Add(newRoot);
 1558393                EnqueueMembers(newRoot, ctx.BackwardQueue, ctx.QueuedBackward, ctx);
 5030394                foreach (var s in ctx.Dg.GetIncomingRoots(newRoot))
 178395                {
 181396                    if (!ctx.InBackward.Contains(ctx.Dg.Find(s))) PropagateBackward(s, ctx);
 178397                }
 1558398            }
 1567399        }
 400        else
 1653401        {
 402            // Plain link added (no merge). Propagate F/B across it if applicable.
 403            //   - If a was in F, b's outgoing closure joins F.
 404            //   - If b was in B, a's incoming closure joins B.
 3221405            if (aInF && !bInF) PropagateForward(bRootBefore, ctx);
 1681406            if (bInB && !aInB) PropagateBackward(aRootBefore, ctx);
 1653407        }
 11502408    }
 409
 410    /// <summary>
 411    /// BFS from <paramref name="fromRoot"/> through <c>_outgoing</c> chains,
 412    /// marking newly-reached components as <c>inForward</c> and enqueueing
 413    /// their unprocessed members to the forward queue. Each component enters
 414    /// <c>inForward</c> at most once.
 415    /// </summary>
 416    private static void PropagateForward(EdgeId fromRoot, Ctx ctx)
 1568417    {
 1568418        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 1568419        var stack = new Stack<EdgeId>();
 1568420        stack.Push(fromRoot);
 3139421        while (stack.Count > 0)
 1571422        {
 1571423            var current = ctx.Dg.Find(stack.Pop());
 1571424            if (!ctx.InForward.Add(current)) continue;
 425
 1571426            if (current != sentinel)
 1453427            {
 1453428                EnqueueMembers(current, ctx.ForwardQueue, ctx.QueuedForward, ctx);
 1453429            }
 430
 4719431            foreach (var t in ctx.Dg.GetOutgoingRoots(current))
 3432            {
 6433                if (!ctx.InForward.Contains(ctx.Dg.Find(t))) stack.Push(t);
 3434            }
 1571435        }
 1568436    }
 437
 438    /// <summary>
 439    /// Mirror of <see cref="PropagateForward"/> walking <c>_incoming</c>.
 440    /// </summary>
 441    private static void PropagateBackward(EdgeId fromRoot, Ctx ctx)
 31442    {
 31443        var sentinel = IslandDirectedGraph.MainNetworkSentinel;
 31444        var stack = new Stack<EdgeId>();
 31445        stack.Push(fromRoot);
 75446        while (stack.Count > 0)
 44447        {
 44448            var current = ctx.Dg.Find(stack.Pop());
 44449            if (!ctx.InBackward.Add(current)) continue;
 450
 44451            if (current != sentinel)
 36452            {
 36453                EnqueueMembers(current, ctx.BackwardQueue, ctx.QueuedBackward, ctx);
 36454            }
 455
 158456            foreach (var s in ctx.Dg.GetIncomingRoots(current))
 13457            {
 26458                if (!ctx.InBackward.Contains(ctx.Dg.Find(s))) stack.Push(s);
 13459            }
 44460        }
 31461    }
 462
 463    private static void EnqueueMembers(EdgeId root, Queue<EdgeId> queue, HashSet<EdgeId> queued, Ctx ctx)
 4604464    {
 4604465        var members = ctx.Dg.GetMembers(root);
 4971466        if (members == null) return;
 542673467        foreach (var m in members)
 264981468        {
 467134469            if (ctx.Dg.IsProcessed(m)) continue;
 470            // Don't queue known-island members. They were added to the dg only
 471            // so cycle detection sees them; we never expand through them.
 62831472            if (IsKnownIsland(m, ctx.Kind, ctx.Islands)) continue;
 122536473            if (!queued.Add(m)) continue;
 3114474            queue.Enqueue(m);
 3114475        }
 4604476    }
 477
 478    /// <summary>
 479    /// Re-canonicalise the F and B sets after a merge. Each set's entries are
 480    /// component roots; a merge can collapse multiple of them into one. We
 481    /// replace stale entries with their current <see cref="Find"/> result and
 482    /// dedup.
 483    /// </summary>
 484    private static void RekeyAfterMerge(Ctx ctx)
 1567485    {
 1567486        Rekey(ctx.InForward, ctx.Dg);
 1567487        Rekey(ctx.InBackward, ctx.Dg);
 1567488    }
 489
 490    private static void Rekey(HashSet<EdgeId> set, IslandDirectedGraph dg)
 3134491    {
 3134492        if (set.Count == 0) return;
 3134493        var fresh = new HashSet<EdgeId>(set.Count);
 24786494        foreach (var r in set) fresh.Add(dg.Find(r));
 4428495        if (fresh.Count == set.Count && SetEquals(fresh, set)) return;
 1840496        set.Clear();
 11673497        foreach (var r in fresh) set.Add(r);
 3134498    }
 499
 500    private static bool SetEquals(HashSet<EdgeId> a, HashSet<EdgeId> b)
 1568501    {
 1568502        if (a.Count != b.Count) return false;
 10050503        foreach (var x in a) if (!b.Contains(x)) return false;
 1294504        return true;
 1568505    }
 506
 507    private static void MaybeCollapse(IslandDirectedGraph dg, EdgeId a, int maxIslandSize)
 1567508    {
 1567509        var size = dg.GetSize(dg.Find(a));
 1755510        if (size >= maxIslandSize) dg.CollapseToMainNetwork(a);
 1567511    }
 512}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

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