< 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:320
Uncovered lines:201
Coverable lines:521
Total lines:766
Line coverage:61.4% (320 of 521)
Covered branches:122
Total branches:224
Branch coverage:54.4% (122 of 224)
Tag:267_28791001112

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.cctor()100%1100%
.ctor()100%1100%
AddVertex(...)100%2100%
IsInGraph(...)100%1100%
GetAllEdges()75%483.33%
IsProcessed(...)100%1100%
SetProcessed(...)100%1100%
IsNotIsland(...)100%2100%
GetSize(...)100%1100%
GetMembers(...)100%2100%
AddDirectedLink(...)92.85%14100%
PathExistsNoLock(...)92.85%14100%
IntersectReachableNoLock(...)100%22100%
HasDirectedLink(...)0%20%
Merge(...)100%10%
MergeNoLock(...)97.61%4295%
CollapseToMainNetwork(...)100%2100%
RemoveEdge(...)0%160%
DiscardAllExceptSentinel()100%1100%
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.Generic;
 2using System.Threading;
 3using Itinero.Network.Enumerators.Edges;
 4
 5namespace Itinero.Network.Search.Islands;
 6
 7/// <summary>
 8/// A directed meta-graph for island detection.
 9/// Each vertex represents one or more routing edges (merged via union-find).
 10/// Directed links represent travel direction between edge groups.
 11/// </summary>
 12internal class IslandDirectedGraph
 13{
 114    internal static readonly EdgeId MainNetworkSentinel = new(uint.MaxValue - 1, uint.MaxValue - 1);
 15
 8516    private readonly Dictionary<EdgeId, EdgeId> _parent = new();
 8517    private readonly Dictionary<EdgeId, int> _rank = new();
 8518    private readonly Dictionary<EdgeId, int> _size = new();
 8519    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _outgoing = new();
 8520    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _incoming = new();
 8521    private readonly Dictionary<EdgeId, List<EdgeId>> _members = new();
 8522    private readonly HashSet<EdgeId> _processed = new();
 23
 24    // The graph is built incrementally (mutations) and queried concurrently from
 25    // many snap operations. The underlying Dictionaries / HashSets are not safe
 26    // for read-during-write — concurrent IsNotIsland calls during an in-flight
 27    // ProcessEdge corrupt the dict and throw "concurrent update". A reader-writer
 28    // lock keeps reads concurrent against each other (cheap on the snap path)
 29    // and exclusive against any mutation.
 8530    private readonly ReaderWriterLockSlim _lock = new(LockRecursionPolicy.SupportsRecursion);
 31
 8532    public IslandDirectedGraph()
 8533    {
 8534        _parent[MainNetworkSentinel] = MainNetworkSentinel;
 8535        _rank[MainNetworkSentinel] = int.MaxValue;
 8536        _size[MainNetworkSentinel] = int.MaxValue;
 8537    }
 38
 39    public void AddVertex(EdgeId edgeId)
 719640    {
 719641        _lock.EnterWriteLock();
 42        try
 719643        {
 1120744            if (_parent.ContainsKey(edgeId)) return;
 318545            _parent[edgeId] = edgeId;
 318546            _rank[edgeId] = 0;
 318547            _size[edgeId] = 1;
 318548            _members[edgeId] = new List<EdgeId> { edgeId };
 318549        }
 2158850        finally { _lock.ExitWriteLock(); }
 719651    }
 52
 53    public bool IsInGraph(EdgeId edgeId)
 154    {
 155        _lock.EnterReadLock();
 256        try { return _parent.ContainsKey(edgeId); }
 357        finally { _lock.ExitReadLock(); }
 158    }
 59
 60    /// <summary>
 61    /// Returns a snapshot of every edge currently in the graph, excluding the
 62    /// <see cref="MainNetworkSentinel"/>. Intended for callers that need to
 63    /// feed every known edge into a global resolution pass (e.g. Tarjan SCC
 64    /// over the full set of one-way singletons forming a cycle).
 65    /// </summary>
 66    public List<EdgeId> GetAllEdges()
 5067    {
 5068        _lock.EnterReadLock();
 69        try
 5070        {
 5071            var result = new List<EdgeId>(_parent.Count);
 25072            foreach (var k in _parent.Keys)
 5073            {
 10074                if (k == MainNetworkSentinel) continue;
 075                result.Add(k);
 076            }
 5077            return result;
 78        }
 15079        finally { _lock.ExitReadLock(); }
 5080    }
 81
 82    public bool IsProcessed(EdgeId edgeId)
 26686783    {
 26686784        _lock.EnterReadLock();
 53373485        try { return _processed.Contains(edgeId); }
 80060186        finally { _lock.ExitReadLock(); }
 26686787    }
 88
 89    public void SetProcessed(EdgeId edgeId)
 114590    {
 114591        _lock.EnterWriteLock();
 343592        try { _processed.Add(edgeId); }
 343593        finally { _lock.ExitWriteLock(); }
 114594    }
 95
 96    public bool IsNotIsland(EdgeId edgeId)
 1063697    {
 1063698        _lock.EnterReadLock();
 99        try
 10636100        {
 13649101            if (!_parent.ContainsKey(edgeId)) return false;
 7623102            return this.FindNoLock(edgeId) == this.FindNoLock(MainNetworkSentinel);
 103        }
 31908104        finally { _lock.ExitReadLock(); }
 10636105    }
 106
 107    public int GetSize(EdgeId edgeId)
 1621108    {
 1621109        _lock.EnterReadLock();
 3242110        try { return _size[this.FindNoLock(edgeId)]; }
 4863111        finally { _lock.ExitReadLock(); }
 1621112    }
 113
 114    public List<EdgeId>? GetMembers(EdgeId edgeId)
 4754115    {
 4754116        _lock.EnterReadLock();
 117        try
 4754118        {
 4754119            var root = this.FindNoLock(edgeId);
 120            // Snapshot — callers iterate outside the lock and concurrent
 121            // merges / RemoveEdge would otherwise mutate the list out from
 122            // under them.
 4754123            return _members.TryGetValue(root, out var m) ? new List<EdgeId>(m) : null;
 124        }
 14262125        finally { _lock.ExitReadLock(); }
 4754126    }
 127
 128    /// <summary>
 129    /// Adds a directed link <paramref name="from"/> → <paramref name="to"/> to the
 130    /// graph, with **eager cycle detection**: if a path already exists in the dg
 131    /// from <paramref name="to"/>'s component back to <paramref name="from"/>'s
 132    /// component, the new link closes a strongly-connected component. All
 133    /// components on every path back are merged into one node (F ∩ R: forward
 134    /// reachable from <paramref name="to"/> ∩ backward reachable from
 135    /// <paramref name="from"/>). Returns <c>true</c> when this happens, so the
 136    /// caller can size-check the merged component for MainNet graduation.
 137    /// Returns <c>false</c> when the link was a regular edge (no cycle closed).
 138    /// </summary>
 139    public bool AddDirectedLink(EdgeId from, EdgeId to)
 3635140    {
 3635141        _lock.EnterWriteLock();
 142        try
 3635143        {
 3635144            var fromRoot = this.FindNoLock(from);
 3635145            var toRoot = this.FindNoLock(to);
 3635146            if (fromRoot == toRoot) return false;
 147
 148            // Eager cycle-merge: if there's already a path toRoot ↝ fromRoot
 149            // in the existing graph, adding from→to closes an SCC. Collapse
 150            // every component on a closing path into one node.
 3635151            if (this.PathExistsNoLock(toRoot, fromRoot))
 1622152            {
 1622153                var sccRoots = this.IntersectReachableNoLock(toRoot, fromRoot);
 1622154                sccRoots.Add(fromRoot);
 1622155                sccRoots.Add(toRoot);
 1622156                EdgeId target = fromRoot;
 11984157                foreach (var r in sccRoots)
 3559158                {
 3559159                    if (this.FindNoLock(r) != this.FindNoLock(target))
 1937160                        this.MergeNoLock(target, r);
 3559161                }
 1622162                return true;
 163            }
 164
 2013165            if (!_outgoing.TryGetValue(fromRoot, out var targets))
 544166            {
 544167                targets = new HashSet<EdgeId>();
 544168                _outgoing[fromRoot] = targets;
 544169            }
 170
 2013171            if (targets.Add(toRoot))
 1962172            {
 173                // also update incoming index
 1962174                if (!_incoming.TryGetValue(toRoot, out var sources))
 1831175                {
 1831176                    sources = new HashSet<EdgeId>();
 1831177                    _incoming[toRoot] = sources;
 1831178                }
 1962179                sources.Add(fromRoot);
 1962180            }
 181
 2013182            return false;
 183        }
 10905184        finally { _lock.ExitWriteLock(); }
 3635185    }
 186
 187    private bool PathExistsNoLock(EdgeId from, EdgeId to)
 3635188    {
 3635189        if (this.FindNoLock(from) == this.FindNoLock(to)) return true;
 3635190        var visited = new HashSet<EdgeId>();
 3635191        var stack = new Stack<EdgeId>();
 3635192        stack.Push(this.FindNoLock(from));
 7751193        while (stack.Count > 0)
 5738194        {
 5738195            var current = this.FindNoLock(stack.Pop());
 7360196            if (current == this.FindNoLock(to)) return true;
 4125197            if (!visited.Add(current)) continue;
 4107198            if (_outgoing.TryGetValue(current, out var outs))
 2180199            {
 271550200                foreach (var o in outs)
 132505201                {
 132505202                    var r = this.FindNoLock(o);
 134783203                    if (!visited.Contains(r)) stack.Push(r);
 132505204                }
 2180205            }
 4107206        }
 2013207        return false;
 3635208    }
 209
 210    /// <summary>
 211    /// Returns components that are both forward-reachable from <paramref name="forwardStart"/>
 212    /// AND backward-reachable from <paramref name="backwardStart"/>. Used to find the
 213    /// SCC that closes when a new link <c>backwardStart → forwardStart</c> is about
 214    /// to be added.
 215    /// </summary>
 216    private HashSet<EdgeId> IntersectReachableNoLock(EdgeId forwardStart, EdgeId backwardStart)
 1622217    {
 1622218        var forward = new HashSet<EdgeId>();
 1622219        {
 1622220            var stack = new Stack<EdgeId>();
 1622221            stack.Push(this.FindNoLock(forwardStart));
 5415222            while (stack.Count > 0)
 3793223            {
 3793224                var current = this.FindNoLock(stack.Pop());
 3803225                if (!forward.Add(current)) continue;
 3783226                if (_outgoing.TryGetValue(current, out var outs))
 2101227                {
 269277228                    foreach (var o in outs)
 131487229                    {
 131487230                        var r = this.FindNoLock(o);
 133658231                        if (!forward.Contains(r)) stack.Push(r);
 131487232                    }
 2101233                }
 3783234            }
 1622235        }
 1622236        var result = new HashSet<EdgeId>();
 1622237        var bStack = new Stack<EdgeId>();
 1622238        var bVisited = new HashSet<EdgeId>();
 1622239        bStack.Push(this.FindNoLock(backwardStart));
 5384240        while (bStack.Count > 0)
 3762241        {
 3762242            var current = this.FindNoLock(bStack.Pop());
 3762243            if (!bVisited.Add(current)) continue;
 7321244            if (forward.Contains(current)) result.Add(current);
 3762245            if (_incoming.TryGetValue(current, out var ins))
 3370246            {
 21660247                foreach (var i in ins)
 5775248                {
 5775249                    var r = this.FindNoLock(i);
 7915250                    if (!bVisited.Contains(r)) bStack.Push(r);
 5775251                }
 3370252            }
 3762253        }
 1622254        return result;
 1622255    }
 256
 257    public bool HasDirectedLink(EdgeId from, EdgeId to)
 0258    {
 0259        _lock.EnterReadLock();
 260        try
 0261        {
 0262            var fromRoot = this.FindNoLock(from);
 0263            var toRoot = this.FindNoLock(to);
 0264            return _outgoing.TryGetValue(fromRoot, out var targets) && targets.Contains(toRoot);
 265        }
 0266        finally { _lock.ExitReadLock(); }
 0267    }
 268
 269    public void Merge(EdgeId a, EdgeId b)
 0270    {
 0271        _lock.EnterWriteLock();
 0272        try { this.MergeNoLock(a, b); }
 0273        finally { _lock.ExitWriteLock(); }
 0274    }
 275
 276    private void MergeNoLock(EdgeId a, EdgeId b)
 3145277    {
 3145278        var rootA = this.FindNoLock(a);
 3145279        var rootB = this.FindNoLock(b);
 3145280        if (rootA == rootB) return;
 281
 282        // sentinel always wins
 3145283        var sentinelRoot = this.FindNoLock(MainNetworkSentinel);
 3145284        if (rootB == sentinelRoot)
 42285            (rootA, rootB) = (rootB, rootA);
 3103286        else if (rootA != sentinelRoot && _rank[rootA] < _rank[rootB])
 1248287            (rootA, rootB) = (rootB, rootA);
 288
 3145289        _parent[rootB] = rootA;
 3145290        if (rootA != sentinelRoot)
 1770291        {
 1770292            _size[rootA] += _size[rootB];
 1977293            if (_rank[rootA] == _rank[rootB]) _rank[rootA]++;
 1770294        }
 295
 296        // merge outgoing
 3145297        if (_outgoing.TryGetValue(rootB, out var bOut))
 728298        {
 728299            if (!_outgoing.TryGetValue(rootA, out var aOut))
 280300            {
 280301                aOut = new HashSet<EdgeId>();
 280302                _outgoing[rootA] = aOut;
 280303            }
 304
 6016305            foreach (var t in bOut)
 1916306            {
 1916307                var tRoot = this.FindNoLock(t);
 1916308                if (tRoot != rootA)
 21309                {
 21310                    aOut.Add(tRoot);
 311                    // update incoming: t's incoming should point to rootA not rootB
 21312                    if (_incoming.TryGetValue(tRoot, out var tInc))
 21313                    {
 21314                        tInc.Remove(rootB);
 21315                        tInc.Add(rootA);
 21316                    }
 21317                }
 1916318            }
 319
 728320            _outgoing.Remove(rootB);
 728321        }
 322
 323        // merge incoming
 3145324        if (_incoming.TryGetValue(rootB, out var bInc))
 1805325        {
 1805326            if (!_incoming.TryGetValue(rootA, out var aInc))
 72327            {
 72328                aInc = new HashSet<EdgeId>();
 72329                _incoming[rootA] = aInc;
 72330            }
 331
 9081332            foreach (var s in bInc)
 1833333            {
 1833334                var sRoot = this.FindNoLock(s);
 1833335                if (sRoot != rootA)
 330336                {
 330337                    aInc.Add(sRoot);
 338                    // update outgoing: s's outgoing should point to rootA not rootB
 330339                    if (_outgoing.TryGetValue(sRoot, out var sOut))
 330340                    {
 330341                        sOut.Remove(rootB);
 330342                        sOut.Add(rootA);
 330343                    }
 330344                }
 1833345            }
 346
 1805347            _incoming.Remove(rootB);
 1805348        }
 349
 350        // remove self-loops
 3145351        if (_outgoing.TryGetValue(rootA, out var aOutFinal))
 2012352            aOutFinal.Remove(rootA);
 3145353        if (_incoming.TryGetValue(rootA, out var aIncFinal))
 2012354            aIncFinal.Remove(rootA);
 355
 356        // merge members
 3145357        if (_members.TryGetValue(rootB, out var bMembers))
 3145358        {
 3145359            if (rootA == sentinelRoot)
 1375360            {
 1375361                _members.Remove(rootB);
 1375362            }
 363            else
 1770364            {
 1770365                if (!_members.TryGetValue(rootA, out var aMembers))
 0366                {
 0367                    aMembers = new List<EdgeId>();
 0368                    _members[rootA] = aMembers;
 0369                }
 1770370                aMembers.AddRange(bMembers);
 1770371                _members.Remove(rootB);
 1770372            }
 3145373        }
 3145374    }
 375
 376    public void CollapseToMainNetwork(EdgeId root)
 1372377    {
 1372378        _lock.EnterWriteLock();
 379        try
 1372380        {
 1372381            root = this.FindNoLock(root);
 1536382            if (root == this.FindNoLock(MainNetworkSentinel)) return;
 1208383            this.MergeNoLock(MainNetworkSentinel, root);
 1208384        }
 4116385        finally { _lock.ExitWriteLock(); }
 1372386    }
 387
 388    public void RemoveEdge(EdgeId edgeId)
 0389    {
 0390        _lock.EnterWriteLock();
 391        try
 0392        {
 0393            var root = this.FindNoLock(edgeId);
 394
 0395            if (_members.TryGetValue(root, out var members))
 0396            {
 0397                members.Remove(edgeId);
 0398                if (members.Count == 0)
 0399                {
 0400                    _members.Remove(root);
 401
 402                    // clean up adjacency
 0403                    if (_outgoing.TryGetValue(root, out var targets))
 0404                    {
 0405                        foreach (var t in targets)
 0406                        {
 0407                            if (_incoming.TryGetValue(this.FindNoLock(t), out var tInc))
 0408                                tInc.Remove(root);
 0409                        }
 0410                        _outgoing.Remove(root);
 0411                    }
 412
 0413                    if (_incoming.TryGetValue(root, out var sources))
 0414                    {
 0415                        foreach (var s in sources)
 0416                        {
 0417                            if (_outgoing.TryGetValue(this.FindNoLock(s), out var sOut))
 0418                                sOut.Remove(root);
 0419                        }
 0420                        _incoming.Remove(root);
 0421                    }
 0422                }
 0423            }
 424
 0425            _parent.Remove(edgeId);
 0426            _processed.Remove(edgeId);
 0427        }
 0428        finally { _lock.ExitWriteLock(); }
 0429    }
 430
 431    /// <summary>
 432    /// O(1) dead-end check using incoming index.
 433    /// </summary>
 434    /// <summary>
 435    /// Resets the graph to the state of a freshly-constructed instance: the
 436    /// MainNet sentinel as its own (id-self) component, everything else gone.
 437    /// The classifier calls this at the end of each <see cref="IslandClassifier.BuildForTileAsync"/>
 438    /// so the dg never accumulates per-tile edge ids across tiles, per the
 439    /// "Tile-based batching and persistence" section of the island-detection
 440    /// spec. Cross-tile MainNet membership is recovered via
 441    /// <see cref="Islands.GetTileDone"/> on subsequent classifications, so
 442    /// dropping the in-dg MainNet membership loses no information.
 443    /// </summary>
 444    public void DiscardAllExceptSentinel()
 120445    {
 120446        _lock.EnterWriteLock();
 447        try
 120448        {
 120449            _parent.Clear();
 120450            _rank.Clear();
 120451            _size.Clear();
 120452            _members.Clear();
 120453            _outgoing.Clear();
 120454            _incoming.Clear();
 120455            _processed.Clear();
 456
 120457            _parent[MainNetworkSentinel] = MainNetworkSentinel;
 120458            _rank[MainNetworkSentinel] = int.MaxValue;
 120459            _size[MainNetworkSentinel] = int.MaxValue;
 120460        }
 360461        finally { _lock.ExitWriteLock(); }
 120462    }
 463
 464    public bool IsDeadEnd(EdgeId edgeId)
 0465    {
 0466        _lock.EnterReadLock();
 467        try
 0468        {
 0469            var root = this.FindNoLock(edgeId);
 0470            if (root == this.FindNoLock(MainNetworkSentinel)) return false;
 471
 0472            var hasOutgoing = _outgoing.TryGetValue(root, out var targets) && targets.Count > 0;
 0473            if (!hasOutgoing) return true;
 474
 0475            var hasIncoming = _incoming.TryGetValue(root, out var sources) && sources.Count > 0;
 0476            return !hasIncoming;
 477        }
 0478        finally { _lock.ExitReadLock(); }
 0479    }
 480
 481    /// <summary>
 482    /// Checks if this edge can reach the sentinel in BOTH directions.
 483    /// </summary>
 484    public bool CanReachMainNetwork(EdgeId edgeId)
 0485    {
 0486        _lock.EnterReadLock();
 487        try
 0488        {
 0489            var root = this.FindNoLock(edgeId);
 0490            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0491            if (root == sentinel) return true;
 492
 0493            var visited = new HashSet<EdgeId>();
 0494            var canForward = this.DfsCanReach(root, sentinel, visited, true);
 0495            if (!canForward) return false;
 496
 0497            visited.Clear();
 0498            return this.DfsCanReach(root, sentinel, visited, false);
 499        }
 0500        finally { _lock.ExitReadLock(); }
 0501    }
 502
 503    /// <summary>
 504    /// Diagnostic: returns (canForward, canBackward) one-direction reachability
 505    /// to <see cref="MainNetworkSentinel"/>. <c>(true,true)</c> matches
 506    /// <see cref="CanReachMainNetwork"/>; the other combinations expose the
 507    /// asymmetric cases.
 508    /// </summary>
 509    public (bool canForward, bool canBackward) ReachMainNetworkDirections(EdgeId edgeId)
 0510    {
 0511        _lock.EnterReadLock();
 512        try
 0513        {
 0514            var root = this.FindNoLock(edgeId);
 0515            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0516            if (root == sentinel) return (true, true);
 517
 0518            var visited = new HashSet<EdgeId>();
 0519            var canForward = this.DfsCanReach(root, sentinel, visited, true);
 0520            visited.Clear();
 0521            var canBackward = this.DfsCanReach(root, sentinel, visited, false);
 0522            return (canForward, canBackward);
 523        }
 0524        finally { _lock.ExitReadLock(); }
 0525    }
 526
 527    /// <summary>
 528    /// Returns the union-find roots this edge's component has outgoing dg links
 529    /// to (after <see cref="Find"/> canonicalisation). Includes the sentinel if
 530    /// the component links to it.
 531    /// </summary>
 532    public List<EdgeId> GetOutgoingRoots(EdgeId edgeId)
 3228533    {
 3228534        var result = new List<EdgeId>();
 3228535        _lock.EnterReadLock();
 536        try
 3228537        {
 3228538            if (!_parent.ContainsKey(edgeId)) return result;
 3228539            var root = this.FindNoLock(edgeId);
 3228540            if (_outgoing.TryGetValue(root, out var outs))
 1722541            {
 1722542                var seen = new HashSet<EdgeId>();
 265082543                foreach (var o in outs)
 129958544                {
 129958545                    var r = this.FindNoLock(o);
 259739546                    if (r == root) continue;
 354547                    if (seen.Add(r)) result.Add(r);
 177548                }
 1722549            }
 3228550        }
 9684551        finally { _lock.ExitReadLock(); }
 3228552        return result;
 3228553    }
 554
 555    /// <summary>
 556    /// Returns the union-find roots this edge's component has incoming dg links
 557    /// from (after <see cref="Find"/> canonicalisation). Includes the sentinel
 558    /// if the sentinel links to the component.
 559    /// </summary>
 560    public List<EdgeId> GetIncomingRoots(EdgeId edgeId)
 1652561    {
 1652562        var result = new List<EdgeId>();
 1652563        _lock.EnterReadLock();
 564        try
 1652565        {
 1652566            if (!_parent.ContainsKey(edgeId)) return result;
 1652567            var root = this.FindNoLock(edgeId);
 1652568            if (_incoming.TryGetValue(root, out var ins))
 1621569            {
 1621570                var seen = new HashSet<EdgeId>();
 12743571                foreach (var i in ins)
 3940572                {
 3940573                    var r = this.FindNoLock(i);
 7689574                    if (r == root) continue;
 382575                    if (seen.Add(r)) result.Add(r);
 191576                }
 1621577            }
 1652578        }
 4956579        finally { _lock.ExitReadLock(); }
 1652580        return result;
 1652581    }
 582
 583    /// <summary>
 584    /// Returns the union-find roots that this edge's component is directionally
 585    /// linked to (outgoing ∪ incoming), excluding the sentinel. Used by the
 586    /// edge-frontier BFS to keep expanding through already-processed edges:
 587    /// the dg knows their links from prior calls' processing, so the BFS can
 588    /// continue without re-doing the merge work.
 589    /// </summary>
 590    public List<EdgeId> GetLinkedNeighbourRoots(EdgeId edgeId)
 0591    {
 0592        var result = new List<EdgeId>();
 0593        _lock.EnterReadLock();
 594        try
 0595        {
 0596            if (!_parent.ContainsKey(edgeId)) return result;
 0597            var root = this.FindNoLock(edgeId);
 0598            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0599            if (_outgoing.TryGetValue(root, out var outs))
 0600            {
 0601                foreach (var o in outs)
 0602                {
 0603                    var r = this.FindNoLock(o);
 0604                    if (r != sentinel) result.Add(r);
 0605                }
 0606            }
 0607            if (_incoming.TryGetValue(root, out var ins))
 0608            {
 0609                foreach (var i in ins)
 0610                {
 0611                    var r = this.FindNoLock(i);
 0612                    if (r != sentinel && !result.Contains(r)) result.Add(r);
 0613                }
 0614            }
 0615        }
 0616        finally { _lock.ExitReadLock(); }
 0617        return result;
 0618    }
 619
 620    private bool DfsCanReach(EdgeId current, EdgeId target, HashSet<EdgeId> visited, bool forward)
 0621    {
 0622        current = this.FindNoLock(current);
 0623        if (current == target) return true;
 0624        if (!visited.Add(current)) return false;
 625
 0626        var adj = forward
 0627            ? (_outgoing.TryGetValue(current, out var o) ? o : null)
 0628            : (_incoming.TryGetValue(current, out var i) ? i : null);
 629
 0630        if (adj == null) return false;
 631
 0632        foreach (var next in adj)
 0633        {
 0634            if (this.DfsCanReach(this.FindNoLock(next), target, visited, forward)) return true;
 0635        }
 636
 0637        return false;
 0638    }
 639
 640    /// <summary>
 641    /// Detects cycles among the given candidate roots and merges them.
 642    /// Uses Tarjan's SCC algorithm on the subgraph of candidates.
 643    /// Returns true if any merges happened.
 644    /// </summary>
 645    public bool DetectAndMergeCycles(List<EdgeId> candidateRoots)
 0646    {
 0647        _lock.EnterWriteLock();
 648        try
 0649        {
 650            // build the set of roots to consider
 0651            var rootSet = new HashSet<EdgeId>();
 0652            foreach (var c in candidateRoots)
 0653            {
 0654                var r = this.FindNoLock(c);
 0655                if (r != this.FindNoLock(MainNetworkSentinel))
 0656                    rootSet.Add(r);
 0657            }
 658
 0659            if (rootSet.Count < 2) return false;
 660
 661            // Tarjan's SCC
 0662            var index = 0;
 0663            var stack = new Stack<EdgeId>();
 0664            var onStack = new HashSet<EdgeId>();
 0665            var indices = new Dictionary<EdgeId, int>();
 0666            var lowLinks = new Dictionary<EdgeId, int>();
 0667            var sccs = new List<List<EdgeId>>();
 668
 0669            foreach (var v in rootSet)
 0670            {
 0671                if (!indices.ContainsKey(v))
 0672                    this.Strongconnect(v, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0673            }
 674
 675            // merge SCCs with more than one vertex
 0676            var merged = false;
 0677            foreach (var scc in sccs)
 0678            {
 0679                if (scc.Count < 2) continue;
 0680                for (var i = 1; i < scc.Count; i++)
 0681                {
 0682                    this.MergeNoLock(scc[0], scc[i]);
 0683                }
 0684                merged = true;
 0685            }
 686
 0687            return merged;
 688        }
 0689        finally { _lock.ExitWriteLock(); }
 0690    }
 691
 692    private void Strongconnect(EdgeId v, HashSet<EdgeId> rootSet,
 693        ref int index, Stack<EdgeId> stack, HashSet<EdgeId> onStack,
 694        Dictionary<EdgeId, int> indices, Dictionary<EdgeId, int> lowLinks,
 695        List<List<EdgeId>> sccs)
 0696    {
 0697        indices[v] = index;
 0698        lowLinks[v] = index;
 0699        index++;
 0700        stack.Push(v);
 0701        onStack.Add(v);
 702
 0703        if (_outgoing.TryGetValue(v, out var targets))
 0704        {
 0705            foreach (var t in targets)
 0706            {
 0707                var w = this.FindNoLock(t);
 0708                if (!rootSet.Contains(w)) continue; // only consider candidates
 709
 0710                if (!indices.ContainsKey(w))
 0711                {
 0712                    this.Strongconnect(w, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0713                    lowLinks[v] = System.Math.Min(lowLinks[v], lowLinks[w]);
 0714                }
 0715                else if (onStack.Contains(w))
 0716                {
 0717                    lowLinks[v] = System.Math.Min(lowLinks[v], indices[w]);
 0718                }
 0719            }
 0720        }
 721
 0722        if (lowLinks[v] == indices[v])
 0723        {
 0724            var scc = new List<EdgeId>();
 725            EdgeId w;
 726            do
 0727            {
 0728                w = stack.Pop();
 0729                onStack.Remove(w);
 0730                scc.Add(w);
 0731            } while (w != v);
 732
 0733            sccs.Add(scc);
 0734        }
 0735    }
 736
 737    /// <summary>
 738    /// Walks up the union-find chain to the root. Acquires the read lock; for callers
 739    /// that already hold the lock (read or write), use <see cref="FindNoLock"/>.
 740    /// </summary>
 741    public EdgeId Find(EdgeId x)
 34528742    {
 34528743        _lock.EnterReadLock();
 69056744        try { return this.FindNoLock(x); }
 103584745        finally { _lock.ExitReadLock(); }
 34528746    }
 747
 748    /// <summary>
 749    /// Lock-free Find for use inside methods that already hold _lock. Intentionally
 750    /// does NOT path-compress: the graph is built once then queried from many concurrent
 751    /// snap calls; compressing would mutate <see cref="_parent"/> during reads and
 752    /// require an exclusive lock for every Find. Without compression each Find is
 753    /// O(log n) thanks to rank-balanced unions in <see cref="MergeNoLock"/> — fast
 754    /// enough for the snap path.
 755    /// </summary>
 756    private EdgeId FindNoLock(EdgeId x)
 528190757    {
 528190758        if (!_parent.TryGetValue(x, out var parent)) return x;
 964790759        while (parent != x)
 436600760        {
 436600761            x = parent;
 436600762            if (!_parent.TryGetValue(x, out parent)) return x;
 436600763        }
 528190764        return x;
 528190765    }
 766}
Generated by: ReportGenerator 4.8.2.0
07/06/2026 - 12:21:39
GitHub | www.palmmedia.de

Methods/Properties

.cctor()
.ctor()
AddVertex(...)
IsInGraph(...)
GetAllEdges()
IsProcessed(...)
SetProcessed(...)
IsNotIsland(...)
GetSize(...)
GetMembers(...)
AddDirectedLink(...)
PathExistsNoLock(...)
IntersectReachableNoLock(...)
HasDirectedLink(...)
Merge(...)
MergeNoLock(...)
CollapseToMainNetwork(...)
RemoveEdge(...)
DiscardAllExceptSentinel()
IsDeadEnd(...)
CanReachMainNetwork(...)
ReachMainNetworkDirections(...)
GetOutgoingRoots(...)
GetIncomingRoots(...)
GetLinkedNeighbourRoots(...)
DfsCanReach(...)
DetectAndMergeCycles(...)
Strongconnect(...)
Find(...)
FindNoLock(...)