< Summary

Class:Itinero.Network.Search.Islands.IslandDirectedGraph
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/IslandDirectedGraph.cs
Covered lines:392
Uncovered lines:237
Coverable lines:629
Total lines:986
Line coverage:62.3% (392 of 629)
Covered branches:175
Total branches:290
Branch coverage:60.3% (175 of 290)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.cctor()100%1100%
.ctor()100%1100%
AddVertex(...)100%2100%
IsInGraph(...)100%1100%
GetAllEdges()75%483.33%
OutgoingIsCanonical(...)83.33%686.66%
IncomingIsCanonical(...)0%60%
HasComponentCycle(...)100%24100%
AdjacencyIsMirrored(...)75%1682.6%
IsProcessed(...)100%1100%
SetProcessed(...)100%1100%
IsNotIsland(...)100%2100%
GetSize(...)100%1100%
GetMembersInto(...)100%6100%
AddDirectedLink(...)100%14100%
PathExistsNoLock(...)90%20100%
IntersectReachableNoLock(...)92.3%26100%
HasDirectedLink(...)0%20%
Merge(...)100%10%
MergeNoLock(...)97.61%4295.29%
CollapseToMainNetwork(...)100%2100%
RemoveEdge(...)0%160%
DiscardAllExceptSentinel()100%10%
IsDeadEnd(...)0%80%
CanReachMainNetwork(...)0%40%
ReachMainNetworkDirections(...)0%20%
GetOutgoingRoots(...)90%10100%
GetIncomingRoots(...)90%10100%
GetLinkedNeighbourRoots(...)0%160%
DfsCanReach(...)0%160%
DetectAndMergeCycles(...)0%160%
Strongconnect(...)0%140%
Find(...)100%1100%
FindNoLock(...)66.66%6100%

File(s)

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

