< 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:294
Uncovered lines:211
Coverable lines:505
Total lines:736
Line coverage:58.2% (294 of 505)
Covered branches:119
Total branches:224
Branch coverage:53.1% (119 of 224)
Tag:263_26948838820

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.cctor()100%1100%
.ctor()100%1100%
AddVertex(...)100%2100%
IsInGraph(...)100%1100%
GetAllEdges()0%40%
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%
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
 8316    private readonly Dictionary<EdgeId, EdgeId> _parent = new();
 8317    private readonly Dictionary<EdgeId, int> _rank = new();
 8318    private readonly Dictionary<EdgeId, int> _size = new();
 8319    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _outgoing = new();
 8320    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _incoming = new();
 8321    private readonly Dictionary<EdgeId, List<EdgeId>> _members = new();
 8322    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.
 8330    private readonly ReaderWriterLockSlim _lock = new(LockRecursionPolicy.SupportsRecursion);
 31
 8332    public IslandDirectedGraph()
 8333    {
 8334        _parent[MainNetworkSentinel] = MainNetworkSentinel;
 8335        _rank[MainNetworkSentinel] = int.MaxValue;
 8336        _size[MainNetworkSentinel] = int.MaxValue;
 8337    }
 38
 39    public void AddVertex(EdgeId edgeId)
 699640    {
 699641        _lock.EnterWriteLock();
 42        try
 699643        {
 1100744            if (_parent.ContainsKey(edgeId)) return;
 298545            _parent[edgeId] = edgeId;
 298546            _rank[edgeId] = 0;
 298547            _size[edgeId] = 1;
 298548            _members[edgeId] = new List<EdgeId> { edgeId };
 298549        }
 2098850        finally { _lock.ExitWriteLock(); }
 699651    }
 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()
 067    {
 068        _lock.EnterReadLock();
 69        try
 070        {
 071            var result = new List<EdgeId>(_parent.Count);
 072            foreach (var k in _parent.Keys)
 073            {
 074                if (k == MainNetworkSentinel) continue;
 075                result.Add(k);
 076            }
 077            return result;
 78        }
 079        finally { _lock.ExitReadLock(); }
 080    }
 81
 82    public bool IsProcessed(EdgeId edgeId)
 26681783    {
 26681784        _lock.EnterReadLock();
 53363485        try { return _processed.Contains(edgeId); }
 80045186        finally { _lock.ExitReadLock(); }
 26681787    }
 88
 89    public void SetProcessed(EdgeId edgeId)
 109590    {
 109591        _lock.EnterWriteLock();
 328592        try { _processed.Add(edgeId); }
 328593        finally { _lock.ExitWriteLock(); }
 109594    }
 95
 96    public bool IsNotIsland(EdgeId edgeId)
 1023697    {
 1023698        _lock.EnterReadLock();
 99        try
 10236100        {
 13048101            if (!_parent.ContainsKey(edgeId)) return false;
 7424102            return this.FindNoLock(edgeId) == this.FindNoLock(MainNetworkSentinel);
 103        }
 30708104        finally { _lock.ExitReadLock(); }
 10236105    }
 106
 107    public int GetSize(EdgeId edgeId)
 1571108    {
 1571109        _lock.EnterReadLock();
 3142110        try { return _size[this.FindNoLock(edgeId)]; }
 4713111        finally { _lock.ExitReadLock(); }
 1571112    }
 113
 114    public List<EdgeId>? GetMembers(EdgeId edgeId)
 4604115    {
 4604116        _lock.EnterReadLock();
 117        try
 4604118        {
 4604119            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.
 4604123            return _members.TryGetValue(root, out var m) ? new List<EdgeId>(m) : null;
 124        }
 13812125        finally { _lock.ExitReadLock(); }
 4604126    }
 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)
 3535140    {
 3535141        _lock.EnterWriteLock();
 142        try
 3535143        {
 3535144            var fromRoot = this.FindNoLock(from);
 3535145            var toRoot = this.FindNoLock(to);
 3535146            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.
 3535151            if (this.PathExistsNoLock(toRoot, fromRoot))
 1572152            {
 1572153                var sccRoots = this.IntersectReachableNoLock(toRoot, fromRoot);
 1572154                sccRoots.Add(fromRoot);
 1572155                sccRoots.Add(toRoot);
 1572156                EdgeId target = fromRoot;
 11634157                foreach (var r in sccRoots)
 3459158                {
 3459159                    if (this.FindNoLock(r) != this.FindNoLock(target))
 1887160                        this.MergeNoLock(target, r);
 3459161                }
 1572162                return true;
 163            }
 164
 1963165            if (!_outgoing.TryGetValue(fromRoot, out var targets))
 494166            {
 494167                targets = new HashSet<EdgeId>();
 494168                _outgoing[fromRoot] = targets;
 494169            }
 170
 1963171            if (targets.Add(toRoot))
 1912172            {
 173                // also update incoming index
 1912174                if (!_incoming.TryGetValue(toRoot, out var sources))
 1780175                {
 1780176                    sources = new HashSet<EdgeId>();
 1780177                    _incoming[toRoot] = sources;
 1780178                }
 1912179                sources.Add(fromRoot);
 1912180            }
 181
 1963182            return false;
 183        }
 10605184        finally { _lock.ExitWriteLock(); }
 3535185    }
 186
 187    private bool PathExistsNoLock(EdgeId from, EdgeId to)
 3535188    {
 3535189        if (this.FindNoLock(from) == this.FindNoLock(to)) return true;
 3535190        var visited = new HashSet<EdgeId>();
 3535191        var stack = new Stack<EdgeId>();
 3535192        stack.Push(this.FindNoLock(from));
 7551193        while (stack.Count > 0)
 5588194        {
 5588195            var current = this.FindNoLock(stack.Pop());
 7160196            if (current == this.FindNoLock(to)) return true;
 4025197            if (!visited.Add(current)) continue;
 4007198            if (_outgoing.TryGetValue(current, out var outs))
 2131199            {
 272593200                foreach (var o in outs)
 133100201                {
 133100202                    var r = this.FindNoLock(o);
 135328203                    if (!visited.Contains(r)) stack.Push(r);
 133100204                }
 2131205            }
 4007206        }
 1963207        return false;
 3535208    }
 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)
 1572217    {
 1572218        var forward = new HashSet<EdgeId>();
 1572219        {
 1572220            var stack = new Stack<EdgeId>();
 1572221            stack.Push(this.FindNoLock(forwardStart));
 5265222            while (stack.Count > 0)
 3693223            {
 3693224                var current = this.FindNoLock(stack.Pop());
 3703225                if (!forward.Add(current)) continue;
 3683226                if (_outgoing.TryGetValue(current, out var outs))
 2052227                {
 270320228                    foreach (var o in outs)
 132082229                    {
 132082230                        var r = this.FindNoLock(o);
 134203231                        if (!forward.Contains(r)) stack.Push(r);
 132082232                    }
 2052233                }
 3683234            }
 1572235        }
 1572236        var result = new HashSet<EdgeId>();
 1572237        var bStack = new Stack<EdgeId>();
 1572238        var bVisited = new HashSet<EdgeId>();
 1572239        bStack.Push(this.FindNoLock(backwardStart));
 5234240        while (bStack.Count > 0)
 3662241        {
 3662242            var current = this.FindNoLock(bStack.Pop());
 3662243            if (!bVisited.Add(current)) continue;
 7121244            if (forward.Contains(current)) result.Add(current);
 3662245            if (_incoming.TryGetValue(current, out var ins))
 3320246            {
 27042247                foreach (var i in ins)
 8541248                {
 8541249                    var r = this.FindNoLock(i);
 10631250                    if (!bVisited.Contains(r)) bStack.Push(r);
 8541251                }
 3320252            }
 3662253        }
 1572254        return result;
 1572255    }
 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)
 2945277    {
 2945278        var rootA = this.FindNoLock(a);
 2945279        var rootB = this.FindNoLock(b);
 2945280        if (rootA == rootB) return;
 281
 282        // sentinel always wins
 2945283        var sentinelRoot = this.FindNoLock(MainNetworkSentinel);
 2945284        if (rootB == sentinelRoot)
 42285            (rootA, rootB) = (rootB, rootA);
 2903286        else if (rootA != sentinelRoot && _rank[rootA] < _rank[rootB])
 1248287            (rootA, rootB) = (rootB, rootA);
 288
 2945289        _parent[rootB] = rootA;
 2945290        if (rootA != sentinelRoot)
 1720291        {
 1720292            _size[rootA] += _size[rootB];
 1877293            if (_rank[rootA] == _rank[rootB]) _rank[rootA]++;
 1720294        }
 295
 296        // merge outgoing
 2945297        if (_outgoing.TryGetValue(rootB, out var bOut))
 628298        {
 628299            if (!_outgoing.TryGetValue(rootA, out var aOut))
 178300            {
 178301                aOut = new HashSet<EdgeId>();
 178302                _outgoing[rootA] = aOut;
 178303            }
 304
 5616305            foreach (var t in bOut)
 1866306            {
 1866307                var tRoot = this.FindNoLock(t);
 1866308                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                }
 1866318            }
 319
 628320            _outgoing.Remove(rootB);
 628321        }
 322
 323        // merge incoming
 2945324        if (_incoming.TryGetValue(rootB, out var bInc))
 1755325        {
 1755326            if (!_incoming.TryGetValue(rootA, out var aInc))
 21327            {
 21328                aInc = new HashSet<EdgeId>();
 21329                _incoming[rootA] = aInc;
 21330            }
 331
 8831332            foreach (var s in bInc)
 1783333            {
 1783334                var sRoot = this.FindNoLock(s);
 1783335                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                }
 1783345            }
 346
 1755347            _incoming.Remove(rootB);
 1755348        }
 349
 350        // remove self-loops
 2945351        if (_outgoing.TryGetValue(rootA, out var aOutFinal))
 1912352            aOutFinal.Remove(rootA);
 2945353        if (_incoming.TryGetValue(rootA, out var aIncFinal))
 1912354            aIncFinal.Remove(rootA);
 355
 356        // merge members
 2945357        if (_members.TryGetValue(rootB, out var bMembers))
 2945358        {
 2945359            if (rootA == sentinelRoot)
 1225360            {
 1225361                _members.Remove(rootB);
 1225362            }
 363            else
 1720364            {
 1720365                if (!_members.TryGetValue(rootA, out var aMembers))
 0366                {
 0367                    aMembers = new List<EdgeId>();
 0368                    _members[rootA] = aMembers;
 0369                }
 1720370                aMembers.AddRange(bMembers);
 1720371                _members.Remove(rootB);
 1720372            }
 2945373        }
 2945374    }
 375
 376    public void CollapseToMainNetwork(EdgeId root)
 1222377    {
 1222378        _lock.EnterWriteLock();
 379        try
 1222380        {
 1222381            root = this.FindNoLock(root);
 1386382            if (root == this.FindNoLock(MainNetworkSentinel)) return;
 1058383            this.MergeNoLock(MainNetworkSentinel, root);
 1058384        }
 3666385        finally { _lock.ExitWriteLock(); }
 1222386    }
 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    public bool IsDeadEnd(EdgeId edgeId)
 0435    {
 0436        _lock.EnterReadLock();
 437        try
 0438        {
 0439            var root = this.FindNoLock(edgeId);
 0440            if (root == this.FindNoLock(MainNetworkSentinel)) return false;
 441
 0442            var hasOutgoing = _outgoing.TryGetValue(root, out var targets) && targets.Count > 0;
 0443            if (!hasOutgoing) return true;
 444
 0445            var hasIncoming = _incoming.TryGetValue(root, out var sources) && sources.Count > 0;
 0446            return !hasIncoming;
 447        }
 0448        finally { _lock.ExitReadLock(); }
 0449    }
 450
 451    /// <summary>
 452    /// Checks if this edge can reach the sentinel in BOTH directions.
 453    /// </summary>
 454    public bool CanReachMainNetwork(EdgeId edgeId)
 0455    {
 0456        _lock.EnterReadLock();
 457        try
 0458        {
 0459            var root = this.FindNoLock(edgeId);
 0460            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0461            if (root == sentinel) return true;
 462
 0463            var visited = new HashSet<EdgeId>();
 0464            var canForward = this.DfsCanReach(root, sentinel, visited, true);
 0465            if (!canForward) return false;
 466
 0467            visited.Clear();
 0468            return this.DfsCanReach(root, sentinel, visited, false);
 469        }
 0470        finally { _lock.ExitReadLock(); }
 0471    }
 472
 473    /// <summary>
 474    /// Diagnostic: returns (canForward, canBackward) one-direction reachability
 475    /// to <see cref="MainNetworkSentinel"/>. <c>(true,true)</c> matches
 476    /// <see cref="CanReachMainNetwork"/>; the other combinations expose the
 477    /// asymmetric cases.
 478    /// </summary>
 479    public (bool canForward, bool canBackward) ReachMainNetworkDirections(EdgeId edgeId)
 0480    {
 0481        _lock.EnterReadLock();
 482        try
 0483        {
 0484            var root = this.FindNoLock(edgeId);
 0485            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0486            if (root == sentinel) return (true, true);
 487
 0488            var visited = new HashSet<EdgeId>();
 0489            var canForward = this.DfsCanReach(root, sentinel, visited, true);
 0490            visited.Clear();
 0491            var canBackward = this.DfsCanReach(root, sentinel, visited, false);
 0492            return (canForward, canBackward);
 493        }
 0494        finally { _lock.ExitReadLock(); }
 0495    }
 496
 497    /// <summary>
 498    /// Returns the union-find roots this edge's component has outgoing dg links
 499    /// to (after <see cref="Find"/> canonicalisation). Includes the sentinel if
 500    /// the component links to it.
 501    /// </summary>
 502    public List<EdgeId> GetOutgoingRoots(EdgeId edgeId)
 3128503    {
 3128504        var result = new List<EdgeId>();
 3128505        _lock.EnterReadLock();
 506        try
 3128507        {
 3128508            if (!_parent.ContainsKey(edgeId)) return result;
 3128509            var root = this.FindNoLock(edgeId);
 3128510            if (_outgoing.TryGetValue(root, out var outs))
 1673511            {
 1673512                var seen = new HashSet<EdgeId>();
 267155513                foreach (var o in outs)
 131068514                {
 131068515                    var r = this.FindNoLock(o);
 261959516                    if (r == root) continue;
 354517                    if (seen.Add(r)) result.Add(r);
 177518                }
 1673519            }
 3128520        }
 9384521        finally { _lock.ExitReadLock(); }
 3128522        return result;
 3128523    }
 524
 525    /// <summary>
 526    /// Returns the union-find roots this edge's component has incoming dg links
 527    /// from (after <see cref="Find"/> canonicalisation). Includes the sentinel
 528    /// if the sentinel links to the component.
 529    /// </summary>
 530    public List<EdgeId> GetIncomingRoots(EdgeId edgeId)
 1602531    {
 1602532        var result = new List<EdgeId>();
 1602533        _lock.EnterReadLock();
 534        try
 1602535        {
 1602536            if (!_parent.ContainsKey(edgeId)) return result;
 1602537            var root = this.FindNoLock(edgeId);
 1602538            if (_incoming.TryGetValue(root, out var ins))
 1571539            {
 1571540                var seen = new HashSet<EdgeId>();
 18289541                foreach (var i in ins)
 6788542                {
 6788543                    var r = this.FindNoLock(i);
 13385544                    if (r == root) continue;
 382545                    if (seen.Add(r)) result.Add(r);
 191546                }
 1571547            }
 1602548        }
 4806549        finally { _lock.ExitReadLock(); }
 1602550        return result;
 1602551    }
 552
 553    /// <summary>
 554    /// Returns the union-find roots that this edge's component is directionally
 555    /// linked to (outgoing ∪ incoming), excluding the sentinel. Used by the
 556    /// edge-frontier BFS to keep expanding through already-processed edges:
 557    /// the dg knows their links from prior calls' processing, so the BFS can
 558    /// continue without re-doing the merge work.
 559    /// </summary>
 560    public List<EdgeId> GetLinkedNeighbourRoots(EdgeId edgeId)
 0561    {
 0562        var result = new List<EdgeId>();
 0563        _lock.EnterReadLock();
 564        try
 0565        {
 0566            if (!_parent.ContainsKey(edgeId)) return result;
 0567            var root = this.FindNoLock(edgeId);
 0568            var sentinel = this.FindNoLock(MainNetworkSentinel);
 0569            if (_outgoing.TryGetValue(root, out var outs))
 0570            {
 0571                foreach (var o in outs)
 0572                {
 0573                    var r = this.FindNoLock(o);
 0574                    if (r != sentinel) result.Add(r);
 0575                }
 0576            }
 0577            if (_incoming.TryGetValue(root, out var ins))
 0578            {
 0579                foreach (var i in ins)
 0580                {
 0581                    var r = this.FindNoLock(i);
 0582                    if (r != sentinel && !result.Contains(r)) result.Add(r);
 0583                }
 0584            }
 0585        }
 0586        finally { _lock.ExitReadLock(); }
 0587        return result;
 0588    }
 589
 590    private bool DfsCanReach(EdgeId current, EdgeId target, HashSet<EdgeId> visited, bool forward)
 0591    {
 0592        current = this.FindNoLock(current);
 0593        if (current == target) return true;
 0594        if (!visited.Add(current)) return false;
 595
 0596        var adj = forward
 0597            ? (_outgoing.TryGetValue(current, out var o) ? o : null)
 0598            : (_incoming.TryGetValue(current, out var i) ? i : null);
 599
 0600        if (adj == null) return false;
 601
 0602        foreach (var next in adj)
 0603        {
 0604            if (this.DfsCanReach(this.FindNoLock(next), target, visited, forward)) return true;
 0605        }
 606
 0607        return false;
 0608    }
 609
 610    /// <summary>
 611    /// Detects cycles among the given candidate roots and merges them.
 612    /// Uses Tarjan's SCC algorithm on the subgraph of candidates.
 613    /// Returns true if any merges happened.
 614    /// </summary>
 615    public bool DetectAndMergeCycles(List<EdgeId> candidateRoots)
 0616    {
 0617        _lock.EnterWriteLock();
 618        try
 0619        {
 620            // build the set of roots to consider
 0621            var rootSet = new HashSet<EdgeId>();
 0622            foreach (var c in candidateRoots)
 0623            {
 0624                var r = this.FindNoLock(c);
 0625                if (r != this.FindNoLock(MainNetworkSentinel))
 0626                    rootSet.Add(r);
 0627            }
 628
 0629            if (rootSet.Count < 2) return false;
 630
 631            // Tarjan's SCC
 0632            var index = 0;
 0633            var stack = new Stack<EdgeId>();
 0634            var onStack = new HashSet<EdgeId>();
 0635            var indices = new Dictionary<EdgeId, int>();
 0636            var lowLinks = new Dictionary<EdgeId, int>();
 0637            var sccs = new List<List<EdgeId>>();
 638
 0639            foreach (var v in rootSet)
 0640            {
 0641                if (!indices.ContainsKey(v))
 0642                    this.Strongconnect(v, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0643            }
 644
 645            // merge SCCs with more than one vertex
 0646            var merged = false;
 0647            foreach (var scc in sccs)
 0648            {
 0649                if (scc.Count < 2) continue;
 0650                for (var i = 1; i < scc.Count; i++)
 0651                {
 0652                    this.MergeNoLock(scc[0], scc[i]);
 0653                }
 0654                merged = true;
 0655            }
 656
 0657            return merged;
 658        }
 0659        finally { _lock.ExitWriteLock(); }
 0660    }
 661
 662    private void Strongconnect(EdgeId v, HashSet<EdgeId> rootSet,
 663        ref int index, Stack<EdgeId> stack, HashSet<EdgeId> onStack,
 664        Dictionary<EdgeId, int> indices, Dictionary<EdgeId, int> lowLinks,
 665        List<List<EdgeId>> sccs)
 0666    {
 0667        indices[v] = index;
 0668        lowLinks[v] = index;
 0669        index++;
 0670        stack.Push(v);
 0671        onStack.Add(v);
 672
 0673        if (_outgoing.TryGetValue(v, out var targets))
 0674        {
 0675            foreach (var t in targets)
 0676            {
 0677                var w = this.FindNoLock(t);
 0678                if (!rootSet.Contains(w)) continue; // only consider candidates
 679
 0680                if (!indices.ContainsKey(w))
 0681                {
 0682                    this.Strongconnect(w, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0683                    lowLinks[v] = System.Math.Min(lowLinks[v], lowLinks[w]);
 0684                }
 0685                else if (onStack.Contains(w))
 0686                {
 0687                    lowLinks[v] = System.Math.Min(lowLinks[v], indices[w]);
 0688                }
 0689            }
 0690        }
 691
 0692        if (lowLinks[v] == indices[v])
 0693        {
 0694            var scc = new List<EdgeId>();
 695            EdgeId w;
 696            do
 0697            {
 0698                w = stack.Pop();
 0699                onStack.Remove(w);
 0700                scc.Add(w);
 0701            } while (w != v);
 702
 0703            sccs.Add(scc);
 0704        }
 0705    }
 706
 707    /// <summary>
 708    /// Walks up the union-find chain to the root. Acquires the read lock; for callers
 709    /// that already hold the lock (read or write), use <see cref="FindNoLock"/>.
 710    /// </summary>
 711    public EdgeId Find(EdgeId x)
 33928712    {
 33928713        _lock.EnterReadLock();
 67856714        try { return this.FindNoLock(x); }
 101784715        finally { _lock.ExitReadLock(); }
 33928716    }
 717
 718    /// <summary>
 719    /// Lock-free Find for use inside methods that already hold _lock. Intentionally
 720    /// does NOT path-compress: the graph is built once then queried from many concurrent
 721    /// snap calls; compressing would mutate <see cref="_parent"/> during reads and
 722    /// require an exclusive lock for every Find. Without compression each Find is
 723    /// O(log n) thanks to rank-balanced unions in <see cref="MergeNoLock"/> — fast
 724    /// enough for the snap path.
 725    /// </summary>
 726    private EdgeId FindNoLock(EdgeId x)
 532456727    {
 532456728        if (!_parent.TryGetValue(x, out var parent)) return x;
 976422729        while (parent != x)
 443966730        {
 443966731            x = parent;
 443966732            if (!_parent.TryGetValue(x, out parent)) return x;
 443966733        }
 532456734        return x;
 532456735    }
 736}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

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