< 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:156
Uncovered lines:55
Coverable lines:211
Total lines:356
Line coverage:73.9% (156 of 211)
Covered branches:87
Total branches:132
Branch coverage:65.9% (87 of 132)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
BuildForTileAsync()0%160%
IsOnIslandAsync()75%11686.18%

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            while (true)
 29136            {
 29137                if (cancellationToken.IsCancellationRequested) return null;
 138
 30139                if (destinationHeap.Count == 0) break;
 28140                var currentEdge = destinationHeap.Pop(out var hops);
 28141                if (!destinationVisits.Add(currentEdge)) continue;
 142
 28143                if (!edgeEnumerator.MoveTo(currentEdge.id, currentEdge.forward))
 0144                    throw new Exception("Enumeration attempted to an edge that does not exist");
 145#if DEBUG
 146                // TODO: if we queue the tail vertex then we can avoid this move.
 28147                var currentCanMove = costFunction.GetIslandBuilderCost(edgeEnumerator);
 28148                if (!currentCanMove)
 0149                    throw new Exception(
 0150                        "Queued edge always has to be traversable in the opposite queued direction in towards search");
 151#endif
 152
 153                // enumerate the neighbours at the tail and propagate labels if a
 154                // move is possible neighbour -> tail -> current.
 155                // TODO: queue previous edges too to be able to handle more complex restrictions.
 28156                var previousEdges =
 28157                    new (EdgeId edgeId, byte? turn)[] { (edgeEnumerator.EdgeId, edgeEnumerator.TailOrder) };
 158
 159                // notify usage of vertex before loading neighbours.
 28160                await network.UsageNotifier.NotifyVertex(network, edgeEnumerator.Tail, cancellationToken);
 28161                if (cancellationToken.IsCancellationRequested) return null;
 162
 163                // enumerate the neighbours and see if the label propagates.
 28164                if (!edgeEnumerator.MoveTo(edgeEnumerator.Tail)) throw new Exception("Vertex does not exist");
 67165                while (edgeEnumerator.MoveNext())
 44166                {
 72167                    if (edgeEnumerator.EdgeId == currentEdge.id) continue;
 168
 169                    // see the turn neighbour -> tail -> current is possible.
 170                    // this means we need to check the neighbour in it's current backward direction and current in forwa
 16171                    var canMove = costFunction.GetIslandBuilderCost(edgeEnumerator, false, previousEdges);
 18172                    if (!canMove) continue;
 173
 174                    // get label for the current edge, we get it here because it could have changed during neighbour pro
 14175                    if (!labels.TryGetWithDetails(currentEdge.id, out var currentLabelDetails))
 0176                        throw new Exception("Current should already have been assigned a label");
 177
 178                    // get neighbour label, if it exists already.
 14179                    var neighbourLabelDetails = labels.GetOrCreateLabel(edgeEnumerator, isOnIslandAlready);
 180
 181                    // a connection can be made, the path neighbour -> current is possible.
 14182                    var madeConnection = labels.ConnectTo(neighbourLabelDetails.label, currentLabelDetails.label);
 14183                    if (!madeConnection)
 13184                    {
 185                        // check if there is a bidirectional link.
 13186                        var canMoveOtherDirection =
 13187                            costFunction.GetIslandBuilderCost(edgeEnumerator, true, previousEdges);
 13188                        if (canMoveOtherDirection)
 9189                        {
 9190                            labels.ConnectTo(currentLabelDetails.label, neighbourLabelDetails.label);
 9191                            madeConnection = true;
 9192                        }
 13193                    }
 194
 14195                    if (madeConnection)
 10196                    {
 197                        // check root island again, it could have grown.
 10198                        if (labels.TryGetWithDetails(edgeId, out rootIsland))
 10199                        {
 10200                            if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 5201                            {
 5202                                if (rootIsland.label != IslandLabels.NotAnIslandLabel)
 0203                                    throw new Exception(
 0204                                        "A large island without the not-an-island label should not exist");
 5205                                return false;
 206                            }
 207
 5208                            if (rootIsland.final)
 0209                                return true; // the island can never ever get bigger anymore.
 5210                        }
 211
 212                        // if not, get the neighbour label again, it is now different.
 5213                        if (!labels.TryGetWithDetails(edgeEnumerator.EdgeId, out neighbourLabelDetails))
 0214                            throw new Exception("This should always exist at this point");
 5215                    }
 216
 9217                    if (neighbourLabelDetails.final)
 3218                    {
 3219                        originHasNonIsland = originHasNonIsland ||
 3220                                             neighbourLabelDetails.label == IslandLabels.NotAnIslandLabel;
 221
 222                        // if the neighbour already has a final label there are only two possibilities here:
 223                        // - this neighbour is an island, a connection with a non-island will never be made, no need to 
 224                        // - this neighbour is not an island, a connection with a non-island edge was made, no need to s
 3225                        continue;
 226                    }
 227
 228                    // add the neighbour to the queue, but in the opposite direction as currently enumerated.
 6229                    var neighbourHops = hops + 1;
 6230                    destinationHeap.Push((edgeEnumerator.EdgeId, !edgeEnumerator.Forward),
 6231                        neighbourHops);
 6232                }
 233
 23234                break;
 235            }
 236
 237            // do away.
 24238            while (true)
 24239            {
 24240                if (cancellationToken.IsCancellationRequested) return null;
 241
 24242                if (originHeap.Count == 0) break;
 24243                var currentEdge = originHeap.Pop(out var hops);
 24244                if (!originVisits.Add(currentEdge)) continue;
 245
 24246                if (!edgeEnumerator.MoveTo(currentEdge.id, currentEdge.forward))
 0247                    throw new Exception("Enumeration attempted to an edge that does not exist");
 248#if DEBUG
 249                // TODO: if we queue the tail vertex then we can avoid this move.
 24250                var currentCanMove = costFunction.GetIslandBuilderCost(edgeEnumerator);
 24251                if (!currentCanMove)
 0252                    throw new Exception(
 0253                        "Queued edge always has to be traversable in the opposite queued direction in towards search");
 254#endif
 255
 256                // enumerate the neighbours at the tail and propagate labels if a
 257                // move is possible current -> head -> neighbour.
 258                // TODO: queue previous edges too to be able to handle more complex restrictions.
 24259                var previousEdges =
 24260                    new (EdgeId edgeId, byte? turn)[] { (edgeEnumerator.EdgeId, edgeEnumerator.HeadOrder) };
 261
 262                // notify usage of vertex before loading neighbours.
 24263                await network.UsageNotifier.NotifyVertex(network, edgeEnumerator.Head, cancellationToken);
 24264                if (cancellationToken.IsCancellationRequested) return null;
 265
 266                // enumerate the neighbours and see if the label propagates.
 24267                if (!edgeEnumerator.MoveTo(edgeEnumerator.Head)) throw new Exception("Vertex does not exist");
 54268                while (edgeEnumerator.MoveNext())
 34269                {
 54270                    if (edgeEnumerator.EdgeId == currentEdge.id) continue;
 271
 272                    // see the turn current -> head -> neighbour is possible.
 14273                    var canMove = costFunction.GetIslandBuilderCost(edgeEnumerator, true, previousEdges);
 19274                    if (!canMove) continue;
 275
 276                    // get label for the current edge, we get it here because it could have changed during neighbour pro
 9277                    if (!labels.TryGetWithDetails(currentEdge.id, out var currentLabelDetails))
 0278                        throw new Exception("Current should already have been assigned a label");
 279
 280                    // get neighbour label, if it exists already.
 9281                    var neighbourLabelDetails = labels.GetOrCreateLabel(edgeEnumerator, isOnIslandAlready);
 282
 283                    // a connection can be made, the path current -> neighbour is possible.
 9284                    var madeConnection = labels.ConnectTo(currentLabelDetails.label, neighbourLabelDetails.label);
 9285                    if (!madeConnection)
 9286                    {
 287                        // check if there is a bidirectional link.
 9288                        var canMoveOtherDirection =
 9289                            costFunction.GetIslandBuilderCost(edgeEnumerator, false, previousEdges);
 9290                        if (canMoveOtherDirection)
 7291                        {
 7292                            labels.ConnectTo(neighbourLabelDetails.label, currentLabelDetails.label);
 7293                            madeConnection = true;
 7294                        }
 9295                    }
 296
 9297                    if (madeConnection)
 7298                    {
 299                        // check root island again, it could have grown.
 7300                        if (labels.TryGetWithDetails(edgeId, out rootIsland))
 7301                        {
 7302                            if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 4303                            {
 4304                                if (rootIsland.label != IslandLabels.NotAnIslandLabel)
 0305                                    throw new Exception(
 0306                                        "A large island without the not-an-island label should not exist");
 4307                                return false;
 308                            }
 309
 3310                            if (rootIsland.final)
 0311                                return true; // the island can never ever get bigger anymore.
 3312                        }
 313
 314                        // if not, get the neighbour label again, it is now different.
 3315                        if (!labels.TryGetWithDetails(edgeEnumerator.EdgeId, out neighbourLabelDetails))
 0316                            throw new Exception("This should always exist at this point");
 3317                    }
 318
 5319                    if (neighbourLabelDetails.final)
 0320                    {
 0321                        destinationHasNonIsland = destinationHasNonIsland ||
 0322                                                  neighbourLabelDetails.label == IslandLabels.NotAnIslandLabel;
 323
 324                        // if the neighbour already has a final label there are only two possibilities here:
 325                        // - this neighbour is an island, a connection with a non-island will never be made, no need to 
 326                        // - this neighbour is not an island, a connection with a non-island edge was made, no need to s
 0327                        continue;
 328                    }
 329
 330                    // add the neighbour to the queue.
 5331                    var neighbourHops = hops + 1;
 5332                    originHeap.Push((edgeEnumerator.EdgeId, edgeEnumerator.Forward),
 5333                        neighbourHops);
 5334                }
 335
 20336                break;
 337            }
 20338        }
 339
 8340        if (!labels.TryGetWithDetails(edgeId, out rootIsland)) throw new Exception("Root should have an island here");
 8341        if (rootIsland.size >= network.IslandManager.MaxIslandSize)
 0342            throw new Exception("This should have been tested before");
 8343        if (rootIsland.final) throw new Exception("This should have been tested before");
 344
 345        // island cannot get bigger anymore.
 346        // it has also not reached the min size.
 8347        labels.SetAsFinal(rootIsland.label);
 8348        return true;
 24349    }
 350
 351    // private static async Task WriteGeoJson(RoutingNetwork network, IslandLabels labels, EdgeId edge)
 352    // {
 353    //     await File.WriteAllTextAsync($"island_labels_{edge.LocalId}_{edge.TileId}_{(long)(DateTime.UtcNow - DateTime.
 354    //         await labels.ToGeoJson(network));
 355    // }
 356}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

BuildForTileAsync()
IsOnIslandAsync()