#LineLine coverage
 1using System.Collections.Concurrent;
 2using System.Collections.Generic;
 3using System.Threading;
 4using Itinero.Network.Enumerators.Edges;
 5
 6namespace Itinero.Network.Search.Islands;
 7
 8/// <summary>
 9/// A directed meta-graph for island detection.
 10/// Each vertex represents one or more routing edges (merged via union-find).
 11/// Directed links represent travel direction between edge groups.
 12/// </summary>
 13internal class IslandDirectedGraph
 14{
 115    internal static readonly EdgeId MainNetworkSentinel = new(uint.MaxValue - 1, uint.MaxValue - 1);
 16
 122817    private readonly Dictionary<EdgeId, EdgeId> _parent = new();
 122818    private readonly Dictionary<EdgeId, int> _rank = new();
 122819    private readonly Dictionary<EdgeId, int> _size = new();
 122820    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _outgoing = new();
 122821    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _incoming = new();
 122822    private readonly Dictionary<EdgeId, List<EdgeId>> _members = new();
 122823    private readonly ConcurrentDictionary<EdgeId, byte> _processed = new();
 24
 25    // The graph is built incrementally (mutations) and queried concurrently from
 26    // many snap operations. The underlying Dictionaries / HashSets are not safe
 27    // for read-during-write — concurrent IsNotIsland calls during an in-flight
 28    // ProcessEdge corrupt the dict and throw "concurrent update". A reader-writer
 29    // lock keeps reads concurrent against each other (cheap on the snap path)
 30    // and exclusive against any mutation.
 122831    private readonly ReaderWriterLockSlim _lock = new(LockRecursionPolicy.SupportsRecursion);
 32
 33    // Scratch for the cycle-merge walks. PathExistsNoLock and IntersectReachableNoLock are
 34    // called only from AddDirectedLink, which holds the write lock, so one set per graph
 35    // is enough. A walk visits 11.5 nodes on average - allocating the collections cost
 36    // more than traversing them.
 122837    private readonly HashSet<EdgeId> _pathVisited = new();
 122838    private readonly Stack<EdgeId> _pathStack = new();
 122839    private readonly HashSet<EdgeId> _sccForward = new();
 122840    private readonly HashSet<EdgeId> _sccBackward = new();
 122841    private readonly Stack<EdgeId> _sccStack = new();
 42
 43    /// Clearing costs capacity, not count, so one freak walk would tax every later one.
 44    private const int ScratchKeepCapacity = 1024;
 45
 122846    public IslandDirectedGraph()
 122847    {
 122848        _parent[MainNetworkSentinel] = MainNetworkSentinel;
 122849        _rank[MainNetworkSentinel] = int.MaxValue;
 122850        _size[MainNetworkSentinel] = int.MaxValue;
 122851    }
 52
 53    public void AddVertex(EdgeId edgeId)
 3051754    {
 3051755        _lock.EnterWriteLock();
 56        try
 3051757        {
 3453658            if (_parent.ContainsKey(edgeId)) return;
 2649859            _parent[edgeId] = edgeId;
 2649860            _rank[edgeId] = 0;
 2649861            _size[edgeId] = 1;
 2649862            _members[edgeId] = new List<EdgeId> { edgeId };
 2649863        }
 9155164        finally { _lock.ExitWriteLock(); }
 3051765    }
 66
 67    public bool IsInGraph(EdgeId edgeId)
 168    {
 169        _lock.EnterReadLock();
 270        try { return _parent.ContainsKey(edgeId); }
 371        finally { _lock.ExitReadLock(); }
 172    }
 73
 74    /// <summary>
 75    /// Returns a snapshot of every edge currently in the graph, excluding the
 76    /// <see cref="MainNetworkSentinel"/>. Intended for callers that need to
 77    /// feed every known edge into a global resolution pass (e.g. Tarjan SCC
 78    /// over the full set of one-way singletons forming a cycle).
 79    /// </summary>
 80    public List<EdgeId> GetAllEdges()
 5081    {
 5082        _lock.EnterReadLock();
 83        try
 5084        {
 5085            var result = new List<EdgeId>(_parent.Count);
 25086            foreach (var k in _parent.Keys)
 5087            {
 10088                if (k == MainNetworkSentinel) continue;
 089                result.Add(k);
 090            }
 5091            return result;
 92        }
 15093        finally { _lock.ExitReadLock(); }
 5094    }
 95
 96    /// <summary>
 97    /// Test-only: are _outgoing and _incoming exact mirrors of each other?
 98    /// </summary>
 99    /// <remarks>
 100    /// They encode the same edge set from both ends, and MergeNoLock relies on that: to
 101    /// repair everyone pointing at an absorbed root it walks _incoming[rootB], so a link
 102    /// recorded in only one direction is a link the repair cannot see. Note that the
 103    /// mirror updates during a merge sit behind TryGetValue guards, and aOut.Add(tRoot)
 104    /// is unconditional while recording the reverse is not.
 105    /// </remarks>
 106    /// <summary>
 107    /// Test-only: every entry in every adjacency set is its own root.
 108    /// </summary>
 109    internal bool OutgoingIsCanonical(out string failure)
 25253110    {
 25253111        _lock.EnterReadLock();
 112        try
 25253113        {
 457533114            foreach (var (root, targets) in _outgoing)
 190887115            {
 1150215116                foreach (var t in targets)
 288777117                {
 577554118                    if (this.FindNoLock(t) == t) continue;
 0119                    failure = $"_outgoing[{root}] holds stale {t}, root is {this.FindNoLock(t)}";
 0120                    return false;
 121                }
 190887122            }
 123
 25253124            failure = "";
 25253125            return true;
 126        }
 75759127        finally { _lock.ExitReadLock(); }
 25253128    }
 129
 130    /// <summary>
 131    /// Test-only, and deliberately NOT asserted: _incoming is expected to hold stale
 132    /// roots.
 133    /// </summary>
 134    /// <remarks>
 135    /// Removing the absorbed root from _incoming[rootA] as well as _outgoing[rootA] makes
 136    /// both indexes exactly canonical and repairs the mirror - and hangs
 137    /// Car/generated/case_gen_car_classifications_016. Removing it from _outgoing alone
 138    /// does not. Something in the backward direction depends on those entries surviving,
 139    /// and until that is understood _incoming must be read through Find.
 140    /// </remarks>
 141    internal bool IncomingIsCanonical(out string failure)
 0142    {
 0143        _lock.EnterReadLock();
 144        try
 0145        {
 0146            foreach (var (root, sources) in _incoming)
 0147            {
 0148                foreach (var f in sources)
 0149                {
 0150                    if (this.FindNoLock(f) == f) continue;
 0151                    failure = $"_incoming[{root}] holds stale {f}, root is {this.FindNoLock(f)}";
 0152                    return false;
 153                }
 0154            }
 155
 0156            failure = "";
 0157            return true;
 158        }
 0159        finally { _lock.ExitReadLock(); }
 0160    }
 161
 162    /// <summary>
 163    /// Test-only: does the component graph contain a cycle? Contracting a complete SCC
 164    /// cannot create one; CollapseToMainNetwork force-merges without checking and can.
 165    /// </summary>
 166    internal bool HasComponentCycle(out string cycle)
 240167    {
 240168        _lock.EnterReadLock();
 169        try
 240170        {
 240171            var state = new Dictionary<EdgeId, int>();
 1787172            foreach (var start in _outgoing.Keys)
 535173            {
 689174                if (state.TryGetValue(start, out var st) && st == 2) continue;
 175
 381176                var stack = new Stack<(EdgeId node, IEnumerator<EdgeId>? iter)>();
 381177                stack.Push((start, null));
 381178                state[start] = 1;
 1503179                while (stack.Count > 0)
 1125180                {
 1125181                    var (node, iter) = stack.Pop();
 1125182                    iter ??= _outgoing.TryGetValue(node, out var outs) ? outs.GetEnumerator() : null;
 1125183                    var advanced = false;
 1394184                    while (iter != null && iter.MoveNext())
 646185                    {
 646186                        var next = iter.Current;
 646187                        if (next == node) continue;
 646188                        state.TryGetValue(next, out var ns);
 646189                        if (ns == 1)
 3190                        {
 3191                            cycle = $"{node} -> {next} closes a cycle";
 3192                            return true;
 193                        }
 194
 912195                        if (ns == 2) continue;
 196
 374197                        stack.Push((node, iter));
 374198                        stack.Push((next, null));
 374199                        state[next] = 1;
 374200                        advanced = true;
 374201                        break;
 202                    }
 203
 1870204                    if (!advanced) state[node] = 2;
 1122205                }
 378206            }
 207
 237208            cycle = "";
 237209            return false;
 210        }
 720211        finally { _lock.ExitReadLock(); }
 240212    }
 213
 214    internal bool AdjacencyIsMirrored(out string failure)
 1215    {
 1216        _lock.EnterReadLock();
 217        try
 1218        {
 9219            foreach (var (from, targets) in _outgoing)
 3220            {
 15221                foreach (var to in targets)
 3222                {
 6223                    if (_incoming.TryGetValue(to, out var sources) && sources.Contains(from)) continue;
 224
 0225                    failure = $"_outgoing[{from}] has {to}, but _incoming[{to}] does not have {from}";
 0226                    return false;
 227                }
 3228            }
 229
 7230            foreach (var (to, sources) in _incoming)
 2231            {
 12232                foreach (var from in sources)
 3233                {
 6234                    if (_outgoing.TryGetValue(from, out var targets) && targets.Contains(to)) continue;
 235
 0236                    failure = $"_incoming[{to}] has {from}, but _outgoing[{from}] does not have {to}";
 0237                    return false;
 238                }
 2239            }
 240
 1241            failure = "";
 1242            return true;
 243        }
 3244        finally { _lock.ExitReadLock(); }
 1245    }
 246
 247    public bool IsProcessed(EdgeId edgeId)
 64803248    {
 64803249        return _processed.ContainsKey(edgeId);
 64803250    }
 251
 252    public void SetProcessed(EdgeId edgeId)
 1162253    {
 1162254        _processed[edgeId] = 0;
 1162255    }
 256
 257    public bool IsNotIsland(EdgeId edgeId)
 13138258    {
 13138259        _lock.EnterReadLock();
 260        try
 13138261        {
 16236262            if (!_parent.ContainsKey(edgeId)) return false;
 10040263            return this.FindNoLock(edgeId) == this.FindNoLock(MainNetworkSentinel);
 264        }
 39414265        finally { _lock.ExitReadLock(); }
 13138266    }
 267
 268    public int GetSize(EdgeId edgeId)
 1640269    {
 1640270        _lock.EnterReadLock();
 3280271        try { return _size[this.FindNoLock(edgeId)]; }
 4920272        finally { _lock.ExitReadLock(); }
 1640273    }
 274
 275    /// <summary>
 276    /// Copies the unprocessed members of <paramref name="edgeId"/>'s component into
 277    /// <paramref name="into"/>. False when the component has no member list, which is the
 278    /// case for the main network sentinel.
 279    /// </summary>
 280    /// <remarks>
 281    /// Still a snapshot - callers iterate outside the lock - but the buffer belongs to the
 282    /// caller instead of being allocated per call, and processed members are dropped as
 283    /// they are passed. IsProcessed is monotone, so a member dropped here can never be
 284    /// needed again and each is dropped at most once; without it the caller re-walked the
 285    /// whole component on every propagation step, and member lists only grow because
 286    /// merges concatenate them. Measured: EnqueueMembers 13.1% -> 2.3% of CPU.
 287    ///
 288    /// Write lock, not read, because this prunes. NOTE: RemoveEdge reads
 289    /// members.Count == 0 as "component is empty" and tears down its adjacency - it has
 290    /// no callers today, but if revived it must not treat a fully-pruned component as an
 291    /// empty one.
 292    /// </remarks>
 293    public bool GetMembersInto(EdgeId edgeId, List<EdgeId> into)
 4815294    {
 4815295        _lock.EnterWriteLock();
 296        try
 4815297        {
 4815298            var root = this.FindNoLock(edgeId);
 5300299            if (!_members.TryGetValue(root, out var m)) return false;
 300
 136332301            for (var i = m.Count - 1; i >= 0; i--)
 63836302            {
 126785303                if (!_processed.ContainsKey(m[i])) continue;
 887304                m[i] = m[^1];
 887305                m.RemoveAt(m.Count - 1);
 887306            }
 307
 4330308            into.Clear();
 4330309            into.AddRange(m);
 4330310            return true;
 311        }
 14445312        finally { _lock.ExitWriteLock(); }
 4815313    }
 314
 315    /// <summary>
 316    /// Adds a directed link <paramref name="from"/> → <paramref name="to"/> to the
 317    /// graph, with **eager cycle detection**: if a path already exists in the dg
 318    /// from <paramref name="to"/>'s component back to <paramref name="from"/>'s
 319    /// component, the new link closes a strongly-connected component. All
 320    /// components on every path back are merged into one node (F ∩ R: forward
 321    /// reachable from <paramref name="to"/> ∩ backward reachable from
 322    /// <paramref name="from"/>). Returns <c>true</c> when this happens, so the
 323    /// caller can size-check the merged component for MainNet graduation.
 324    /// Returns <c>false</c> when the link was a regular edge (no cycle closed).
 325    /// </summary>
 326    public bool AddDirectedLink(EdgeId from, EdgeId to)
 56729327    {
 56729328        _lock.EnterWriteLock();
 329        try
 56729330        {
 56729331            var fromRoot = this.FindNoLock(from);
 56729332            var toRoot = this.FindNoLock(to);
 68916333            if (fromRoot == toRoot) return false;
 334
 335            // Eager cycle-merge: if there's already a path toRoot ↝ fromRoot
 336            // in the existing graph, adding from→to closes an SCC. Collapse
 337            // every component on a closing path into one node.
 44542338            if (this.PathExistsNoLock(toRoot, fromRoot))
 8334339            {
 8334340                var sccRoots = this.IntersectReachableNoLock(toRoot, fromRoot);
 8334341                sccRoots.Add(fromRoot);
 8334342                sccRoots.Add(toRoot);
 8334343                EdgeId target = fromRoot;
 71832344                foreach (var r in sccRoots)
 23415345                {
 23415346                    if (this.FindNoLock(r) != this.FindNoLock(target))
 15081347                        this.MergeNoLock(target, r);
 23415348                }
 8334349                return true;
 350            }
 351
 36208352            if (!_outgoing.TryGetValue(fromRoot, out var targets))
 16867353            {
 16867354                targets = new HashSet<EdgeId>();
 16867355                _outgoing[fromRoot] = targets;
 16867356            }
 357
 36208358            if (targets.Add(toRoot))
 31623359            {
 360                // also update incoming index
 31623361                if (!_incoming.TryGetValue(toRoot, out var sources))
 18238362                {
 18238363                    sources = new HashSet<EdgeId>();
 18238364                    _incoming[toRoot] = sources;
 18238365                }
 31623366                sources.Add(fromRoot);
 31623367            }
 368
 36208369            return false;
 370        }
 170187371        finally { _lock.ExitWriteLock(); }
 56729372    }
 373
 374    private bool PathExistsNoLock(EdgeId from, EdgeId to)
 44542375    {
 44542376        var fromRoot = this.FindNoLock(from);
 44542377        var toRoot = this.FindNoLock(to);
 44542378        if (fromRoot == toRoot) return true;
 379
 380        // A path needs a first step out of from and a last step into to. Both O(1), both
 381        // usually absent, and the expensive case here is proving there is NO path.
 65716382        if (!_outgoing.ContainsKey(fromRoot)) return false;
 31449383        if (!_incoming.ContainsKey(toRoot)) return false;
 384
 15287385        var visited = _pathVisited;
 15287386        var stack = _pathStack;
 15287387        visited.Clear();
 15287388        stack.Clear();
 15287389        stack.Push(fromRoot);
 390        try
 15287391        {
 69411392            while (stack.Count > 0)
 62458393            {
 394                // No Find on the popped value: everything pushed came from _outgoing,
 395                // which MergeNoLock keeps canonical (OutgoingIsCanonical). _incoming is
 396                // NOT canonical and must still be read through Find - see
 397                // IslandDirectedGraphMirrorTests.
 62458398                var current = stack.Pop();
 70792399                if (current == toRoot) return true;
 55717400                if (!visited.Add(current)) continue;
 71611401                if (!_outgoing.TryGetValue(current, out var outs)) continue;
 402
 220379403                foreach (var o in outs)
 60013404                {
 116842405                    if (!visited.Contains(o)) stack.Push(o);
 60013406                }
 33451407            }
 408
 6953409            return false;
 410        }
 411        finally
 15287412        {
 15287413            if (visited.Count > ScratchKeepCapacity) _pathVisited.TrimExcess();
 15287414        }
 44542415    }
 416
 417    /// <summary>
 418    /// Returns components that are both forward-reachable from <paramref name="forwardStart"/>
 419    /// AND backward-reachable from <paramref name="backwardStart"/>. Used to find the
 420    /// SCC that closes when a new link <c>backwardStart → forwardStart</c> is about
 421    /// to be added.
 422    /// </summary>
 423    private HashSet<EdgeId> IntersectReachableNoLock(EdgeId forwardStart, EdgeId backwardStart)
 8334424    {
 425        // Scratch is reused for the two traversals; the result is not, because the caller
 426        // adds to it and iterates it after this returns.
 8334427        var forward = _sccForward;
 8334428        var stack = _sccStack;
 8334429        forward.Clear();
 8334430        stack.Clear();
 8334431        stack.Push(this.FindNoLock(forwardStart));
 65389432        while (stack.Count > 0)
 57055433        {
 434            // _outgoing is canonical, so no Find on the way out.
 57055435            var current = stack.Pop();
 61394436            if (!forward.Add(current)) continue;
 75819437            if (!_outgoing.TryGetValue(current, out var outs)) continue;
 438
 201347439            foreach (var o in outs)
 56254440            {
 104975441                if (!forward.Contains(o)) stack.Push(o);
 56254442            }
 29613443        }
 444
 8334445        var result = new HashSet<EdgeId>();
 8334446        var backward = _sccBackward;
 8334447        backward.Clear();
 8334448        stack.Clear();
 8334449        stack.Push(this.FindNoLock(backwardStart));
 64534450        while (stack.Count > 0)
 56200451        {
 452            // _incoming is NOT canonical - it deliberately keeps absorbed roots, and
 453            // removing them hangs a real route. So the backward walk still resolves every
 454            // entry through Find.
 56200455            var current = this.FindNoLock(stack.Pop());
 60486456            if (!backward.Add(current)) continue;
 75329457            if (forward.Contains(current)) result.Add(current);
 73518458            if (!_incoming.TryGetValue(current, out var ins)) continue;
 459
 294464460            foreach (var i in ins)
 101767461            {
 101767462                var r = this.FindNoLock(i);
 149633463                if (!backward.Contains(r)) stack.Push(r);
 101767464            }
 30310465        }
 466
 8334467        if (forward.Count > ScratchKeepCapacity) _sccForward.TrimExcess();
 8334468        if (backward.Count > ScratchKeepCapacity) _sccBackward.TrimExcess();
 469
 8334470        return result;
 8334471    }
 472
 473    public bool HasDirectedLink(EdgeId from, EdgeId to)
 0474    {
 0475        _lock.EnterReadLock();
 476        try
 0477        {
 0478            var fromRoot = this.FindNoLock(from);
 0479            var toRoot = this.FindNoLock(to);
 0480            return _outgoing.TryGetValue(fromRoot, out var targets) && targets.Contains(toRoot);
 481        }
 0482        finally { _lock.ExitReadLock(); }
 0483    }
 484
 485    public void Merge(EdgeId a, EdgeId b)
 0486    {
 0487        _lock.EnterWriteLock();
 0488        try { this.MergeNoLock(a, b); }
 0489        finally { _lock.ExitWriteLock(); }
 0490    }
 491
 492    private void MergeNoLock(EdgeId a, EdgeId b)
 19601493    {
 19601494        var rootA = this.FindNoLock(a);
 19601495        var rootB = this.FindNoLock(b);
 19601496        if (rootA == rootB) return;
 497
 498        // sentinel always wins
 19601499        var sentinelRoot = this.FindNoLock(MainNetworkSentinel);
 19601500        if (rootB == sentinelRoot)
 1492501            (rootA, rootB) = (rootB, rootA);
 18109502        else if (rootA != sentinelRoot && _rank[rootA] < _rank[rootB])
 2750503            (rootA, rootB) = (rootB, rootA);
 504
 19601505        _parent[rootB] = rootA;
 19601506        if (rootA != sentinelRoot)
 10675507        {
 10675508            _size[rootA] += _size[rootB];
 13231509            if (_rank[rootA] == _rank[rootB]) _rank[rootA]++;
 10675510        }
 511
 512        // merge outgoing
 19601513        if (_outgoing.TryGetValue(rootB, out var bOut))
 13646514        {
 13646515            if (!_outgoing.TryGetValue(rootA, out var aOut))
 1769516            {
 1769517                aOut = new HashSet<EdgeId>();
 1769518                _outgoing[rootA] = aOut;
 1769519            }
 520
 83006521            foreach (var t in bOut)
 21034522            {
 21034523                var tRoot = this.FindNoLock(t);
 21034524                if (tRoot != rootA)
 9645525                {
 9645526                    aOut.Add(tRoot);
 527                    // update incoming: t's incoming should point to rootA not rootB
 9645528                    if (_incoming.TryGetValue(tRoot, out var tInc))
 9645529                    {
 9645530                        tInc.Remove(rootB);
 9645531                        tInc.Add(rootA);
 9645532                    }
 9645533                }
 21034534            }
 535
 13646536            _outgoing.Remove(rootB);
 13646537        }
 538
 539        // merge incoming
 19601540        if (_incoming.TryGetValue(rootB, out var bInc))
 13653541        {
 13653542            if (!_incoming.TryGetValue(rootA, out var aInc))
 408543            {
 408544                aInc = new HashSet<EdgeId>();
 408545                _incoming[rootA] = aInc;
 408546            }
 547
 88049548            foreach (var s in bInc)
 23545549            {
 23545550                var sRoot = this.FindNoLock(s);
 23545551                if (sRoot != rootA)
 13824552                {
 13824553                    aInc.Add(sRoot);
 554                    // update outgoing: s's outgoing should point to rootA not rootB
 13824555                    if (_outgoing.TryGetValue(sRoot, out var sOut))
 13824556                    {
 13824557                        sOut.Remove(rootB);
 13824558                        sOut.Add(rootA);
 13824559                    }
 13824560                }
 23545561            }
 562
 13653563            _incoming.Remove(rootB);
 13653564        }
 565
 566        // remove self-loops, including rootB which has just become part of rootA
 19601567        if (_outgoing.TryGetValue(rootA, out var aOutFinal))
 17554568        {
 17554569            aOutFinal.Remove(rootA);
 17554570            aOutFinal.Remove(rootB);
 17554571        }
 572
 19601573        if (_incoming.TryGetValue(rootA, out var aIncFinal))
 17581574        {
 17581575            aIncFinal.Remove(rootA);
 17581576        }
 577
 578        // merge members
 19601579        if (_members.TryGetValue(rootB, out var bMembers))
 19601580        {
 19601581            if (rootA == sentinelRoot)
 8926582            {
 8926583                _members.Remove(rootB);
 8926584            }
 585            else
 10675586            {
 10675587                if (!_members.TryGetValue(rootA, out var aMembers))
 0588                {
 0589                    aMembers = new List<EdgeId>();
 0590                    _members[rootA] = aMembers;
 0591                }
 10675592                aMembers.AddRange(bMembers);
 10675593                _members.Remove(rootB);
 10675594            }
 19601595        }
 19601596    }
 597
 598    public void CollapseToMainNetwork(EdgeId root)
 6686599    {
 6686600        _lock.EnterWriteLock();
 601        try
 6686602        {
 6686603            root = this.FindNoLock(root);
 8852604            if (root == this.FindNoLock(MainNetworkSentinel)) return;
 4520605            this.MergeNoLock(MainNetworkSentinel, root);
 4520606        }
 20058607        finally { _lock.ExitWriteLock(); }
 6686608    }
 609
 610    public void RemoveEdge(EdgeId edgeId)
 0611    {
 0612        _lock.EnterWriteLock();
 613        try
 0614        {
 0615            var root = this.FindNoLock(edgeId);
 616
 0617            if (_members.TryGetValue(root, out var members))
 0618            {
 0619                members.Remove(edgeId);
 0620                if (members.Count == 0)
 0621                {
 0622                    _members.Remove(root);
 623
 624                    // clean up adjacency
 0625                    if (_outgoing.TryGetValue(root, out var targets))
 0626                    {
 0627                        foreach (var t in targets)
 0628                        {
 0629                            if (_incoming.TryGetValue(this.FindNoLock(t), out var tInc))
 0630                                tInc.Remove(root);
 0631                        }
 0632                        _outgoing.Remove(root);
 0633                    }
 634
 0635                    if (_incoming.TryGetValue(root, out var sources))
 0636                    {
 0637                        foreach (var s in sources)
 0638                        {
 0639                            if (_outgoing.TryGetValue(this.FindNoLock(s), out var sOut))
 0640                                sOut.Remove(root);
 0641                        }
 0642                        _incoming.Remove(root);
 0643                    }
 0644                }
 0645            }
 646
 0647            _parent.Remove(edgeId);
 0648            _processed.TryRemove(edgeId, out _);
 0649        }
 0650        finally { _lock.ExitWriteLock(); }
 0651    }
 652
 653    /// <summary>
 654    /// O(1) dead-end check using incoming index.
 655    /// </summary>
 656    /// <summary>
 657    /// Resets the graph to the state of a freshly-constructed instance: the
 658    /// MainNet sentinel as its own (id-self) component, everything else gone.
 659    /// The classifier calls this at the end of each <see cref="IslandClassifier.BuildForTileAsync"/>
 660    /// so the dg never accumulates per-tile edge ids across tiles, per the
 661    /// "Tile-based batching and persistence" section of the island-detection
 662    /// spec. Cross-tile MainNet membership is recovered via
 663    /// <see cref="Islands.GetTileDone"/> on subsequent classifications, so
 664    /// dropping the in-dg MainNet membership loses no information.
 665    /// </summary>
 666    public void DiscardAllExceptSentinel()
 0667    {
 0668        _lock.EnterWriteLock();
 669        try
 0670        {
 0671            _parent.Clear();
 0672            _rank.Clear();
 0673            _size.Clear();
 0674            _members.Clear();
 0675            _outgoing.Clear();
 0676            _incoming.Clear();
 0677            _processed.Clear();
 678
 0679            _parent[MainNetworkSentinel] = MainNetworkSentinel;
 0680            _rank[MainNetworkSentinel] = int.MaxValue;
 0681            _size[MainNetworkSentinel] = int.MaxValue;
 0682        }
 0683        finally { _lock.ExitWriteLock(); }
 0684    }
 685
 686    public bool IsDeadEnd(EdgeId edgeId)
 0687    {
 0688        _lock.EnterReadLock();
 689        try
 0690        {
 0691            var root = this.FindNoLock(edgeId);
 0692            if (root == this.FindNoLock(MainNetworkSentinel)) return false;
 693
 0694            var hasOutgoing = _outgoing.TryGetValue(root, out var targets) && targets.Count > 0;
 0695            if (!hasOutgoing) return true;
 696
 0697            var hasIncoming = _incoming.TryGetValue(root, out var sources) && sources.Count > 0;
 0698            return !hasIncoming;
 699        }
 0700        finally { _lock.ExitReadLock(); }
 0701    }
 702
 703    /// <summary>
 704    /// Checks if this edge can reach the sentinel in BOTH directions.
 705    /// </summary>
 706    public bool CanReachMainNetwork(EdgeId edgeId)
 0707    {
 0708        _lock.EnterReadLock();
 709        try
 0710        {
 0711            var root = this.FindNoLock(edgeId);
 0712            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0713            if (root == sentinel) return true;
 714
 0715            var visited = new HashSet<EdgeId>();
 0716            var canForward = this.DfsCanReach(root, sentinel, visited, true);
 0717            if (!canForward) return false;
 718
 0719            visited.Clear();
 0720            return this.DfsCanReach(root, sentinel, visited, false);
 721        }
 0722        finally { _lock.ExitReadLock(); }
 0723    }
 724
 725    /// <summary>
 726    /// Diagnostic: returns (canForward, canBackward) one-direction reachability
 727    /// to <see cref="MainNetworkSentinel"/>. <c>(true,true)</c> matches
 728    /// <see cref="CanReachMainNetwork"/>; the other combinations expose the
 729    /// asymmetric cases.
 730    /// </summary>
 731    public (bool canForward, bool canBackward) ReachMainNetworkDirections(EdgeId edgeId)
 0732    {
 0733        _lock.EnterReadLock();
 734        try
 0735        {
 0736            var root = this.FindNoLock(edgeId);
 0737            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0738            if (root == sentinel) return (true, true);
 739
 0740            var visited = new HashSet<EdgeId>();
 0741            var canForward = this.DfsCanReach(root, sentinel, visited, true);
 0742            visited.Clear();
 0743            var canBackward = this.DfsCanReach(root, sentinel, visited, false);
 0744            return (canForward, canBackward);
 745        }
 0746        finally { _lock.ExitReadLock(); }
 0747    }
 748
 749    /// <summary>
 750    /// Returns the union-find roots this edge's component has outgoing dg links
 751    /// to (after <see cref="Find"/> canonicalisation). Includes the sentinel if
 752    /// the component links to it.
 753    /// </summary>
 754    public List<EdgeId> GetOutgoingRoots(EdgeId edgeId)
 3265755    {
 3265756        var result = new List<EdgeId>();
 3265757        _lock.EnterReadLock();
 758        try
 3265759        {
 3265760            if (!_parent.ContainsKey(edgeId)) return result;
 3265761            var root = this.FindNoLock(edgeId);
 3265762            if (_outgoing.TryGetValue(root, out var outs))
 1739763            {
 1739764                var seen = new HashSet<EdgeId>();
 5579765                foreach (var o in outs)
 181766                {
 181767                    if (o == root) continue;
 362768                    if (seen.Add(o)) result.Add(o);
 181769                }
 1739770            }
 3265771        }
 9795772        finally { _lock.ExitReadLock(); }
 3265773        return result;
 3265774    }
 775
 776    /// <summary>
 777    /// Returns the union-find roots this edge's component has incoming dg links
 778    /// from (after <see cref="Find"/> canonicalisation). Includes the sentinel
 779    /// if the sentinel links to the component.
 780    /// </summary>
 781    public List<EdgeId> GetIncomingRoots(EdgeId edgeId)
 1672782    {
 1672783        var result = new List<EdgeId>();
 1672784        _lock.EnterReadLock();
 785        try
 1672786        {
 1672787            if (!_parent.ContainsKey(edgeId)) return result;
 1672788            var root = this.FindNoLock(edgeId);
 1672789            if (_incoming.TryGetValue(root, out var ins))
 1635790            {
 1635791                var seen = new HashSet<EdgeId>();
 12813792                foreach (var i in ins)
 3954793                {
 3954794                    var r = this.FindNoLock(i);
 7716795                    if (r == root) continue;
 384796                    if (seen.Add(r)) result.Add(r);
 192797                }
 1635798            }
 1672799        }
 5016800        finally { _lock.ExitReadLock(); }
 1672801        return result;
 1672802    }
 803
 804    /// <summary>
 805    /// Returns the union-find roots that this edge's component is directionally
 806    /// linked to (outgoing ∪ incoming), excluding the sentinel. Used by the
 807    /// edge-frontier BFS to keep expanding through already-processed edges:
 808    /// the dg knows their links from prior calls' processing, so the BFS can
 809    /// continue without re-doing the merge work.
 810    /// </summary>
 811    public List<EdgeId> GetLinkedNeighbourRoots(EdgeId edgeId)
 0812    {
 0813        var result = new List<EdgeId>();
 0814        _lock.EnterReadLock();
 815        try
 0816        {
 0817            if (!_parent.ContainsKey(edgeId)) return result;
 0818            var root = this.FindNoLock(edgeId);
 0819            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0820            if (_outgoing.TryGetValue(root, out var outs))
 0821            {
 0822                foreach (var o in outs)
 0823                {
 0824                    if (o != sentinel) result.Add(o);
 0825                }
 0826            }
 0827            if (_incoming.TryGetValue(root, out var ins))
 0828            {
 0829                foreach (var i in ins)
 0830                {
 0831                    var r = this.FindNoLock(i);
 0832                    if (r != sentinel && !result.Contains(r)) result.Add(r);
 0833                }
 0834            }
 0835        }
 0836        finally { _lock.ExitReadLock(); }
 0837        return result;
 0838    }
 839
 840    private bool DfsCanReach(EdgeId current, EdgeId target, HashSet<EdgeId> visited, bool forward)
 0841    {
 0842        current = this.FindNoLock(current);
 0843        if (current == target) return true;
 0844        if (!visited.Add(current)) return false;
 845
 0846        var adj = forward
 0847            ? (_outgoing.TryGetValue(current, out var o) ? o : null)
 0848            : (_incoming.TryGetValue(current, out var i) ? i : null);
 849
 0850        if (adj == null) return false;
 851
 0852        foreach (var next in adj)
 0853        {
 0854            if (this.DfsCanReach(this.FindNoLock(next), target, visited, forward)) return true;
 0855        }
 856
 0857        return false;
 0858    }
 859
 860    /// <summary>
 861    /// Detects cycles among the given candidate roots and merges them.
 862    /// Uses Tarjan's SCC algorithm on the subgraph of candidates.
 863    /// Returns true if any merges happened.
 864    /// </summary>
 865    public bool DetectAndMergeCycles(List<EdgeId> candidateRoots)
 0866    {
 0867        _lock.EnterWriteLock();
 868        try
 0869        {
 870            // build the set of roots to consider
 0871            var rootSet = new HashSet<EdgeId>();
 0872            foreach (var c in candidateRoots)
 0873            {
 0874                var r = this.FindNoLock(c);
 0875                if (r != this.FindNoLock(MainNetworkSentinel))
 0876                    rootSet.Add(r);
 0877            }
 878
 0879            if (rootSet.Count < 2) return false;
 880
 881            // Tarjan's SCC
 0882            var index = 0;
 0883            var stack = new Stack<EdgeId>();
 0884            var onStack = new HashSet<EdgeId>();
 0885            var indices = new Dictionary<EdgeId, int>();
 0886            var lowLinks = new Dictionary<EdgeId, int>();
 0887            var sccs = new List<List<EdgeId>>();
 888
 0889            foreach (var v in rootSet)
 0890            {
 0891                if (!indices.ContainsKey(v))
 0892                    this.Strongconnect(v, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0893            }
 894
 895            // merge SCCs with more than one vertex
 0896            var merged = false;
 0897            foreach (var scc in sccs)
 0898            {
 0899                if (scc.Count < 2) continue;
 0900                for (var i = 1; i < scc.Count; i++)
 0901                {
 0902                    this.MergeNoLock(scc[0], scc[i]);
 0903                }
 0904                merged = true;
 0905            }
 906
 0907            return merged;
 908        }
 0909        finally { _lock.ExitWriteLock(); }
 0910    }
 911
 912    private void Strongconnect(EdgeId v, HashSet<EdgeId> rootSet,
 913        ref int index, Stack<EdgeId> stack, HashSet<EdgeId> onStack,
 914        Dictionary<EdgeId, int> indices, Dictionary<EdgeId, int> lowLinks,
 915        List<List<EdgeId>> sccs)
 0916    {
 0917        indices[v] = index;
 0918        lowLinks[v] = index;
 0919        index++;
 0920        stack.Push(v);
 0921        onStack.Add(v);
 922
 0923        if (_outgoing.TryGetValue(v, out var targets))
 0924        {
 0925            foreach (var t in targets)
 0926            {
 0927                var w = this.FindNoLock(t);
 0928                if (!rootSet.Contains(w)) continue; // only consider candidates
 929
 0930                if (!indices.ContainsKey(w))
 0931                {
 0932                    this.Strongconnect(w, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0933                    lowLinks[v] = System.Math.Min(lowLinks[v], lowLinks[w]);
 0934                }
 0935                else if (onStack.Contains(w))
 0936                {
 0937                    lowLinks[v] = System.Math.Min(lowLinks[v], indices[w]);
 0938                }
 0939            }
 0940        }
 941
 0942        if (lowLinks[v] == indices[v])
 0943        {
 0944            var scc = new List<EdgeId>();
 945            EdgeId w;
 946            do
 0947            {
 0948                w = stack.Pop();
 0949                onStack.Remove(w);
 0950                scc.Add(w);
 0951            } while (w != v);
 952
 0953            sccs.Add(scc);
 0954        }
 0955    }
 956
 957    /// <summary>
 958    /// Walks up the union-find chain to the root. Acquires the read lock; for callers
 959    /// that already hold the lock (read or write), use <see cref="FindNoLock"/>.
 960    /// </summary>
 961    public EdgeId Find(EdgeId x)
 406824962    {
 406824963        _lock.EnterReadLock();
 813648964        try { return this.FindNoLock(x); }
 1220472965        finally { _lock.ExitReadLock(); }
 406824966    }
 967
 968    /// <summary>
 969    /// Lock-free Find for use inside methods that already hold _lock. Intentionally
 970    /// does NOT path-compress: the graph is built once then queried from many concurrent
 971    /// snap calls; compressing would mutate <see cref="_parent"/> during reads and
 972    /// require an exclusive lock for every Find. Without compression each Find is
 973    /// O(log n) thanks to rank-balanced unions in <see cref="MergeNoLock"/> — fast
 974    /// enough for the snap path.
 975    /// </summary>
 976    private EdgeId FindNoLock(EdgeId x)
 1271788977    {
 1271788978        if (!_parent.TryGetValue(x, out var parent)) return x;
 1725275979        while (parent != x)
 453487980        {
 453487981            x = parent;
 453487982            if (!_parent.TryGetValue(x, out parent)) return x;
 453487983        }
 1271788984        return x;
 1271788985    }
 986}