< Summary

Class:Itinero.Network.Search.Islands.IslandBuilder
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/IslandBuilder.cs
Covered lines:225
Uncovered lines:32
Coverable lines:257
Total lines:397
Line coverage:87.5% (225 of 257)
Covered branches:143
Total branches:178
Branch coverage:80.3% (143 of 178)
Tag:260_25658844794

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
ResolveEdgeAsync()73.8%42100%
BuildForTileAsync()88.46%26100%
ProcessEdge(...)90.74%5487.5%
TryResolve(...)61.76%3463.49%
CollectComponentCandidates(...)80%10100%
EnqueueNeighborTiles(...)91.66%12100%

File(s)

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

#LineLine coverage
 1using System.Collections.Generic;
 2using System.Threading;
 3using System.Threading.Tasks;
 4using Itinero.Network.Enumerators.Edges;
 5using Itinero.Network.Tiles;
 6using Itinero.Profiles;
 7using Itinero.Routing.Costs;
 8
 9namespace Itinero.Network.Search.Islands;
 10
 11internal class IslandBuilder
 12{
 13    /// <summary>
 14    /// Resolves whether an edge is on an island. Keeps expanding until definitive.
 15    /// </summary>
 16    public static async Task<bool?> ResolveEdgeAsync(RoutingNetwork network, Profile profile, EdgeId edgeId,
 17        CancellationToken cancellationToken)
 3118    {
 3119        if (cancellationToken.IsCancellationRequested) return null;
 20
 3121        var islands = network.IslandManager.GetIslandsFor(profile);
 3122        var dg = network.IslandManager.GetOrCreateDirectedGraph(profile);
 23
 24        // quick checks.
 4225        if (islands.IsEdgeOnIsland(edgeId)) return true;
 3426        if (dg.IsNotIsland(edgeId)) return false;
 27
 628        var costFunction = network.GetCostFunctionFor(profile);
 629        var edgeEnumerator = network.GetEdgeEnumerator();
 630        var maxIslandSize = network.IslandManager.MaxIslandSize;
 31
 32        // process the edge.
 633        ProcessEdge(dg, costFunction, edgeEnumerator, edgeId, islands, maxIslandSize);
 634        if (!dg.IsInGraph(edgeId)) return null; // not traversable
 35
 36        // expand outward from the edge's component until resolved.
 637        var processedTiles = new HashSet<uint>();
 638        var tilesToProcess = new Queue<uint>();
 39
 40        // seed with tiles of vertices of the edge.
 641        if (edgeEnumerator.MoveTo(edgeId, true))
 642        {
 643            tilesToProcess.Enqueue(edgeEnumerator.Tail.TileId);
 644            tilesToProcess.Enqueue(edgeEnumerator.Head.TileId);
 645        }
 46
 1247        while (tilesToProcess.Count > 0)
 1048        {
 1049            if (cancellationToken.IsCancellationRequested) return null;
 50
 51            // check resolution.
 1052            if (islands.IsEdgeOnIsland(edgeId)) return true;
 1053            if (dg.IsNotIsland(edgeId)) return false;
 54
 1055            var tileId = tilesToProcess.Dequeue();
 1356            if (!processedTiles.Add(tileId)) continue;
 57
 58            // load tile.
 759            await network.UsageNotifier.NotifyVertex(network, new VertexId(tileId, 0), cancellationToken);
 760            if (cancellationToken.IsCancellationRequested) return null;
 61
 762            var tile = network.GetTileForRead(tileId);
 763            if (tile == null) continue;
 64
 65            // process all edges in the tile.
 766            var tileEnumerator = new NetworkTileEnumerator();
 767            tileEnumerator.MoveTo(tile);
 768            var vertex = new VertexId(tileId, 0);
 42569            while (tileEnumerator.MoveTo(vertex))
 42270            {
 202171                while (tileEnumerator.MoveNext())
 160372                {
 238973                    if (!tileEnumerator.Forward) continue;
 81774                    ProcessEdge(dg, costFunction, edgeEnumerator, tileEnumerator.EdgeId, islands, maxIslandSize);
 75
 76                    // early exit if resolved.
 82177                    if (dg.IsNotIsland(edgeId)) return false;
 81378                }
 41879                vertex = new VertexId(tileId, vertex.LocalId + 1);
 41880            }
 381            if (dg.IsNotIsland(edgeId)) return false;
 82
 83            // try resolve with cycle detection.
 384            var candidates = CollectComponentCandidates(dg, edgeId, islands);
 385            TryResolve(dg, islands, candidates, maxIslandSize);
 86
 387            if (islands.IsEdgeOnIsland(edgeId)) return true;
 388            if (dg.IsNotIsland(edgeId)) return false;
 89
 90            // enqueue tiles of unresolved neighbors.
 391            EnqueueNeighborTiles(dg, edgeId, edgeEnumerator, processedTiles, tilesToProcess);
 392        }
 93
 94        // final resolution attempt.
 295        var finalCandidates = CollectComponentCandidates(dg, edgeId, islands);
 296        TryResolve(dg, islands, finalCandidates, maxIslandSize);
 97
 298        if (islands.IsEdgeOnIsland(edgeId)) return true;
 299        if (dg.IsNotIsland(edgeId)) return false;
 100
 101        // no more tiles to expand and still unresolved.
 102        // if the component can't reach the sentinel, it's isolated → island.
 2103        return true;
 31104    }
 105
 106    /// <summary>
 107    /// Processes all edges in a tile into the DG.
 108    /// </summary>
 109    public static async Task BuildForTileAsync(RoutingNetwork network, Profile profile, uint tileId,
 110        CancellationToken cancellationToken)
 11111    {
 11112        if (cancellationToken.IsCancellationRequested) return;
 11113        var islands = network.IslandManager.GetIslandsFor(profile);
 114
 11115        var tile = network.GetTileForRead(tileId);
 11116        if (tile == null) return;
 117
 11118        var dg = network.IslandManager.GetOrCreateDirectedGraph(profile);
 11119        var costFunction = network.GetCostFunctionFor(profile);
 11120        var edgeEnumerator = network.GetEdgeEnumerator();
 11121        var maxIslandSize = network.IslandManager.MaxIslandSize;
 122
 11123        var tileEnumerator = new NetworkTileEnumerator();
 11124        tileEnumerator.MoveTo(tile);
 11125        var vertex = new VertexId(tileId, 0);
 49126        while (tileEnumerator.MoveTo(vertex))
 38127        {
 92128            while (tileEnumerator.MoveNext())
 54129            {
 54130                if (cancellationToken.IsCancellationRequested) return;
 81131                if (!tileEnumerator.Forward) continue;
 27132                ProcessEdge(dg, costFunction, edgeEnumerator, tileEnumerator.EdgeId, islands, maxIslandSize);
 27133            }
 38134            vertex = new VertexId(tileId, vertex.LocalId + 1);
 38135        }
 136
 137        // collect tile edges as candidates.
 11138        var candidates = new List<EdgeId>();
 11139        tileEnumerator.MoveTo(tile);
 11140        vertex = new VertexId(tileId, 0);
 49141        while (tileEnumerator.MoveTo(vertex))
 38142        {
 92143            while (tileEnumerator.MoveNext())
 54144            {
 81145                if (!tileEnumerator.Forward) continue;
 27146                var eid = tileEnumerator.EdgeId;
 27147                if (dg.IsInGraph(eid) && !dg.IsNotIsland(eid) && !islands.IsEdgeOnIsland(eid))
 14148                    candidates.Add(eid);
 27149            }
 38150            vertex = new VertexId(tileId, vertex.LocalId + 1);
 38151        }
 152
 11153        TryResolve(dg, islands, candidates, maxIslandSize);
 154
 11155        if (candidates.Count == 0)
 10156            islands.SetTileDone(tileId);
 11157    }
 158
 159    /// <summary>
 160    /// Processes a single edge into the DG.
 161    /// </summary>
 162    internal static void ProcessEdge(IslandDirectedGraph dg,
 163        ICostFunction costFunction, RoutingNetworkEdgeEnumerator edgeEnumerator,
 164        EdgeId edgeId, Islands islands, int maxIslandSize)
 850165    {
 860166        if (dg.IsProcessed(edgeId)) return;
 846167        if (dg.IsNotIsland(edgeId)) return;
 834168        if (islands.IsEdgeOnIsland(edgeId)) return;
 169
 834170        if (!edgeEnumerator.MoveTo(edgeId, true)) return;
 834171        var canForward = costFunction.GetIslandBuilderCost(edgeEnumerator);
 834172        if (!edgeEnumerator.MoveTo(edgeId, false)) return;
 834173        var canBackward = costFunction.GetIslandBuilderCost(edgeEnumerator);
 174
 834175        if (!canForward && !canBackward) return;
 176
 834177        dg.AddVertex(edgeId);
 178
 4968179        for (var pass = 0; pass < 2; pass++)
 1660180        {
 1660181            var forward = pass == 0;
 1660182            if (forward && !canForward) continue;
 1666183            if (!forward && !canBackward) continue;
 184
 1654185            edgeEnumerator.MoveTo(edgeId, forward);
 1654186            var targetVertex = edgeEnumerator.Head;
 187
 188            // Pre-position helper enumerators on edgeId in both traversal directions so
 189            // we can hand them to the two-enumerator GetIslandBuilderCost primitive:
 190            //   edgeIdFrom: head = targetVertex (for canGoTo, where edgeId is the "from")
 191            //   edgeIdTo:   tail = targetVertex (for canComeFrom, where edgeId is the "to")
 1654192            var edgeIdFrom = edgeEnumerator.Network.GetEdgeEnumerator();
 1654193            edgeIdFrom.MoveTo(edgeId, forward);
 1654194            var edgeIdTo = edgeEnumerator.Network.GetEdgeEnumerator();
 1654195            edgeIdTo.MoveTo(edgeId, !forward);
 196
 197            // Reusable probe positioned on the current neighbor in its
 198            // "arriving at targetVertex" direction (head = targetVertex), used as the
 199            // "from" side of canComeFrom.
 1654200            var neighborArriving = edgeEnumerator.Network.GetEdgeEnumerator();
 201
 1654202            if (!edgeEnumerator.MoveTo(targetVertex)) continue;
 203
 8006204            while (edgeEnumerator.MoveNext())
 6362205            {
 8011206                if (edgeEnumerator.EdgeId == edgeId) continue;
 207
 4713208                var neighborId = edgeEnumerator.EdgeId;
 209
 210                // skip known islands.
 4713211                if (islands.IsEdgeOnIsland(neighborId)) continue;
 212
 213                // determine DG vertex for the neighbor.
 214                EdgeId neighborDgVertex;
 4713215                if (dg.IsNotIsland(neighborId))
 0216                {
 0217                    neighborDgVertex = IslandDirectedGraph.MainNetworkSentinel;
 0218                }
 219                else
 4713220                {
 4713221                    dg.AddVertex(neighborId);
 4713222                    neighborDgVertex = neighborId;
 4713223                }
 224
 225                // canGoTo (edgeId → neighbor at the shared vertex):
 226                //   from = edgeIdFrom (head = targetVertex)
 227                //   to   = edgeEnumerator on the neighbor (tail = targetVertex by iteration)
 4713228                var canGoTo = costFunction.GetIslandBuilderCost(edgeIdFrom, edgeEnumerator);
 4713229                if (canGoTo)
 4708230                {
 4708231                    dg.AddDirectedLink(edgeId, neighborDgVertex);
 232                    // bidirectional merge check: O(1).
 4708233                    if (dg.HasDirectedLink(neighborDgVertex, edgeId))
 0234                    {
 0235                        dg.Merge(edgeId, neighborDgVertex);
 0236                        var newSize = dg.GetSize(dg.Find(edgeId));
 0237                        if (newSize >= maxIslandSize)
 0238                            dg.CollapseToMainNetwork(edgeId);
 0239                    }
 4708240                }
 241
 242                // canComeFrom (neighbor → edgeId at the shared vertex):
 243                //   from = neighbor in its "arriving at targetVertex" direction
 244                //          (head = targetVertex, i.e. the opposite of iteration direction)
 245                //   to   = edgeIdTo (tail = targetVertex)
 4713246                neighborArriving.MoveTo(neighborId, !edgeEnumerator.Forward);
 4713247                var canComeFrom = costFunction.GetIslandBuilderCost(neighborArriving, edgeIdTo);
 4713248                if (canComeFrom)
 4704249                {
 4704250                    dg.AddDirectedLink(neighborDgVertex, edgeId);
 251                    // bidirectional merge check: O(1).
 4704252                    if (dg.HasDirectedLink(edgeId, neighborDgVertex))
 1028253                    {
 1028254                        dg.Merge(edgeId, neighborDgVertex);
 1028255                        var newSize = dg.GetSize(dg.Find(edgeId));
 1028256                        if (newSize >= maxIslandSize)
 10257                            dg.CollapseToMainNetwork(edgeId);
 1028258                    }
 4704259                }
 260
 4723261                if (dg.IsNotIsland(edgeId)) break;
 262
 263                // re-enumerate to continue.
 4703264                edgeEnumerator.MoveTo(targetVertex);
 11554265                while (edgeEnumerator.MoveNext())
 11554266                {
 16257267                    if (edgeEnumerator.EdgeId == neighborId) break;
 6851268                }
 4703269            }
 270
 1664271            if (dg.IsNotIsland(edgeId)) break;
 1644272        }
 273
 834274        dg.SetProcessed(edgeId);
 850275    }
 276
 277    /// <summary>
 278    /// Resolves candidates: dead-end pruning, cycle detection, reachability.
 279    /// </summary>
 280    private static void TryResolve(IslandDirectedGraph dg, Islands islands,
 281        List<EdgeId> candidates, int maxIslandSize)
 16282    {
 283        bool changed;
 284        do
 24285        {
 24286            changed = false;
 287
 288            // 1. Prune dead-ends.
 292289            for (var i = candidates.Count - 1; i >= 0; i--)
 122290            {
 122291                var edgeId = candidates[i];
 122292                if (!dg.IsInGraph(edgeId) || dg.IsNotIsland(edgeId))
 0293                {
 0294                    candidates.RemoveAt(i);
 0295                    continue;
 296                }
 297
 122298                if (dg.IsDeadEnd(edgeId))
 11299                {
 11300                    var members = dg.GetMembers(dg.Find(edgeId));
 11301                    if (members != null)
 11302                    {
 11303                        var copy = new List<EdgeId>(members);
 55304                        foreach (var m in copy)
 11305                        {
 11306                            islands.SetEdgeOnIsland(m);
 11307                            dg.RemoveEdge(m);
 11308                        }
 11309                    }
 11310                    candidates.RemoveAt(i);
 11311                    changed = true;
 11312                }
 122313            }
 314
 315            // 2. Detect one-way cycles among remaining candidates (Tarjan's SCC).
 24316            if (candidates.Count >= 2)
 6317            {
 6318                if (dg.DetectAndMergeCycles(candidates))
 0319                {
 0320                    changed = true;
 321                    // check if any merged component now exceeds MaxIslandSize.
 0322                    for (var i = candidates.Count - 1; i >= 0; i--)
 0323                    {
 0324                        var edgeId = candidates[i];
 0325                        if (!dg.IsInGraph(edgeId) || dg.IsNotIsland(edgeId))
 0326                        {
 0327                            candidates.RemoveAt(i);
 0328                            continue;
 329                        }
 330
 0331                        var root = dg.Find(edgeId);
 0332                        if (dg.GetSize(root) >= maxIslandSize)
 0333                        {
 0334                            dg.CollapseToMainNetwork(root);
 0335                            candidates.RemoveAt(i);
 0336                        }
 0337                    }
 0338                }
 6339            }
 340
 341            // 3. Check if any remaining candidate can reach the sentinel both ways.
 270342            for (var i = candidates.Count - 1; i >= 0; i--)
 111343            {
 111344                var edgeId = candidates[i];
 111345                if (!dg.IsInGraph(edgeId) || dg.IsNotIsland(edgeId))
 0346                {
 0347                    candidates.RemoveAt(i);
 0348                    continue;
 349                }
 350
 111351                if (dg.CanReachMainNetwork(edgeId))
 1352                {
 1353                    dg.CollapseToMainNetwork(edgeId);
 1354                    candidates.RemoveAt(i);
 1355                    changed = true;
 1356                }
 111357            }
 48358        } while (changed);
 16359    }
 360
 361    private static List<EdgeId> CollectComponentCandidates(IslandDirectedGraph dg, EdgeId edgeId, Islands islands)
 5362    {
 5363        var candidates = new List<EdgeId>();
 5364        if (!dg.IsInGraph(edgeId)) return candidates;
 365
 5366        var members = dg.GetMembers(dg.Find(edgeId));
 5367        if (members != null)
 5368        {
 231369            foreach (var m in members)
 108370            {
 108371                if (!dg.IsNotIsland(m) && !islands.IsEdgeOnIsland(m))
 108372                    candidates.Add(m);
 108373            }
 5374        }
 375
 5376        return candidates;
 5377    }
 378
 379    private static void EnqueueNeighborTiles(IslandDirectedGraph dg, EdgeId edgeId,
 380        RoutingNetworkEdgeEnumerator edgeEnumerator,
 381        HashSet<uint> processedTiles, Queue<uint> tilesToProcess)
 3382    {
 3383        if (!dg.IsInGraph(edgeId)) return;
 384
 3385        var members = dg.GetMembers(dg.Find(edgeId));
 3386        if (members == null) return;
 387
 217388        foreach (var member in members)
 104389        {
 104390            if (!edgeEnumerator.MoveTo(member, true)) continue;
 104391            var t = edgeEnumerator.Tail.TileId;
 104392            var h = edgeEnumerator.Head.TileId;
 119393            if (!processedTiles.Contains(t)) tilesToProcess.Enqueue(t);
 104394            if (!processedTiles.Contains(h)) tilesToProcess.Enqueue(h);
 104395        }
 3396    }
 397}
Generated by: ReportGenerator 4.8.2.0
05/11/2026 - 08:25:56
GitHub | www.palmmedia.de

Methods/Properties

ResolveEdgeAsync()
BuildForTileAsync()
ProcessEdge(...)
TryResolve(...)
CollectComponentCandidates(...)
EnqueueNeighborTiles(...)