< 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:158
Uncovered lines:57
Coverable lines:215
Total lines:362
Line coverage:73.4% (158 of 215)
Covered branches:89
Total branches:136
Branch coverage:65.4% (89 of 136)
Tag:232_15462506344

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
BuildForTileAsync()0%160%
IsOnIslandAsync()74.16%12085.4%

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))
 1981        {
 82            // check if the neighbour has a status already we can use.
 1983            var onIslandAlready = isOnIslandAlready?.Invoke(edgeEnumerator);
 1984            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
 1796            {
 97                // create the root island.
 1798                rootIsland = labels.AddNew(edgeId);
 1799            }
 19100        }
 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
 37133        while (originHeap.Count > 0 || destinationHeap.Count > 0)
 29134        {
 29135            if (originVisits.Count >= (network.IslandManager.MaxIslandSize * 64) ||
 29136                destinationVisits.Count >= (network.IslandManager.MaxIslandSize * 64))
 0137            {
 0138                break;
 139            }
 140
 29141            while (true)
 29142            {
 29143                if (cancellationToken.IsCancellationRequested) return null;
 144
 30145                if (destinationHeap.Count == 0) break;
 28146                var currentEdge = destinationHeap.Pop(out var hops);
 28147                if (!destinationVisits.Add(currentEdge)) continue;
 148
 28149                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.
 28153                var currentCanMove = costFunction.GetIslandBuilderCost(edgeEnumerator);
 28154                if (!currentCanMove)
 0155                    throw new Exception(
 0156                        "Queued edge always has to be traversable in the opposite queued direction in towards search");
 157#endif
 158
 159                // enumerate the neighbours at the tail and propagate labels if a
 160                // move is possible neighbour -> tail -> current.
 161                // TODO: queue previous edges too to be able to handle more complex restrictions.
 28162                var previousEdges =
 28163                    new (EdgeId edgeId, byte? turn)[] { (edgeEnumerator.EdgeId, edgeEnumerator.TailOrder) };
 164
 165                // notify usage of vertex before loading neighbours.
 28166                await network.UsageNotifier.NotifyVertex(network, edgeEnumerator.Tail, cancellationToken);
 28167                if (cancellationToken.IsCancellationRequested) return null;
 168
 169                // enumerate the neighbours and see if the label propagates.
 28170                if (!edgeEnumerator.MoveTo(edgeEnumerator.Tail)) throw new Exception("Vertex does not exist");
 67171                while (edgeEnumerator.MoveNext())
 44172                {
 72173                    if (edgeEnumerator.EdgeId == currentEdge.id) continue;
 174
 175                    // see the turn neighbour -> tail -> current is possible.
 176                    // this means we need to check the neighbour in it's current backward direction and current in forwa
 16177                    var canMove = costFunction.GetIslandBuilderCost(edgeEnumerator, false, previousEdges);
 18178                    if (!canMove) continue;
 179
 180                    // get label for the current edge, we get it here because it could have changed during neighbour pro
 14181                    if (!labels.TryGetWithDetails(currentEdge.id, out var currentLabelDetails))
 0182                        throw new Exception("Current should already have been assigned a label");
 183
 184                    // get neighbour label, if it exists already.
 14185                    var neighbourLabelDetails = labels.GetOrCreateLabel(edgeEnumerator, isOnIslandAlready);
 186
 187                    // a connection can be made, the path neighbour -> current is possible.
 14188                    var madeConnection = labels.ConnectTo(neighbourLabelDetails.label, currentLabelDetails.label);
 14189                    if (!madeConnection)
 13190                    {
 191                        // check if there is a bidirectional link.
 13192                        var canMoveOtherDirection =
 13193                            costFunction.GetIslandBuilderCost(edgeEnumerator, true, previousEdges);
 13194                        if (canMoveOtherDirection)
 9195                        {
 9196                            labels.ConnectTo(currentLabelDetails.label, neighbourLabelDetails.label);
 9197                            madeConnection = true;
 9198                        }
 13199                    }
 200
 14201                    if (madeConnection)
 10202                    {
 203                        // check root island again, it could have grown.
 10204                        if (labels.TryGetWithDetails(edgeId, out rootIsland))
 10205                        {
 10206                            if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 5207                            {
 5208                                if (rootIsland.label != IslandLabels.NotAnIslandLabel)
 0209                                    throw new Exception(
 0210                                        "A large island without the not-an-island label should not exist");
 5211                                return false;
 212                            }
 213
 5214                            if (rootIsland.final)
 0215                                return true; // the island can never ever get bigger anymore.
 5216                        }
 217
 218                        // if not, get the neighbour label again, it is now different.
 5219                        if (!labels.TryGetWithDetails(edgeEnumerator.EdgeId, out neighbourLabelDetails))
 0220                            throw new Exception("This should always exist at this point");
 5221                    }
 222
 9223                    if (neighbourLabelDetails.final)
 3224                    {
 3225                        originHasNonIsland = originHasNonIsland ||
 3226                                             neighbourLabelDetails.label == IslandLabels.NotAnIslandLabel;
 227
 228                        // if the neighbour already has a final label there are only two possibilities here:
 229                        // - this neighbour is an island, a connection with a non-island will never be made, no need to 
 230                        // - this neighbour is not an island, a connection with a non-island edge was made, no need to s
 3231                        continue;
 232                    }
 233
 234                    // add the neighbour to the queue, but in the opposite direction as currently enumerated.
 6235                    var neighbourHops = hops + 1;
 6236                    destinationHeap.Push((edgeEnumerator.EdgeId, !edgeEnumerator.Forward),
 6237                        neighbourHops);
 6238                }
 239
 23240                break;
 241            }
 242
 243            // do away.
 24244            while (true)
 24245            {
 24246                if (cancellationToken.IsCancellationRequested) return null;
 247
 24248                if (originHeap.Count == 0) break;
 24249                var currentEdge = originHeap.Pop(out var hops);
 24250                if (!originVisits.Add(currentEdge)) continue;
 251
 24252                if (!edgeEnumerator.MoveTo(currentEdge.id, currentEdge.forward))
 0253                    throw new Exception("Enumeration attempted to an edge that does not exist");
 254#if DEBUG
 255                // TODO: if we queue the tail vertex then we can avoid this move.
 24256                var currentCanMove = costFunction.GetIslandBuilderCost(edgeEnumerator);
 24257                if (!currentCanMove)
 0258                    throw new Exception(
 0259                        "Queued edge always has to be traversable in the opposite queued direction in towards search");
 260#endif
 261
 262                // enumerate the neighbours at the tail and propagate labels if a
 263                // move is possible current -> head -> neighbour.
 264                // TODO: queue previous edges too to be able to handle more complex restrictions.
 24265                var previousEdges =
 24266                    new (EdgeId edgeId, byte? turn)[] { (edgeEnumerator.EdgeId, edgeEnumerator.HeadOrder) };
 267
 268                // notify usage of vertex before loading neighbours.
 24269                await network.UsageNotifier.NotifyVertex(network, edgeEnumerator.Head, cancellationToken);
 24270                if (cancellationToken.IsCancellationRequested) return null;
 271
 272                // enumerate the neighbours and see if the label propagates.
 24273                if (!edgeEnumerator.MoveTo(edgeEnumerator.Head)) throw new Exception("Vertex does not exist");
 54274                while (edgeEnumerator.MoveNext())
 34275                {
 54276                    if (edgeEnumerator.EdgeId == currentEdge.id) continue;
 277
 278                    // see the turn current -> head -> neighbour is possible.
 14279                    var canMove = costFunction.GetIslandBuilderCost(edgeEnumerator, true, previousEdges);
 19280                    if (!canMove) continue;
 281
 282                    // get label for the current edge, we get it here because it could have changed during neighbour pro
 9283                    if (!labels.TryGetWithDetails(currentEdge.id, out var currentLabelDetails))
 0284                        throw new Exception("Current should already have been assigned a label");
 285
 286                    // get neighbour label, if it exists already.
 9287                    var neighbourLabelDetails = labels.GetOrCreateLabel(edgeEnumerator, isOnIslandAlready);
 288
 289                    // a connection can be made, the path current -> neighbour is possible.
 9290                    var madeConnection = labels.ConnectTo(currentLabelDetails.label, neighbourLabelDetails.label);
 9291                    if (!madeConnection)
 9292                    {
 293                        // check if there is a bidirectional link.
 9294                        var canMoveOtherDirection =
 9295                            costFunction.GetIslandBuilderCost(edgeEnumerator, false, previousEdges);
 9296                        if (canMoveOtherDirection)
 7297                        {
 7298                            labels.ConnectTo(neighbourLabelDetails.label, currentLabelDetails.label);
 7299                            madeConnection = true;
 7300                        }
 9301                    }
 302
 9303                    if (madeConnection)
 7304                    {
 305                        // check root island again, it could have grown.
 7306                        if (labels.TryGetWithDetails(edgeId, out rootIsland))
 7307                        {
 7308                            if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 4309                            {
 4310                                if (rootIsland.label != IslandLabels.NotAnIslandLabel)
 0311                                    throw new Exception(
 0312                                        "A large island without the not-an-island label should not exist");
 4313                                return false;
 314                            }
 315
 3316                            if (rootIsland.final)
 0317                                return true; // the island can never ever get bigger anymore.
 3318                        }
 319
 320                        // if not, get the neighbour label again, it is now different.
 3321                        if (!labels.TryGetWithDetails(edgeEnumerator.EdgeId, out neighbourLabelDetails))
 0322                            throw new Exception("This should always exist at this point");
 3323                    }
 324
 5325                    if (neighbourLabelDetails.final)
 0326                    {
 0327                        destinationHasNonIsland = destinationHasNonIsland ||
 0328                                                  neighbourLabelDetails.label == IslandLabels.NotAnIslandLabel;
 329
 330                        // if the neighbour already has a final label there are only two possibilities here:
 331                        // - this neighbour is an island, a connection with a non-island will never be made, no need to 
 332                        // - this neighbour is not an island, a connection with a non-island edge was made, no need to s
 0333                        continue;
 334                    }
 335
 336                    // add the neighbour to the queue.
 5337                    var neighbourHops = hops + 1;
 5338                    originHeap.Push((edgeEnumerator.EdgeId, edgeEnumerator.Forward),
 5339                        neighbourHops);
 5340                }
 341
 20342                break;
 343            }
 20344        }
 345
 8346        if (!labels.TryGetWithDetails(edgeId, out rootIsland)) throw new Exception("Root should have an island here");
 8347        if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 0348            throw new Exception("This should have been tested before");
 8349        if (rootIsland.final) throw new Exception("This should have been tested before");
 350
 351        // island cannot get bigger anymore.
 352        // it has also not reached the min size.
 8353        labels.SetAsFinal(rootIsland.label);
 8354        return true;
 24355    }
 356
 357    // private static async Task WriteGeoJson(RoutingNetwork network, IslandLabels labels, EdgeId edge)
 358    // {
 359    //     await File.WriteAllTextAsync($"island_labels_{edge.LocalId}_{edge.TileId}_{(long)(DateTime.UtcNow - DateTime.
 360    //         await labels.ToGeoJson(network));
 361    // }
 362}
Generated by: ReportGenerator 4.8.2.0
06/05/2025 - 08:42:07
GitHub | www.palmmedia.de

Methods/Properties

BuildForTileAsync()
IsOnIslandAsync()