< 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:201
Uncovered lines:75
Coverable lines:276
Total lines:383
Line coverage:72.8% (201 of 276)
Covered branches:92
Total branches:138
Branch coverage:66.6% (92 of 138)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.cctor()100%1100%
.ctor()100%1100%
AddVertex(...)100%2100%
IsInGraph(...)100%1100%
IsProcessed(...)100%1100%
SetProcessed(...)100%1100%
IsNotIsland(...)100%2100%
GetSize(...)100%1100%
GetMembers(...)50%2100%
AddDirectedLink(...)100%8100%
HasDirectedLink(...)100%2100%
Merge(...)88.09%4283.75%
CollapseToMainNetwork(...)100%2100%
RemoveEdge(...)81.25%1687.09%
IsDeadEnd(...)75%8100%
CanReachMainNetwork(...)50%480%
DfsCanReach(...)56.25%16100%
DetectAndMergeCycles(...)31.25%1631.25%
Strongconnect(...)0%140%
Find(...)75%4100%

File(s)

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

#LineLine coverage
 1using System.Collections.Generic;
 2using Itinero.Network.Enumerators.Edges;
 3
 4namespace Itinero.Network.Search.Islands;
 5
 6/// <summary>
 7/// A directed meta-graph for island detection.
 8/// Each vertex represents one or more routing edges (merged via union-find).
 9/// Directed links represent travel direction between edge groups.
 10/// </summary>
 11internal class IslandDirectedGraph
 12{
 113    internal static readonly EdgeId MainNetworkSentinel = new(uint.MaxValue - 1, uint.MaxValue - 1);
 14
 915    private readonly Dictionary<EdgeId, EdgeId> _parent = new();
 916    private readonly Dictionary<EdgeId, int> _rank = new();
 917    private readonly Dictionary<EdgeId, int> _size = new();
 918    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _outgoing = new();
 919    private readonly Dictionary<EdgeId, HashSet<EdgeId>> _incoming = new();
 920    private readonly Dictionary<EdgeId, List<EdgeId>> _members = new();
 921    private readonly HashSet<EdgeId> _processed = new();
 22
 923    public IslandDirectedGraph()
 924    {
 925        _parent[MainNetworkSentinel] = MainNetworkSentinel;
 926        _rank[MainNetworkSentinel] = int.MaxValue;
 927        _size[MainNetworkSentinel] = int.MaxValue;
 928    }
 29
 30    public void AddVertex(EdgeId edgeId)
 553031    {
 1001832        if (_parent.ContainsKey(edgeId)) return;
 104233        _parent[edgeId] = edgeId;
 104234        _rank[edgeId] = 0;
 104235        _size[edgeId] = 1;
 104236        _members[edgeId] = new List<EdgeId> { edgeId };
 553037    }
 38
 25739    public bool IsInGraph(EdgeId edgeId) => _parent.ContainsKey(edgeId);
 84140    public bool IsProcessed(EdgeId edgeId) => _processed.Contains(edgeId);
 82641    public void SetProcessed(EdgeId edgeId) => _processed.Add(edgeId);
 42
 43    public bool IsNotIsland(EdgeId edgeId)
 1309744    {
 1414545        if (!_parent.ContainsKey(edgeId)) return false;
 1204946        return this.Find(edgeId) == this.Find(MainNetworkSentinel);
 1309747    }
 48
 102749    public int GetSize(EdgeId edgeId) => _size[this.Find(edgeId)];
 50
 51    public List<EdgeId>? GetMembers(EdgeId edgeId)
 1352    {
 1353        var root = this.Find(edgeId);
 1354        return _members.TryGetValue(root, out var m) ? m : null;
 1355    }
 56
 57    public void AddDirectedLink(EdgeId from, EdgeId to)
 940658    {
 940659        var fromRoot = this.Find(from);
 940660        var toRoot = this.Find(to);
 1675661        if (fromRoot == toRoot) return;
 62
 205663        if (!_outgoing.TryGetValue(fromRoot, out var targets))
 103864        {
 103865            targets = new HashSet<EdgeId>();
 103866            _outgoing[fromRoot] = targets;
 103867        }
 68
 205669        if (targets.Add(toRoot))
 205670        {
 71            // also update incoming index
 205672            if (!_incoming.TryGetValue(toRoot, out var sources))
 103873            {
 103874                sources = new HashSet<EdgeId>();
 103875                _incoming[toRoot] = sources;
 103876            }
 205677            sources.Add(fromRoot);
 205678        }
 940679    }
 80
 81    public bool HasDirectedLink(EdgeId from, EdgeId to)
 940682    {
 940683        var fromRoot = this.Find(from);
 940684        var toRoot = this.Find(to);
 940685        return _outgoing.TryGetValue(fromRoot, out var targets) && targets.Contains(toRoot);
 940686    }
 87
 88    public void Merge(EdgeId a, EdgeId b)
 103689    {
 103690        var rootA = this.Find(a);
 103691        var rootB = this.Find(b);
 103692        if (rootA == rootB) return;
 93
 94        // sentinel always wins
 103695        var sentinelRoot = this.Find(MainNetworkSentinel);
 103696        if (rootB == sentinelRoot)
 097            (rootA, rootB) = (rootB, rootA);
 103698        else if (rootA != sentinelRoot && _rank[rootA] < _rank[rootB])
 199            (rootA, rootB) = (rootB, rootA);
 100
 1036101        _parent[rootB] = rootA;
 1036102        if (rootA != sentinelRoot)
 1027103        {
 1027104            _size[rootA] += _size[rootB];
 1044105            if (_rank[rootA] == _rank[rootB]) _rank[rootA]++;
 1027106        }
 107
 108        // merge outgoing
 1036109        if (_outgoing.TryGetValue(rootB, out var bOut))
 1036110        {
 1036111            if (!_outgoing.TryGetValue(rootA, out var aOut))
 6112            {
 6113                aOut = new HashSet<EdgeId>();
 6114                _outgoing[rootA] = aOut;
 6115            }
 116
 7216117            foreach (var t in bOut)
 2054118            {
 2054119                var tRoot = this.Find(t);
 2054120                if (tRoot != rootA)
 1121                {
 1122                    aOut.Add(tRoot);
 123                    // update incoming: t's incoming should point to rootA not rootB
 1124                    if (_incoming.TryGetValue(tRoot, out var tInc))
 1125                    {
 1126                        tInc.Remove(rootB);
 1127                        tInc.Add(rootA);
 1128                    }
 1129                }
 2054130            }
 131
 1036132            _outgoing.Remove(rootB);
 1036133        }
 134
 135        // merge incoming
 1036136        if (_incoming.TryGetValue(rootB, out var bInc))
 1036137        {
 1036138            if (!_incoming.TryGetValue(rootA, out var aInc))
 6139            {
 6140                aInc = new HashSet<EdgeId>();
 6141                _incoming[rootA] = aInc;
 6142            }
 143
 7216144            foreach (var s in bInc)
 2054145            {
 2054146                var sRoot = this.Find(s);
 2054147                if (sRoot != rootA)
 0148                {
 0149                    aInc.Add(sRoot);
 150                    // update outgoing: s's outgoing should point to rootA not rootB
 0151                    if (_outgoing.TryGetValue(sRoot, out var sOut))
 0152                    {
 0153                        sOut.Remove(rootB);
 0154                        sOut.Add(rootA);
 0155                    }
 0156                }
 2054157            }
 158
 1036159            _incoming.Remove(rootB);
 1036160        }
 161
 162        // remove self-loops
 1036163        if (_outgoing.TryGetValue(rootA, out var aOutFinal))
 1036164            aOutFinal.Remove(rootA);
 1036165        if (_incoming.TryGetValue(rootA, out var aIncFinal))
 1036166            aIncFinal.Remove(rootA);
 167
 168        // merge members
 1036169        if (_members.TryGetValue(rootB, out var bMembers))
 1036170        {
 1036171            if (rootA == sentinelRoot)
 9172            {
 9173                _members.Remove(rootB);
 9174            }
 175            else
 1027176            {
 1027177                if (!_members.TryGetValue(rootA, out var aMembers))
 0178                {
 0179                    aMembers = new List<EdgeId>();
 0180                    _members[rootA] = aMembers;
 0181                }
 1027182                aMembers.AddRange(bMembers);
 1027183                _members.Remove(rootB);
 1027184            }
 1036185        }
 1036186    }
 187
 188    public void CollapseToMainNetwork(EdgeId root)
 9189    {
 9190        root = this.Find(root);
 9191        if (root == this.Find(MainNetworkSentinel)) return;
 9192        this.Merge(MainNetworkSentinel, root);
 9193    }
 194
 195    public void RemoveEdge(EdgeId edgeId)
 5196    {
 5197        var root = this.Find(edgeId);
 198
 5199        if (_members.TryGetValue(root, out var members))
 5200        {
 5201            members.Remove(edgeId);
 5202            if (members.Count == 0)
 5203            {
 5204                _members.Remove(root);
 205
 206                // clean up adjacency
 5207                if (_outgoing.TryGetValue(root, out var targets))
 1208                {
 3209                    foreach (var t in targets)
 0210                    {
 0211                        if (_incoming.TryGetValue(this.Find(t), out var tInc))
 0212                            tInc.Remove(root);
 0213                    }
 1214                    _outgoing.Remove(root);
 1215                }
 216
 5217                if (_incoming.TryGetValue(root, out var sources))
 1218                {
 5219                    foreach (var s in sources)
 1220                    {
 1221                        if (_outgoing.TryGetValue(this.Find(s), out var sOut))
 1222                            sOut.Remove(root);
 1223                    }
 1224                    _incoming.Remove(root);
 1225                }
 5226            }
 5227        }
 228
 5229        _parent.Remove(edgeId);
 5230        _processed.Remove(edgeId);
 5231    }
 232
 233    /// <summary>
 234    /// O(1) dead-end check using incoming index.
 235    /// </summary>
 236    public bool IsDeadEnd(EdgeId edgeId)
 115237    {
 115238        var root = this.Find(edgeId);
 115239        if (root == this.Find(MainNetworkSentinel)) return false;
 240
 115241        var hasOutgoing = _outgoing.TryGetValue(root, out var targets) && targets.Count > 0;
 120242        if (!hasOutgoing) return true;
 243
 110244        var hasIncoming = _incoming.TryGetValue(root, out var sources) && sources.Count > 0;
 110245        return !hasIncoming;
 115246    }
 247
 248    /// <summary>
 249    /// Checks if this edge can reach the sentinel in BOTH directions.
 250    /// </summary>
 251    public bool CanReachMainNetwork(EdgeId edgeId)
 110252    {
 110253        var root = this.Find(edgeId);
 110254        var sentinel = this.Find(MainNetworkSentinel);
 110255        if (root == sentinel) return true;
 256
 110257        var visited = new HashSet<EdgeId>();
 110258        var canForward = this.DfsCanReach(root, sentinel, visited, true);
 220259        if (!canForward) return false;
 260
 0261        visited.Clear();
 0262        return this.DfsCanReach(root, sentinel, visited, false);
 110263    }
 264
 265    private bool DfsCanReach(EdgeId current, EdgeId target, HashSet<EdgeId> visited, bool forward)
 9520266    {
 9520267        current = this.Find(current);
 9520268        if (current == target) return true;
 18930269        if (!visited.Add(current)) return false;
 270
 110271        var adj = forward
 110272            ? (_outgoing.TryGetValue(current, out var o) ? o : null)
 110273            : (_incoming.TryGetValue(current, out var i) ? i : null);
 274
 110275        if (adj == null) return false;
 276
 19150277        foreach (var next in adj)
 9410278        {
 9410279            if (this.DfsCanReach(this.Find(next), target, visited, forward)) return true;
 9410280        }
 281
 110282        return false;
 9520283    }
 284
 285    /// <summary>
 286    /// Detects cycles among the given candidate roots and merges them.
 287    /// Uses Tarjan's SCC algorithm on the subgraph of candidates.
 288    /// Returns true if any merges happened.
 289    /// </summary>
 290    public bool DetectAndMergeCycles(List<EdgeId> candidateRoots)
 6291    {
 292        // build the set of roots to consider
 6293        var rootSet = new HashSet<EdgeId>();
 238294        foreach (var c in candidateRoots)
 110295        {
 110296            var r = this.Find(c);
 110297            if (r != this.Find(MainNetworkSentinel))
 110298                rootSet.Add(r);
 110299        }
 300
 12301        if (rootSet.Count < 2) return false;
 302
 303        // Tarjan's SCC
 0304        var index = 0;
 0305        var stack = new Stack<EdgeId>();
 0306        var onStack = new HashSet<EdgeId>();
 0307        var indices = new Dictionary<EdgeId, int>();
 0308        var lowLinks = new Dictionary<EdgeId, int>();
 0309        var sccs = new List<List<EdgeId>>();
 310
 0311        foreach (var v in rootSet)
 0312        {
 0313            if (!indices.ContainsKey(v))
 0314                this.Strongconnect(v, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0315        }
 316
 317        // merge SCCs with more than one vertex
 0318        var merged = false;
 0319        foreach (var scc in sccs)
 0320        {
 0321            if (scc.Count < 2) continue;
 0322            for (var i = 1; i < scc.Count; i++)
 0323            {
 0324                this.Merge(scc[0], scc[i]);
 0325            }
 0326            merged = true;
 0327        }
 328
 0329        return merged;
 6330    }
 331
 332    private void Strongconnect(EdgeId v, HashSet<EdgeId> rootSet,
 333        ref int index, Stack<EdgeId> stack, HashSet<EdgeId> onStack,
 334        Dictionary<EdgeId, int> indices, Dictionary<EdgeId, int> lowLinks,
 335        List<List<EdgeId>> sccs)
 0336    {
 0337        indices[v] = index;
 0338        lowLinks[v] = index;
 0339        index++;
 0340        stack.Push(v);
 0341        onStack.Add(v);
 342
 0343        if (_outgoing.TryGetValue(v, out var targets))
 0344        {
 0345            foreach (var t in targets)
 0346            {
 0347                var w = this.Find(t);
 0348                if (!rootSet.Contains(w)) continue; // only consider candidates
 349
 0350                if (!indices.ContainsKey(w))
 0351                {
 0352                    this.Strongconnect(w, rootSet, ref index, stack, onStack, indices, lowLinks, sccs);
 0353                    lowLinks[v] = System.Math.Min(lowLinks[v], lowLinks[w]);
 0354                }
 0355                else if (onStack.Contains(w))
 0356                {
 0357                    lowLinks[v] = System.Math.Min(lowLinks[v], indices[w]);
 0358                }
 0359            }
 0360        }
 361
 0362        if (lowLinks[v] == indices[v])
 0363        {
 0364            var scc = new List<EdgeId>();
 365            EdgeId w;
 366            do
 0367            {
 0368                w = stack.Pop();
 0369                onStack.Remove(w);
 0370                scc.Add(w);
 0371            } while (w != v);
 372
 0373            sccs.Add(scc);
 0374        }
 0375    }
 376
 377    public EdgeId Find(EdgeId x)
 150330378    {
 150330379        if (!_parent.ContainsKey(x)) return x;
 210018380        if (_parent[x] != x) _parent[x] = this.Find(_parent[x]);
 150330381        return _parent[x];
 150330382    }
 383}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

.cctor()
.ctor()
AddVertex(...)
IsInGraph(...)
IsProcessed(...)
SetProcessed(...)
IsNotIsland(...)
GetSize(...)
GetMembers(...)
AddDirectedLink(...)
HasDirectedLink(...)
Merge(...)
CollapseToMainNetwork(...)
RemoveEdge(...)
IsDeadEnd(...)
CanReachMainNetwork(...)
DfsCanReach(...)
DetectAndMergeCycles(...)
Strongconnect(...)
Find(...)