| | | 1 | | using System.Collections.Concurrent; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Threading; |
| | | 4 | | using Itinero.Network.Enumerators.Edges; |
| | | 5 | | |
| | | 6 | | namespace 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> |
| | | 13 | | internal class IslandDirectedGraph |
| | | 14 | | { |
| | 1 | 15 | | internal static readonly EdgeId MainNetworkSentinel = new(uint.MaxValue - 1, uint.MaxValue - 1); |
| | | 16 | | |
| | 1228 | 17 | | private readonly Dictionary<EdgeId, EdgeId> _parent = new(); |
| | 1228 | 18 | | private readonly Dictionary<EdgeId, int> _rank = new(); |
| | 1228 | 19 | | private readonly Dictionary<EdgeId, int> _size = new(); |
| | 1228 | 20 | | private readonly Dictionary<EdgeId, HashSet<EdgeId>> _outgoing = new(); |
| | 1228 | 21 | | private readonly Dictionary<EdgeId, HashSet<EdgeId>> _incoming = new(); |
| | 1228 | 22 | | private readonly Dictionary<EdgeId, List<EdgeId>> _members = new(); |
| | 1228 | 23 | | 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. |
| | 1228 | 31 | | 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. |
| | 1228 | 37 | | private readonly HashSet<EdgeId> _pathVisited = new(); |
| | 1228 | 38 | | private readonly Stack<EdgeId> _pathStack = new(); |
| | 1228 | 39 | | private readonly HashSet<EdgeId> _sccForward = new(); |
| | 1228 | 40 | | private readonly HashSet<EdgeId> _sccBackward = new(); |
| | 1228 | 41 | | 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 | | |
| | 1228 | 46 | | public IslandDirectedGraph() |
| | 1228 | 47 | | { |
| | 1228 | 48 | | _parent[MainNetworkSentinel] = MainNetworkSentinel; |
| | 1228 | 49 | | _rank[MainNetworkSentinel] = int.MaxValue; |
| | 1228 | 50 | | _size[MainNetworkSentinel] = int.MaxValue; |
| | 1228 | 51 | | } |
| | | 52 | | |
| | | 53 | | public void AddVertex(EdgeId edgeId) |
| | 30517 | 54 | | { |
| | 30517 | 55 | | _lock.EnterWriteLock(); |
| | | 56 | | try |
| | 30517 | 57 | | { |
| | 34536 | 58 | | if (_parent.ContainsKey(edgeId)) return; |
| | 26498 | 59 | | _parent[edgeId] = edgeId; |
| | 26498 | 60 | | _rank[edgeId] = 0; |
| | 26498 | 61 | | _size[edgeId] = 1; |
| | 26498 | 62 | | _members[edgeId] = new List<EdgeId> { edgeId }; |
| | 26498 | 63 | | } |
| | 91551 | 64 | | finally { _lock.ExitWriteLock(); } |
| | 30517 | 65 | | } |
| | | 66 | | |
| | | 67 | | public bool IsInGraph(EdgeId edgeId) |
| | 1 | 68 | | { |
| | 1 | 69 | | _lock.EnterReadLock(); |
| | 2 | 70 | | try { return _parent.ContainsKey(edgeId); } |
| | 3 | 71 | | finally { _lock.ExitReadLock(); } |
| | 1 | 72 | | } |
| | | 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() |
| | 50 | 81 | | { |
| | 50 | 82 | | _lock.EnterReadLock(); |
| | | 83 | | try |
| | 50 | 84 | | { |
| | 50 | 85 | | var result = new List<EdgeId>(_parent.Count); |
| | 250 | 86 | | foreach (var k in _parent.Keys) |
| | 50 | 87 | | { |
| | 100 | 88 | | if (k == MainNetworkSentinel) continue; |
| | 0 | 89 | | result.Add(k); |
| | 0 | 90 | | } |
| | 50 | 91 | | return result; |
| | | 92 | | } |
| | 150 | 93 | | finally { _lock.ExitReadLock(); } |
| | 50 | 94 | | } |
| | | 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) |
| | 25253 | 110 | | { |
| | 25253 | 111 | | _lock.EnterReadLock(); |
| | | 112 | | try |
| | 25253 | 113 | | { |
| | 457533 | 114 | | foreach (var (root, targets) in _outgoing) |
| | 190887 | 115 | | { |
| | 1150215 | 116 | | foreach (var t in targets) |
| | 288777 | 117 | | { |
| | 577554 | 118 | | if (this.FindNoLock(t) == t) continue; |
| | 0 | 119 | | failure = $"_outgoing[{root}] holds stale {t}, root is {this.FindNoLock(t)}"; |
| | 0 | 120 | | return false; |
| | | 121 | | } |
| | 190887 | 122 | | } |
| | | 123 | | |
| | 25253 | 124 | | failure = ""; |
| | 25253 | 125 | | return true; |
| | | 126 | | } |
| | 75759 | 127 | | finally { _lock.ExitReadLock(); } |
| | 25253 | 128 | | } |
| | | 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) |
| | 0 | 142 | | { |
| | 0 | 143 | | _lock.EnterReadLock(); |
| | | 144 | | try |
| | 0 | 145 | | { |
| | 0 | 146 | | foreach (var (root, sources) in _incoming) |
| | 0 | 147 | | { |
| | 0 | 148 | | foreach (var f in sources) |
| | 0 | 149 | | { |
| | 0 | 150 | | if (this.FindNoLock(f) == f) continue; |
| | 0 | 151 | | failure = $"_incoming[{root}] holds stale {f}, root is {this.FindNoLock(f)}"; |
| | 0 | 152 | | return false; |
| | | 153 | | } |
| | 0 | 154 | | } |
| | | 155 | | |
| | 0 | 156 | | failure = ""; |
| | 0 | 157 | | return true; |
| | | 158 | | } |
| | 0 | 159 | | finally { _lock.ExitReadLock(); } |
| | 0 | 160 | | } |
| | | 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) |
| | 240 | 167 | | { |
| | 240 | 168 | | _lock.EnterReadLock(); |
| | | 169 | | try |
| | 240 | 170 | | { |
| | 240 | 171 | | var state = new Dictionary<EdgeId, int>(); |
| | 1787 | 172 | | foreach (var start in _outgoing.Keys) |
| | 535 | 173 | | { |
| | 689 | 174 | | if (state.TryGetValue(start, out var st) && st == 2) continue; |
| | | 175 | | |
| | 381 | 176 | | var stack = new Stack<(EdgeId node, IEnumerator<EdgeId>? iter)>(); |
| | 381 | 177 | | stack.Push((start, null)); |
| | 381 | 178 | | state[start] = 1; |
| | 1503 | 179 | | while (stack.Count > 0) |
| | 1125 | 180 | | { |
| | 1125 | 181 | | var (node, iter) = stack.Pop(); |
| | 1125 | 182 | | iter ??= _outgoing.TryGetValue(node, out var outs) ? outs.GetEnumerator() : null; |
| | 1125 | 183 | | var advanced = false; |
| | 1394 | 184 | | while (iter != null && iter.MoveNext()) |
| | 646 | 185 | | { |
| | 646 | 186 | | var next = iter.Current; |
| | 646 | 187 | | if (next == node) continue; |
| | 646 | 188 | | state.TryGetValue(next, out var ns); |
| | 646 | 189 | | if (ns == 1) |
| | 3 | 190 | | { |
| | 3 | 191 | | cycle = $"{node} -> {next} closes a cycle"; |
| | 3 | 192 | | return true; |
| | | 193 | | } |
| | | 194 | | |
| | 912 | 195 | | if (ns == 2) continue; |
| | | 196 | | |
| | 374 | 197 | | stack.Push((node, iter)); |
| | 374 | 198 | | stack.Push((next, null)); |
| | 374 | 199 | | state[next] = 1; |
| | 374 | 200 | | advanced = true; |
| | 374 | 201 | | break; |
| | | 202 | | } |
| | | 203 | | |
| | 1870 | 204 | | if (!advanced) state[node] = 2; |
| | 1122 | 205 | | } |
| | 378 | 206 | | } |
| | | 207 | | |
| | 237 | 208 | | cycle = ""; |
| | 237 | 209 | | return false; |
| | | 210 | | } |
| | 720 | 211 | | finally { _lock.ExitReadLock(); } |
| | 240 | 212 | | } |
| | | 213 | | |
| | | 214 | | internal bool AdjacencyIsMirrored(out string failure) |
| | 1 | 215 | | { |
| | 1 | 216 | | _lock.EnterReadLock(); |
| | | 217 | | try |
| | 1 | 218 | | { |
| | 9 | 219 | | foreach (var (from, targets) in _outgoing) |
| | 3 | 220 | | { |
| | 15 | 221 | | foreach (var to in targets) |
| | 3 | 222 | | { |
| | 6 | 223 | | if (_incoming.TryGetValue(to, out var sources) && sources.Contains(from)) continue; |
| | | 224 | | |
| | 0 | 225 | | failure = $"_outgoing[{from}] has {to}, but _incoming[{to}] does not have {from}"; |
| | 0 | 226 | | return false; |
| | | 227 | | } |
| | 3 | 228 | | } |
| | | 229 | | |
| | 7 | 230 | | foreach (var (to, sources) in _incoming) |
| | 2 | 231 | | { |
| | 12 | 232 | | foreach (var from in sources) |
| | 3 | 233 | | { |
| | 6 | 234 | | if (_outgoing.TryGetValue(from, out var targets) && targets.Contains(to)) continue; |
| | | 235 | | |
| | 0 | 236 | | failure = $"_incoming[{to}] has {from}, but _outgoing[{from}] does not have {to}"; |
| | 0 | 237 | | return false; |
| | | 238 | | } |
| | 2 | 239 | | } |
| | | 240 | | |
| | 1 | 241 | | failure = ""; |
| | 1 | 242 | | return true; |
| | | 243 | | } |
| | 3 | 244 | | finally { _lock.ExitReadLock(); } |
| | 1 | 245 | | } |
| | | 246 | | |
| | | 247 | | public bool IsProcessed(EdgeId edgeId) |
| | 64803 | 248 | | { |
| | 64803 | 249 | | return _processed.ContainsKey(edgeId); |
| | 64803 | 250 | | } |
| | | 251 | | |
| | | 252 | | public void SetProcessed(EdgeId edgeId) |
| | 1162 | 253 | | { |
| | 1162 | 254 | | _processed[edgeId] = 0; |
| | 1162 | 255 | | } |
| | | 256 | | |
| | | 257 | | public bool IsNotIsland(EdgeId edgeId) |
| | 13138 | 258 | | { |
| | 13138 | 259 | | _lock.EnterReadLock(); |
| | | 260 | | try |
| | 13138 | 261 | | { |
| | 16236 | 262 | | if (!_parent.ContainsKey(edgeId)) return false; |
| | 10040 | 263 | | return this.FindNoLock(edgeId) == this.FindNoLock(MainNetworkSentinel); |
| | | 264 | | } |
| | 39414 | 265 | | finally { _lock.ExitReadLock(); } |
| | 13138 | 266 | | } |
| | | 267 | | |
| | | 268 | | public int GetSize(EdgeId edgeId) |
| | 1640 | 269 | | { |
| | 1640 | 270 | | _lock.EnterReadLock(); |
| | 3280 | 271 | | try { return _size[this.FindNoLock(edgeId)]; } |
| | 4920 | 272 | | finally { _lock.ExitReadLock(); } |
| | 1640 | 273 | | } |
| | | 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) |
| | 4815 | 294 | | { |
| | 4815 | 295 | | _lock.EnterWriteLock(); |
| | | 296 | | try |
| | 4815 | 297 | | { |
| | 4815 | 298 | | var root = this.FindNoLock(edgeId); |
| | 5300 | 299 | | if (!_members.TryGetValue(root, out var m)) return false; |
| | | 300 | | |
| | 136332 | 301 | | for (var i = m.Count - 1; i >= 0; i--) |
| | 63836 | 302 | | { |
| | 126785 | 303 | | if (!_processed.ContainsKey(m[i])) continue; |
| | 887 | 304 | | m[i] = m[^1]; |
| | 887 | 305 | | m.RemoveAt(m.Count - 1); |
| | 887 | 306 | | } |
| | | 307 | | |
| | 4330 | 308 | | into.Clear(); |
| | 4330 | 309 | | into.AddRange(m); |
| | 4330 | 310 | | return true; |
| | | 311 | | } |
| | 14445 | 312 | | finally { _lock.ExitWriteLock(); } |
| | 4815 | 313 | | } |
| | | 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) |
| | 56729 | 327 | | { |
| | 56729 | 328 | | _lock.EnterWriteLock(); |
| | | 329 | | try |
| | 56729 | 330 | | { |
| | 56729 | 331 | | var fromRoot = this.FindNoLock(from); |
| | 56729 | 332 | | var toRoot = this.FindNoLock(to); |
| | 68916 | 333 | | 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. |
| | 44542 | 338 | | if (this.PathExistsNoLock(toRoot, fromRoot)) |
| | 8334 | 339 | | { |
| | 8334 | 340 | | var sccRoots = this.IntersectReachableNoLock(toRoot, fromRoot); |
| | 8334 | 341 | | sccRoots.Add(fromRoot); |
| | 8334 | 342 | | sccRoots.Add(toRoot); |
| | 8334 | 343 | | EdgeId target = fromRoot; |
| | 71832 | 344 | | foreach (var r in sccRoots) |
| | 23415 | 345 | | { |
| | 23415 | 346 | | if (this.FindNoLock(r) != this.FindNoLock(target)) |
| | 15081 | 347 | | this.MergeNoLock(target, r); |
| | 23415 | 348 | | } |
| | 8334 | 349 | | return true; |
| | | 350 | | } |
| | | 351 | | |
| | 36208 | 352 | | if (!_outgoing.TryGetValue(fromRoot, out var targets)) |
| | 16867 | 353 | | { |
| | 16867 | 354 | | targets = new HashSet<EdgeId>(); |
| | 16867 | 355 | | _outgoing[fromRoot] = targets; |
| | 16867 | 356 | | } |
| | | 357 | | |
| | 36208 | 358 | | if (targets.Add(toRoot)) |
| | 31623 | 359 | | { |
| | | 360 | | // also update incoming index |
| | 31623 | 361 | | if (!_incoming.TryGetValue(toRoot, out var sources)) |
| | 18238 | 362 | | { |
| | 18238 | 363 | | sources = new HashSet<EdgeId>(); |
| | 18238 | 364 | | _incoming[toRoot] = sources; |
| | 18238 | 365 | | } |
| | 31623 | 366 | | sources.Add(fromRoot); |
| | 31623 | 367 | | } |
| | | 368 | | |
| | 36208 | 369 | | return false; |
| | | 370 | | } |
| | 170187 | 371 | | finally { _lock.ExitWriteLock(); } |
| | 56729 | 372 | | } |
| | | 373 | | |
| | | 374 | | private bool PathExistsNoLock(EdgeId from, EdgeId to) |
| | 44542 | 375 | | { |
| | 44542 | 376 | | var fromRoot = this.FindNoLock(from); |
| | 44542 | 377 | | var toRoot = this.FindNoLock(to); |
| | 44542 | 378 | | 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. |
| | 65716 | 382 | | if (!_outgoing.ContainsKey(fromRoot)) return false; |
| | 31449 | 383 | | if (!_incoming.ContainsKey(toRoot)) return false; |
| | | 384 | | |
| | 15287 | 385 | | var visited = _pathVisited; |
| | 15287 | 386 | | var stack = _pathStack; |
| | 15287 | 387 | | visited.Clear(); |
| | 15287 | 388 | | stack.Clear(); |
| | 15287 | 389 | | stack.Push(fromRoot); |
| | | 390 | | try |
| | 15287 | 391 | | { |
| | 69411 | 392 | | while (stack.Count > 0) |
| | 62458 | 393 | | { |
| | | 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. |
| | 62458 | 398 | | var current = stack.Pop(); |
| | 70792 | 399 | | if (current == toRoot) return true; |
| | 55717 | 400 | | if (!visited.Add(current)) continue; |
| | 71611 | 401 | | if (!_outgoing.TryGetValue(current, out var outs)) continue; |
| | | 402 | | |
| | 220379 | 403 | | foreach (var o in outs) |
| | 60013 | 404 | | { |
| | 116842 | 405 | | if (!visited.Contains(o)) stack.Push(o); |
| | 60013 | 406 | | } |
| | 33451 | 407 | | } |
| | | 408 | | |
| | 6953 | 409 | | return false; |
| | | 410 | | } |
| | | 411 | | finally |
| | 15287 | 412 | | { |
| | 15287 | 413 | | if (visited.Count > ScratchKeepCapacity) _pathVisited.TrimExcess(); |
| | 15287 | 414 | | } |
| | 44542 | 415 | | } |
| | | 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) |
| | 8334 | 424 | | { |
| | | 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. |
| | 8334 | 427 | | var forward = _sccForward; |
| | 8334 | 428 | | var stack = _sccStack; |
| | 8334 | 429 | | forward.Clear(); |
| | 8334 | 430 | | stack.Clear(); |
| | 8334 | 431 | | stack.Push(this.FindNoLock(forwardStart)); |
| | 65389 | 432 | | while (stack.Count > 0) |
| | 57055 | 433 | | { |
| | | 434 | | // _outgoing is canonical, so no Find on the way out. |
| | 57055 | 435 | | var current = stack.Pop(); |
| | 61394 | 436 | | if (!forward.Add(current)) continue; |
| | 75819 | 437 | | if (!_outgoing.TryGetValue(current, out var outs)) continue; |
| | | 438 | | |
| | 201347 | 439 | | foreach (var o in outs) |
| | 56254 | 440 | | { |
| | 104975 | 441 | | if (!forward.Contains(o)) stack.Push(o); |
| | 56254 | 442 | | } |
| | 29613 | 443 | | } |
| | | 444 | | |
| | 8334 | 445 | | var result = new HashSet<EdgeId>(); |
| | 8334 | 446 | | var backward = _sccBackward; |
| | 8334 | 447 | | backward.Clear(); |
| | 8334 | 448 | | stack.Clear(); |
| | 8334 | 449 | | stack.Push(this.FindNoLock(backwardStart)); |
| | 64534 | 450 | | while (stack.Count > 0) |
| | 56200 | 451 | | { |
| | | 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. |
| | 56200 | 455 | | var current = this.FindNoLock(stack.Pop()); |
| | 60486 | 456 | | if (!backward.Add(current)) continue; |
| | 75329 | 457 | | if (forward.Contains(current)) result.Add(current); |
| | 73518 | 458 | | if (!_incoming.TryGetValue(current, out var ins)) continue; |
| | | 459 | | |
| | 294464 | 460 | | foreach (var i in ins) |
| | 101767 | 461 | | { |
| | 101767 | 462 | | var r = this.FindNoLock(i); |
| | 149633 | 463 | | if (!backward.Contains(r)) stack.Push(r); |
| | 101767 | 464 | | } |
| | 30310 | 465 | | } |
| | | 466 | | |
| | 8334 | 467 | | if (forward.Count > ScratchKeepCapacity) _sccForward.TrimExcess(); |
| | 8334 | 468 | | if (backward.Count > ScratchKeepCapacity) _sccBackward.TrimExcess(); |
| | | 469 | | |
| | 8334 | 470 | | return result; |
| | 8334 | 471 | | } |
| | | 472 | | |
| | | 473 | | public bool HasDirectedLink(EdgeId from, EdgeId to) |
| | 0 | 474 | | { |
| | 0 | 475 | | _lock.EnterReadLock(); |
| | | 476 | | try |
| | 0 | 477 | | { |
| | 0 | 478 | | var fromRoot = this.FindNoLock(from); |
| | 0 | 479 | | var toRoot = this.FindNoLock(to); |
| | 0 | 480 | | return _outgoing.TryGetValue(fromRoot, out var targets) && targets.Contains(toRoot); |
| | | 481 | | } |
| | 0 | 482 | | finally { _lock.ExitReadLock(); } |
| | 0 | 483 | | } |
| | | 484 | | |
| | | 485 | | public void Merge(EdgeId a, EdgeId b) |
| | 0 | 486 | | { |
| | 0 | 487 | | _lock.EnterWriteLock(); |
| | 0 | 488 | | try { this.MergeNoLock(a, b); } |
| | 0 | 489 | | finally { _lock.ExitWriteLock(); } |
| | 0 | 490 | | } |
| | | 491 | | |
| | | 492 | | private void MergeNoLock(EdgeId a, EdgeId b) |
| | 19601 | 493 | | { |
| | 19601 | 494 | | var rootA = this.FindNoLock(a); |
| | 19601 | 495 | | var rootB = this.FindNoLock(b); |
| | 19601 | 496 | | if (rootA == rootB) return; |
| | | 497 | | |
| | | 498 | | // sentinel always wins |
| | 19601 | 499 | | var sentinelRoot = this.FindNoLock(MainNetworkSentinel); |
| | 19601 | 500 | | if (rootB == sentinelRoot) |
| | 1492 | 501 | | (rootA, rootB) = (rootB, rootA); |
| | 18109 | 502 | | else if (rootA != sentinelRoot && _rank[rootA] < _rank[rootB]) |
| | 2750 | 503 | | (rootA, rootB) = (rootB, rootA); |
| | | 504 | | |
| | 19601 | 505 | | _parent[rootB] = rootA; |
| | 19601 | 506 | | if (rootA != sentinelRoot) |
| | 10675 | 507 | | { |
| | 10675 | 508 | | _size[rootA] += _size[rootB]; |
| | 13231 | 509 | | if (_rank[rootA] == _rank[rootB]) _rank[rootA]++; |
| | 10675 | 510 | | } |
| | | 511 | | |
| | | 512 | | // merge outgoing |
| | 19601 | 513 | | if (_outgoing.TryGetValue(rootB, out var bOut)) |
| | 13646 | 514 | | { |
| | 13646 | 515 | | if (!_outgoing.TryGetValue(rootA, out var aOut)) |
| | 1769 | 516 | | { |
| | 1769 | 517 | | aOut = new HashSet<EdgeId>(); |
| | 1769 | 518 | | _outgoing[rootA] = aOut; |
| | 1769 | 519 | | } |
| | | 520 | | |
| | 83006 | 521 | | foreach (var t in bOut) |
| | 21034 | 522 | | { |
| | 21034 | 523 | | var tRoot = this.FindNoLock(t); |
| | 21034 | 524 | | if (tRoot != rootA) |
| | 9645 | 525 | | { |
| | 9645 | 526 | | aOut.Add(tRoot); |
| | | 527 | | // update incoming: t's incoming should point to rootA not rootB |
| | 9645 | 528 | | if (_incoming.TryGetValue(tRoot, out var tInc)) |
| | 9645 | 529 | | { |
| | 9645 | 530 | | tInc.Remove(rootB); |
| | 9645 | 531 | | tInc.Add(rootA); |
| | 9645 | 532 | | } |
| | 9645 | 533 | | } |
| | 21034 | 534 | | } |
| | | 535 | | |
| | 13646 | 536 | | _outgoing.Remove(rootB); |
| | 13646 | 537 | | } |
| | | 538 | | |
| | | 539 | | // merge incoming |
| | 19601 | 540 | | if (_incoming.TryGetValue(rootB, out var bInc)) |
| | 13653 | 541 | | { |
| | 13653 | 542 | | if (!_incoming.TryGetValue(rootA, out var aInc)) |
| | 408 | 543 | | { |
| | 408 | 544 | | aInc = new HashSet<EdgeId>(); |
| | 408 | 545 | | _incoming[rootA] = aInc; |
| | 408 | 546 | | } |
| | | 547 | | |
| | 88049 | 548 | | foreach (var s in bInc) |
| | 23545 | 549 | | { |
| | 23545 | 550 | | var sRoot = this.FindNoLock(s); |
| | 23545 | 551 | | if (sRoot != rootA) |
| | 13824 | 552 | | { |
| | 13824 | 553 | | aInc.Add(sRoot); |
| | | 554 | | // update outgoing: s's outgoing should point to rootA not rootB |
| | 13824 | 555 | | if (_outgoing.TryGetValue(sRoot, out var sOut)) |
| | 13824 | 556 | | { |
| | 13824 | 557 | | sOut.Remove(rootB); |
| | 13824 | 558 | | sOut.Add(rootA); |
| | 13824 | 559 | | } |
| | 13824 | 560 | | } |
| | 23545 | 561 | | } |
| | | 562 | | |
| | 13653 | 563 | | _incoming.Remove(rootB); |
| | 13653 | 564 | | } |
| | | 565 | | |
| | | 566 | | // remove self-loops, including rootB which has just become part of rootA |
| | 19601 | 567 | | if (_outgoing.TryGetValue(rootA, out var aOutFinal)) |
| | 17554 | 568 | | { |
| | 17554 | 569 | | aOutFinal.Remove(rootA); |
| | 17554 | 570 | | aOutFinal.Remove(rootB); |
| | 17554 | 571 | | } |
| | | 572 | | |
| | 19601 | 573 | | if (_incoming.TryGetValue(rootA, out var aIncFinal)) |
| | 17581 | 574 | | { |
| | 17581 | 575 | | aIncFinal.Remove(rootA); |
| | 17581 | 576 | | } |
| | | 577 | | |
| | | 578 | | // merge members |
| | 19601 | 579 | | if (_members.TryGetValue(rootB, out var bMembers)) |
| | 19601 | 580 | | { |
| | 19601 | 581 | | if (rootA == sentinelRoot) |
| | 8926 | 582 | | { |
| | 8926 | 583 | | _members.Remove(rootB); |
| | 8926 | 584 | | } |
| | | 585 | | else |
| | 10675 | 586 | | { |
| | 10675 | 587 | | if (!_members.TryGetValue(rootA, out var aMembers)) |
| | 0 | 588 | | { |
| | 0 | 589 | | aMembers = new List<EdgeId>(); |
| | 0 | 590 | | _members[rootA] = aMembers; |
| | 0 | 591 | | } |
| | 10675 | 592 | | aMembers.AddRange(bMembers); |
| | 10675 | 593 | | _members.Remove(rootB); |
| | 10675 | 594 | | } |
| | 19601 | 595 | | } |
| | 19601 | 596 | | } |
| | | 597 | | |
| | | 598 | | public void CollapseToMainNetwork(EdgeId root) |
| | 6686 | 599 | | { |
| | 6686 | 600 | | _lock.EnterWriteLock(); |
| | | 601 | | try |
| | 6686 | 602 | | { |
| | 6686 | 603 | | root = this.FindNoLock(root); |
| | 8852 | 604 | | if (root == this.FindNoLock(MainNetworkSentinel)) return; |
| | 4520 | 605 | | this.MergeNoLock(MainNetworkSentinel, root); |
| | 4520 | 606 | | } |
| | 20058 | 607 | | finally { _lock.ExitWriteLock(); } |
| | 6686 | 608 | | } |
| | | 609 | | |
| | | 610 | | public void RemoveEdge(EdgeId edgeId) |
| | 0 | 611 | | { |
| | 0 | 612 | | _lock.EnterWriteLock(); |
| | | 613 | | try |
| | 0 | 614 | | { |
| | 0 | 615 | | var root = this.FindNoLock(edgeId); |
| | | 616 | | |
| | 0 | 617 | | if (_members.TryGetValue(root, out var members)) |
| | 0 | 618 | | { |
| | 0 | 619 | | members.Remove(edgeId); |
| | 0 | 620 | | if (members.Count == 0) |
| | 0 | 621 | | { |
| | 0 | 622 | | _members.Remove(root); |
| | | 623 | | |
| | | 624 | | // clean up adjacency |
| | 0 | 625 | | if (_outgoing.TryGetValue(root, out var targets)) |
| | 0 | 626 | | { |
| | 0 | 627 | | foreach (var t in targets) |
| | 0 | 628 | | { |
| | 0 | 629 | | if (_incoming.TryGetValue(this.FindNoLock(t), out var tInc)) |
| | 0 | 630 | | tInc.Remove(root); |
| | 0 | 631 | | } |
| | 0 | 632 | | _outgoing.Remove(root); |
| | 0 | 633 | | } |
| | | 634 | | |
| | 0 | 635 | | if (_incoming.TryGetValue(root, out var sources)) |
| | 0 | 636 | | { |
| | 0 | 637 | | foreach (var s in sources) |
| | 0 | 638 | | { |
| | 0 | 639 | | if (_outgoing.TryGetValue(this.FindNoLock(s), out var sOut)) |
| | 0 | 640 | | sOut.Remove(root); |
| | 0 | 641 | | } |
| | 0 | 642 | | _incoming.Remove(root); |
| | 0 | 643 | | } |
| | 0 | 644 | | } |
| | 0 | 645 | | } |
| | | 646 | | |
| | 0 | 647 | | _parent.Remove(edgeId); |
| | 0 | 648 | | _processed.TryRemove(edgeId, out _); |
| | 0 | 649 | | } |
| | 0 | 650 | | finally { _lock.ExitWriteLock(); } |
| | 0 | 651 | | } |
| | | 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() |
| | 0 | 667 | | { |
| | 0 | 668 | | _lock.EnterWriteLock(); |
| | | 669 | | try |
| | 0 | 670 | | { |
| | 0 | 671 | | _parent.Clear(); |
| | 0 | 672 | | _rank.Clear(); |
| | 0 | 673 | | _size.Clear(); |
| | 0 | 674 | | _members.Clear(); |
| | 0 | 675 | | _outgoing.Clear(); |
| | 0 | 676 | | _incoming.Clear(); |
| | 0 | 677 | | _processed.Clear(); |
| | | 678 | | |
| | 0 | 679 | | _parent[MainNetworkSentinel] = MainNetworkSentinel; |
| | 0 | 680 | | _rank[MainNetworkSentinel] = int.MaxValue; |
| | 0 | 681 | | _size[MainNetworkSentinel] = int.MaxValue; |
| | 0 | 682 | | } |
| | 0 | 683 | | finally { _lock.ExitWriteLock(); } |
| | 0 | 684 | | } |
| | | 685 | | |
| | | 686 | | public bool IsDeadEnd(EdgeId edgeId) |
| | 0 | 687 | | { |
| | 0 | 688 | | _lock.EnterReadLock(); |
| | | 689 | | try |
| | 0 | 690 | | { |
| | 0 | 691 | | var root = this.FindNoLock(edgeId); |
| | 0 | 692 | | if (root == this.FindNoLock(MainNetworkSentinel)) return false; |
| | | 693 | | |
| | 0 | 694 | | var hasOutgoing = _outgoing.TryGetValue(root, out var targets) && targets.Count > 0; |
| | 0 | 695 | | if (!hasOutgoing) return true; |
| | | 696 | | |
| | 0 | 697 | | var hasIncoming = _incoming.TryGetValue(root, out var sources) && sources.Count > 0; |
| | 0 | 698 | | return !hasIncoming; |
| | | 699 | | } |
| | 0 | 700 | | finally { _lock.ExitReadLock(); } |
| | 0 | 701 | | } |
| | | 702 | | |
| | | 703 | | /// <summary> |
| | | 704 | | /// Checks if this edge can reach the sentinel in BOTH directions. |
| | | 705 | | /// </summary> |
| | | 706 | | public bool CanReachMainNetwork(EdgeId edgeId) |
| | 0 | 707 | | { |
| | 0 | 708 | | _lock.EnterReadLock(); |
| | | 709 | | try |
| | 0 | 710 | | { |
| | 0 | 711 | | var root = this.FindNoLock(edgeId); |
| | 0 | 712 | | var sentinel = this.FindNoLock(MainNetworkSentinel); |
| | 0 | 713 | | if (root == sentinel) return true; |
| | | 714 | | |
| | 0 | 715 | | var visited = new HashSet<EdgeId>(); |
| | 0 | 716 | | var canForward = this.DfsCanReach(root, sentinel, visited, true); |
| | 0 | 717 | | if (!canForward) return false; |
| | | 718 | | |
| | 0 | 719 | | visited.Clear(); |
| | 0 | 720 | | return this.DfsCanReach(root, sentinel, visited, false); |
| | | 721 | | } |
| | 0 | 722 | | finally { _lock.ExitReadLock(); } |
| | 0 | 723 | | } |
| | | 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) |
| | 0 | 732 | | { |
| | 0 | 733 | | _lock.EnterReadLock(); |
| | | 734 | | try |
| | 0 | 735 | | { |
| | 0 | 736 | | var root = this.FindNoLock(edgeId); |
| | 0 | 737 | | var sentinel = this.FindNoLock(MainNetworkSentinel); |
| | 0 | 738 | | if (root == sentinel) return (true, true); |
| | | 739 | | |
| | 0 | 740 | | var visited = new HashSet<EdgeId>(); |
| | 0 | 741 | | var canForward = this.DfsCanReach(root, sentinel, visited, true); |
| | 0 | 742 | | visited.Clear(); |
| | 0 | 743 | | var canBackward = this.DfsCanReach(root, sentinel, visited, false); |
| | 0 | 744 | | return (canForward, canBackward); |
| | | 745 | | } |
| | 0 | 746 | | finally { _lock.ExitReadLock(); } |
| | 0 | 747 | | } |
| | | 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) |
| | 3265 | 755 | | { |
| | 3265 | 756 | | var result = new List<EdgeId>(); |
| | 3265 | 757 | | _lock.EnterReadLock(); |
| | | 758 | | try |
| | 3265 | 759 | | { |
| | 3265 | 760 | | if (!_parent.ContainsKey(edgeId)) return result; |
| | 3265 | 761 | | var root = this.FindNoLock(edgeId); |
| | 3265 | 762 | | if (_outgoing.TryGetValue(root, out var outs)) |
| | 1739 | 763 | | { |
| | 1739 | 764 | | var seen = new HashSet<EdgeId>(); |
| | 5579 | 765 | | foreach (var o in outs) |
| | 181 | 766 | | { |
| | 181 | 767 | | if (o == root) continue; |
| | 362 | 768 | | if (seen.Add(o)) result.Add(o); |
| | 181 | 769 | | } |
| | 1739 | 770 | | } |
| | 3265 | 771 | | } |
| | 9795 | 772 | | finally { _lock.ExitReadLock(); } |
| | 3265 | 773 | | return result; |
| | 3265 | 774 | | } |
| | | 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) |
| | 1672 | 782 | | { |
| | 1672 | 783 | | var result = new List<EdgeId>(); |
| | 1672 | 784 | | _lock.EnterReadLock(); |
| | | 785 | | try |
| | 1672 | 786 | | { |
| | 1672 | 787 | | if (!_parent.ContainsKey(edgeId)) return result; |
| | 1672 | 788 | | var root = this.FindNoLock(edgeId); |
| | 1672 | 789 | | if (_incoming.TryGetValue(root, out var ins)) |
| | 1635 | 790 | | { |
| | 1635 | 791 | | var seen = new HashSet<EdgeId>(); |
| | 12813 | 792 | | foreach (var i in ins) |
| | 3954 | 793 | | { |
| | 3954 | 794 | | var r = this.FindNoLock(i); |
| | 7716 | 795 | | if (r == root) continue; |
| | 384 | 796 | | if (seen.Add(r)) result.Add(r); |
| | 192 | 797 | | } |
| | 1635 | 798 | | } |
| | 1672 | 799 | | } |
| | 5016 | 800 | | finally { _lock.ExitReadLock(); } |
| | 1672 | 801 | | return result; |
| | 1672 | 802 | | } |
| | | 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) |
| | 0 | 812 | | { |
| | 0 | 813 | | var result = new List<EdgeId>(); |
| | 0 | 814 | | _lock.EnterReadLock(); |
| | | 815 | | try |
| | 0 | 816 | | { |
| | 0 | 817 | | if (!_parent.ContainsKey(edgeId)) return result; |
| | 0 | 818 | | var root = this.FindNoLock(edgeId); |
| | 0 | 819 | | var sentinel = this.FindNoLock(MainNetworkSentinel); |
| | 0 | 820 | | if (_outgoing.TryGetValue(root, out var outs)) |
| | 0 | 821 | | { |
| | 0 | 822 | | foreach (var o in outs) |
| | 0 | 823 | | { |
| | 0 | 824 | | if (o != sentinel) result.Add(o); |
| | 0 | 825 | | } |
| | 0 | 826 | | } |
| | 0 | 827 | | if (_incoming.TryGetValue(root, out var ins)) |
| | 0 | 828 | | { |
| | 0 | 829 | | foreach (var i in ins) |
| | 0 | 830 | | { |
| | 0 | 831 | | var r = this.FindNoLock(i); |
| | 0 | 832 | | if (r != sentinel && !result.Contains(r)) result.Add(r); |
| | 0 | 833 | | } |
| | 0 | 834 | | } |
| | 0 | 835 | | } |
| | 0 | 836 | | finally { _lock.ExitReadLock(); } |
| | 0 | 837 | | return result; |
| | 0 | 838 | | } |
| | | 839 | | |
| | | 840 | | private bool DfsCanReach(EdgeId current, EdgeId target, HashSet<EdgeId> visited, bool forward) |
| | 0 | 841 | | { |
| | 0 | 842 | | current = this.FindNoLock(current); |
| | 0 | 843 | | if (current == target) return true; |
| | 0 | 844 | | if (!visited.Add(current)) return false; |
| | | 845 | | |
| | 0 | 846 | | var adj = forward |
| | 0 | 847 | | ? (_outgoing.TryGetValue(current, out var o) ? o : null) |
| | 0 | 848 | | : (_incoming.TryGetValue(current, out var i) ? i : null); |
| | | 849 | | |
| | 0 | 850 | | if (adj == null) return false; |
| | | 851 | | |
| | 0 | 852 | | foreach (var next in adj) |
| | 0 | 853 | | { |
| | 0 | 854 | | if (this.DfsCanReach(this.FindNoLock(next), target, visited, forward)) return true; |
| | 0 | 855 | | } |
| | | 856 | | |
| | 0 | 857 | | return false; |
| | 0 | 858 | | } |
| | | 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) |
| | 0 | 866 | | { |
| | 0 | 867 | | _lock.EnterWriteLock(); |
| | | 868 | | try |
| | 0 | 869 | | { |
| | | 870 | | // build the set of roots to consider |
| | 0 | 871 | | var rootSet = new HashSet<EdgeId>(); |
| | 0 | 872 | | foreach (var c in candidateRoots) |
| | 0 | 873 | | { |
| | 0 | 874 | | var r = this.FindNoLock(c); |
| | 0 | 875 | | if (r != this.FindNoLock(MainNetworkSentinel)) |
| | 0 | 876 | | rootSet.Add(r); |
| | 0 | 877 | | } |
| | | 878 | | |
| | 0 | 879 | | if (rootSet.Count < 2) return false; |
| | | 880 | | |
| | | 881 | | // Tarjan's SCC |
| | 0 | 882 | | var index = 0; |
| | 0 | 883 | | var stack = new Stack<EdgeId>(); |
| | 0 | 884 | | var onStack = new HashSet<EdgeId>(); |
| | 0 | 885 | | var indices = new Dictionary<EdgeId, int>(); |
| | 0 | 886 | | var lowLinks = new Dictionary<EdgeId, int>(); |
| | 0 | 887 | | var sccs = new List<List<EdgeId>>(); |
| | | 888 | | |
| | 0 | 889 | | foreach (var v in rootSet) |
| | 0 | 890 | | { |
| | 0 | 891 | | if (!indices.ContainsKey(v)) |
| | 0 | 892 | | this.Strongconnect(v, rootSet, ref index, stack, onStack, indices, lowLinks, sccs); |
| | 0 | 893 | | } |
| | | 894 | | |
| | | 895 | | // merge SCCs with more than one vertex |
| | 0 | 896 | | var merged = false; |
| | 0 | 897 | | foreach (var scc in sccs) |
| | 0 | 898 | | { |
| | 0 | 899 | | if (scc.Count < 2) continue; |
| | 0 | 900 | | for (var i = 1; i < scc.Count; i++) |
| | 0 | 901 | | { |
| | 0 | 902 | | this.MergeNoLock(scc[0], scc[i]); |
| | 0 | 903 | | } |
| | 0 | 904 | | merged = true; |
| | 0 | 905 | | } |
| | | 906 | | |
| | 0 | 907 | | return merged; |
| | | 908 | | } |
| | 0 | 909 | | finally { _lock.ExitWriteLock(); } |
| | 0 | 910 | | } |
| | | 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) |
| | 0 | 916 | | { |
| | 0 | 917 | | indices[v] = index; |
| | 0 | 918 | | lowLinks[v] = index; |
| | 0 | 919 | | index++; |
| | 0 | 920 | | stack.Push(v); |
| | 0 | 921 | | onStack.Add(v); |
| | | 922 | | |
| | 0 | 923 | | if (_outgoing.TryGetValue(v, out var targets)) |
| | 0 | 924 | | { |
| | 0 | 925 | | foreach (var t in targets) |
| | 0 | 926 | | { |
| | 0 | 927 | | var w = this.FindNoLock(t); |
| | 0 | 928 | | if (!rootSet.Contains(w)) continue; // only consider candidates |
| | | 929 | | |
| | 0 | 930 | | if (!indices.ContainsKey(w)) |
| | 0 | 931 | | { |
| | 0 | 932 | | this.Strongconnect(w, rootSet, ref index, stack, onStack, indices, lowLinks, sccs); |
| | 0 | 933 | | lowLinks[v] = System.Math.Min(lowLinks[v], lowLinks[w]); |
| | 0 | 934 | | } |
| | 0 | 935 | | else if (onStack.Contains(w)) |
| | 0 | 936 | | { |
| | 0 | 937 | | lowLinks[v] = System.Math.Min(lowLinks[v], indices[w]); |
| | 0 | 938 | | } |
| | 0 | 939 | | } |
| | 0 | 940 | | } |
| | | 941 | | |
| | 0 | 942 | | if (lowLinks[v] == indices[v]) |
| | 0 | 943 | | { |
| | 0 | 944 | | var scc = new List<EdgeId>(); |
| | | 945 | | EdgeId w; |
| | | 946 | | do |
| | 0 | 947 | | { |
| | 0 | 948 | | w = stack.Pop(); |
| | 0 | 949 | | onStack.Remove(w); |
| | 0 | 950 | | scc.Add(w); |
| | 0 | 951 | | } while (w != v); |
| | | 952 | | |
| | 0 | 953 | | sccs.Add(scc); |
| | 0 | 954 | | } |
| | 0 | 955 | | } |
| | | 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) |
| | 406824 | 962 | | { |
| | 406824 | 963 | | _lock.EnterReadLock(); |
| | 813648 | 964 | | try { return this.FindNoLock(x); } |
| | 1220472 | 965 | | finally { _lock.ExitReadLock(); } |
| | 406824 | 966 | | } |
| | | 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) |
| | 1271788 | 977 | | { |
| | 1271788 | 978 | | if (!_parent.TryGetValue(x, out var parent)) return x; |
| | 1725275 | 979 | | while (parent != x) |
| | 453487 | 980 | | { |
| | 453487 | 981 | | x = parent; |
| | 453487 | 982 | | if (!_parent.TryGetValue(x, out parent)) return x; |
| | 453487 | 983 | | } |
| | 1271788 | 984 | | return x; |
| | 1271788 | 985 | | } |
| | | 986 | | } |