< 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:160
Uncovered lines:57
Coverable lines:217
Total lines:364
Line coverage:73.7% (160 of 217)
Covered branches:88
Total branches:136
Branch coverage:64.7% (88 of 136)
Tag:236_17851749384

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
BuildForTileAsync()0%160%
IsOnIslandAsync()73.33%12085.56%

File(s)

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

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Threading;
 4using System.Threading.Tasks;
 5using Itinero.Network.Enumerators.Edges;
 6using Itinero.Network.Tiles;
 7using Itinero.Profiles;
 8using Itinero.Routing.Costs;
 9using Itinero.Routing.DataStructures;
 10
 11namespace Itinero.Network.Search.Islands;
 12
 13internal class IslandBuilder
 14{
 15    public static async Task BuildForTileAsync(RoutingNetwork network, Profile profile, uint tileId, CancellationToken c
 016    {
 017        if (cancellationToken.IsCancellationRequested) return;
 018        var islands = network.IslandManager.GetIslandsFor(profile);
 19
 020        var tile = network.GetTileForRead(tileId);
 021        if (tile == null) return;
 22
 023        var enumerator = new NetworkTileEnumerator();
 024        enumerator.MoveTo(tile);
 25
 026        var labels = new IslandLabels(network.IslandManager.MaxIslandSize);
 027        var costFunction = network.GetCostFunctionFor(profile);
 028        var vertex = new VertexId(tileId, 0);
 029        while (enumerator.MoveTo(vertex))
 030        {
 031            while (enumerator.MoveNext())
 032            {
 033                if (cancellationToken.IsCancellationRequested) return;
 34
 035                var onIsland = await IsOnIslandAsync(network, labels, costFunction, enumerator.EdgeId,
 036                    IsOnIslandAlready, cancellationToken);
 037                if (onIsland == null) continue; // edge cannot be traversed by profile.
 038                if (!onIsland.Value) continue; // edge is not on island.
 39
 040                islands.SetEdgeOnIsland(enumerator.EdgeId);
 041            }
 42
 043            vertex = new VertexId(tileId, vertex.LocalId + 1);
 044        }
 45
 046        if (cancellationToken.IsCancellationRequested) return;
 047        islands.SetTileDone(tileId);
 048        return;
 49
 50        bool? IsOnIslandAlready(IEdgeEnumerator e)
 051        {
 052            return islands.IsEdgeOnIsland(e, tileId);
 053        }
 054    }
 55
 56    internal static async Task<bool?> IsOnIslandAsync(RoutingNetwork network, IslandLabels labels,
 57        ICostFunction costFunction, EdgeId edgeId,
 58        Func<IEdgeEnumerator, bool?>? isOnIslandAlready = null, CancellationToken cancellationToken = default)
 2459    {
 60        // to check if an edge is on an island we do the following:
 61        // - verify it can be used as an origin by searching forward and finding a big connected island.
 62        // - verify it can be used as a destination by searching backward and finding a big connected island.
 63
 64        // the following assumptions are used:
 65        // - two bidirectional edges that share a vertex are always on the same island.
 66        // - an island bigger than a given threshold is considered connected.
 67        // - onedirectional edges are always their own islands until they occur in a loop.
 68
 2469        var edgeEnumerator = network.GetEdgeEnumerator();
 2470        edgeEnumerator.MoveTo(edgeId, true);
 2471        var costEnumerator = network.GetEdgeEnumerator();
 2472        var canForward = costFunction.GetIslandBuilderCost(edgeEnumerator);
 2473        costEnumerator.MoveTo(edgeId, false);
 2474        var canBackward = costFunction.GetIslandBuilderCost(costEnumerator);
 75
 76        // test if the edge can be traversed, if not return undefined value.
 2477        if (!canForward && !canBackward) return null;
 78
 79        // see if the edge already has a label.
 2480        if (!labels.TryGetWithDetails(edgeId, out var rootIsland))
 1781        {
 82            // check if the neighbour has a status already we can use.
 1783            var onIslandAlready = isOnIslandAlready?.Invoke(edgeEnumerator);
 1784            if (onIslandAlready != null)
 285            {
 286                if (onIslandAlready.Value)
 087                {
 088                    rootIsland = labels.AddNew(edgeId, false);
 089                }
 90                else
 291                {
 292                    rootIsland = labels.AddTo(IslandLabels.NotAnIslandLabel, edgeId);
 293                }
 294            }
 95            else
 1596            {
 97                // create the root island.
 1598                rootIsland = labels.AddNew(edgeId);
 1599            }
 17100        }
 101
 24102        if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 7103        {
 7104            if (rootIsland.label != IslandLabels.NotAnIslandLabel)
 0105                throw new Exception("A large island without the not-an-island label should not exist");
 7106            return false;
 107        }
 108
 17109        if (rootIsland.final) return true; // the island can never ever get bigger anymore.
 110
 111        // a search in two parts:
 112        // - a search space of routes going towards the edge, the destination heap.
 113        // - a search space of routes going away from the edge, the origin heap.
 114        // when either of the searches stops before the island is final the edge is on an island.
 115
 17116        var originHeap = new BinaryHeap<(EdgeId id, bool forward)>();
 17117        var originVisits = new HashSet<(EdgeId id, bool forward)>();
 17118        var originHasNonIsland = false;
 17119        var destinationHeap = new BinaryHeap<(EdgeId id, bool forward)>();
 17120        var destinationVisits = new HashSet<(EdgeId id, bool forward)>();
 17121        var destinationHasNonIsland = false;
 17122        if (canForward)
 17123        {
 17124            originHeap.Push((edgeId, true), 1);
 17125            destinationHeap.Push((edgeId, true), 1);
 17126        }
 17127        if (canBackward)
 11128        {
 11129            originHeap.Push((edgeId, false), 1);
 11130            destinationHeap.Push((edgeId, false), 1);
 11131        }
 132
 44133        while (originHeap.Count > 0 || destinationHeap.Count > 0)
 33134        {
 33135            if (originVisits.Count >= (network.IslandManager.MaxIslandSize * 64) ||
 33136                destinationVisits.Count >= (network.IslandManager.MaxIslandSize * 64))
 0137            {
 0138                break;
 139            }
 140
 33141            while (true)
 33142            {
 33143                if (cancellationToken.IsCancellationRequested) return null;
 144
 37145                if (destinationHeap.Count == 0) break;
 29146                var currentEdge = destinationHeap.Pop(out var hops);
 29147                if (!destinationVisits.Add(currentEdge)) continue;
 148
 29149                if (!edgeEnumerator.MoveTo(currentEdge.id, currentEdge.forward))
 0150                    throw new Exception("Enumeration attempted to an edge that does not exist");
 151#if DEBUG
 152                // TODO: if we queue the tail vertex then we can avoid this move.
 29153                var currentCanMove = costFunction.GetIslandBuilderCost(edgeEnumerator);
 29154                if (!currentCanMove)
 0155                    throw new Exception(
 0156                        "Queued edge always has to be traversable in the opposite queued direction in towards search");
 157#endif
 29158                var currentCanMoveBackwards = costFunction.GetIslandBuilderCost(edgeEnumerator, false);
 159
 160                // enumerate the neighbours at the tail and propagate labels if a
 161                // move is possible neighbour -> tail -> current.
 162                // TODO: queue previous edges too to be able to handle more complex restrictions.
 29163                var previousEdges =
 29164                    new (EdgeId edgeId, byte? turn)[] { (edgeEnumerator.EdgeId, edgeEnumerator.TailOrder) };
 165
 166                // notify usage of vertex before loading neighbours.
 29167                await network.UsageNotifier.NotifyVertex(network, edgeEnumerator.Tail, cancellationToken);
 29168                if (cancellationToken.IsCancellationRequested) return null;
 169
 170                // enumerate the neighbours and see if the label propagates.
 29171                if (!edgeEnumerator.MoveTo(edgeEnumerator.Tail)) throw new Exception("Vertex does not exist");
 72172                while (edgeEnumerator.MoveNext())
 46173                {
 75174                    if (edgeEnumerator.EdgeId == currentEdge.id) continue;
 175
 176                    // see the turn neighbour -> tail -> current is possible.
 177                    // this means we need to check the neighbour in it's current backward direction and current in forwa
 17178                    var canMove = costFunction.GetIslandBuilderCost(edgeEnumerator, false, previousEdges);
 19179                    if (!canMove) continue;
 180
 181                    // get label for the current edge, we get it here because it could have changed during neighbour pro
 15182                    if (!labels.TryGetWithDetails(currentEdge.id, out var currentLabelDetails))
 0183                        throw new Exception("Current should already have been assigned a label");
 184
 185                    // get neighbour label, if it exists already.
 15186                    var neighbourLabelDetails = labels.GetOrCreateLabel(edgeEnumerator, isOnIslandAlready);
 187
 188                    // a connection can be made, the path neighbour -> current is possible.
 15189                    var madeConnection = labels.ConnectTo(neighbourLabelDetails.label, currentLabelDetails.label);
 15190                    if (!madeConnection && currentCanMoveBackwards)
 8191                    {
 192                        // check if there is a bidirectional link.
 8193                        var canMoveOtherDirection =
 8194                            costFunction.GetIslandBuilderCost(edgeEnumerator, true, previousEdges);
 8195                        if (canMoveOtherDirection)
 5196                        {
 5197                            labels.ConnectTo(currentLabelDetails.label, neighbourLabelDetails.label);
 5198                            madeConnection = true;
 5199                        }
 8200                    }
 201
 15202                    if (madeConnection)
 7203                    {
 204                        // check root island again, it could have grown.
 7205                        if (labels.TryGetWithDetails(edgeId, out rootIsland))
 7206                        {
 7207                            if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 3208                            {
 3209                                if (rootIsland.label != IslandLabels.NotAnIslandLabel)
 0210                                    throw new Exception(
 0211                                        "A large island without the not-an-island label should not exist");
 3212                                return false;
 213                            }
 214
 4215                            if (rootIsland.final)
 0216                                return true; // the island can never ever get bigger anymore.
 4217                        }
 218
 219                        // if not, get the neighbour label again, it is now different.
 4220                        if (!labels.TryGetWithDetails(edgeEnumerator.EdgeId, out neighbourLabelDetails))
 0221                            throw new Exception("This should always exist at this point");
 4222                    }
 223
 12224                    if (neighbourLabelDetails.final)
 6225                    {
 6226                        originHasNonIsland = originHasNonIsland ||
 6227                                             neighbourLabelDetails.label == IslandLabels.NotAnIslandLabel;
 228
 229                        // if the neighbour already has a final label there are only two possibilities here:
 230                        // - this neighbour is an island, a connection with a non-island will never be made, no need to 
 231                        // - this neighbour is not an island, a connection with a non-island edge was made, no need to s
 6232                        continue;
 233                    }
 234
 235                    // add the neighbour to the queue, but in the opposite direction as currently enumerated.
 6236                    var neighbourHops = hops + 1;
 6237                    destinationHeap.Push((edgeEnumerator.EdgeId, !edgeEnumerator.Forward),
 6238                        neighbourHops);
 6239                }
 240
 26241                break;
 242            }
 243
 244            // do away.
 30245            while (true)
 30246            {
 30247                if (cancellationToken.IsCancellationRequested) return null;
 248
 30249                if (originHeap.Count == 0) break;
 30250                var currentEdge = originHeap.Pop(out var hops);
 30251                if (!originVisits.Add(currentEdge)) continue;
 252
 30253                if (!edgeEnumerator.MoveTo(currentEdge.id, currentEdge.forward))
 0254                    throw new Exception("Enumeration attempted to an edge that does not exist");
 255#if DEBUG
 256                // TODO: if we queue the tail vertex then we can avoid this move.
 30257                var currentCanMove = costFunction.GetIslandBuilderCost(edgeEnumerator);
 30258                if (!currentCanMove)
 0259                    throw new Exception(
 0260                        "Queued edge always has to be traversable in the opposite queued direction in towards search");
 261#endif
 30262                var currentCanMoveBackwards = costFunction.GetIslandBuilderCost(edgeEnumerator, false);
 263
 264                // enumerate the neighbours at the tail and propagate labels if a
 265                // move is possible current -> head -> neighbour.
 266                // TODO: queue previous edges too to be able to handle more complex restrictions.
 30267                var previousEdges =
 30268                    new (EdgeId edgeId, byte? turn)[] { (edgeEnumerator.EdgeId, edgeEnumerator.HeadOrder) };
 269
 270                // notify usage of vertex before loading neighbours.
 30271                await network.UsageNotifier.NotifyVertex(network, edgeEnumerator.Head, cancellationToken);
 30272                if (cancellationToken.IsCancellationRequested) return null;
 273
 274                // enumerate the neighbours and see if the label propagates.
 30275                if (!edgeEnumerator.MoveTo(edgeEnumerator.Head)) throw new Exception("Vertex does not exist");
 73276                while (edgeEnumerator.MoveNext())
 46277                {
 73278                    if (edgeEnumerator.EdgeId == currentEdge.id) continue;
 279
 280                    // see the turn current -> head -> neighbour is possible.
 19281                    var canMove = costFunction.GetIslandBuilderCost(edgeEnumerator, true, previousEdges);
 26282                    if (!canMove) continue;
 283
 284                    // get label for the current edge, we get it here because it could have changed during neighbour pro
 12285                    if (!labels.TryGetWithDetails(currentEdge.id, out var currentLabelDetails))
 0286                        throw new Exception("Current should already have been assigned a label");
 287
 288                    // get neighbour label, if it exists already.
 12289                    var neighbourLabelDetails = labels.GetOrCreateLabel(edgeEnumerator, isOnIslandAlready);
 290
 291                    // a connection can be made, the path current -> neighbour is possible.
 12292                    var madeConnection = labels.ConnectTo(currentLabelDetails.label, neighbourLabelDetails.label);
 12293                    if (!madeConnection && currentCanMoveBackwards)
 6294                    {
 295                        // check if there is a bidirectional link.
 6296                        var canMoveOtherDirection =
 6297                            costFunction.GetIslandBuilderCost(edgeEnumerator, false, previousEdges);
 6298                        if (canMoveOtherDirection)
 6299                        {
 6300                            labels.ConnectTo(neighbourLabelDetails.label, currentLabelDetails.label);
 6301                            madeConnection = true;
 6302                        }
 6303                    }
 304
 12305                    if (madeConnection)
 6306                    {
 307                        // check root island again, it could have grown.
 6308                        if (labels.TryGetWithDetails(edgeId, out rootIsland))
 6309                        {
 6310                            if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 3311                            {
 3312                                if (rootIsland.label != IslandLabels.NotAnIslandLabel)
 0313                                    throw new Exception(
 0314                                        "A large island without the not-an-island label should not exist");
 3315                                return false;
 316                            }
 317
 3318                            if (rootIsland.final)
 0319                                return true; // the island can never ever get bigger anymore.
 3320                        }
 321
 322                        // if not, get the neighbour label again, it is now different.
 3323                        if (!labels.TryGetWithDetails(edgeEnumerator.EdgeId, out neighbourLabelDetails))
 0324                            throw new Exception("This should always exist at this point");
 3325                    }
 326
 9327                    if (neighbourLabelDetails.final)
 0328                    {
 0329                        destinationHasNonIsland = destinationHasNonIsland ||
 0330                                                  neighbourLabelDetails.label == IslandLabels.NotAnIslandLabel;
 331
 332                        // if the neighbour already has a final label there are only two possibilities here:
 333                        // - this neighbour is an island, a connection with a non-island will never be made, no need to 
 334                        // - this neighbour is not an island, a connection with a non-island edge was made, no need to s
 0335                        continue;
 336                    }
 337
 338                    // add the neighbour to the queue.
 9339                    var neighbourHops = hops + 1;
 9340                    originHeap.Push((edgeEnumerator.EdgeId, edgeEnumerator.Forward),
 9341                        neighbourHops);
 9342                }
 343
 27344                break;
 345            }
 27346        }
 347
 11348        if (!labels.TryGetWithDetails(edgeId, out rootIsland)) throw new Exception("Root should have an island here");
 11349        if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 0350            throw new Exception("This should have been tested before");
 11351        if (rootIsland.final) throw new Exception("This should have been tested before");
 352
 353        // island cannot get bigger anymore.
 354        // it has also not reached the min size.
 11355        labels.SetAsFinal(rootIsland.label);
 11356        return true;
 24357    }
 358
 359    // private static async Task WriteGeoJson(RoutingNetwork network, IslandLabels labels, EdgeId edge)
 360    // {
 361    //     await File.WriteAllTextAsync($"island_labels_{edge.LocalId}_{edge.TileId}_{(long)(DateTime.UtcNow - DateTime.
 362    //         await labels.ToGeoJson(network));
 363    // }
 364}
Generated by: ReportGenerator 4.8.2.0
09/19/2025 - 07:34:11
GitHub | www.palmmedia.de

Methods/Properties

BuildForTileAsync()
IsOnIslandAsync()