< Summary

Class:Itinero.Routing.ReachabilityRouter
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/ReachabilityRouter.cs
Covered lines:169
Uncovered lines:32
Coverable lines:201
Total lines:419
Line coverage:84% (169 of 201)
Covered branches:60
Total branches:78
Branch coverage:76.9% (60 of 78)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
PathAsync()100%2100%
ResolveAsync()78.84%5279.84%
<ResolveAsync()100%1100%
<ResolveAsync()50%655.55%
NewHalf(...)100%1100%
Stranded(...)100%2100%
BoxFor(...)100%1100%
NextSnapAsync()100%6100%
Routable(...)50%877.77%
SettledEdges(...)100%2100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/ReachabilityRouter.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Threading;
 4using System.Threading.Tasks;
 5using Itinero.Geo;
 6using Itinero.Network;
 7using Itinero.Network.Enumerators.Edges;
 8using Itinero.Network.Search.Edges;
 9using Itinero.Network.Search.Reachability;
 10using Itinero.Network.Tiles;
 11using Itinero.Routes.Paths;
 12using Itinero.Routing.Costs;
 13using Itinero.Routing.Flavours.Dijkstra;
 14using Itinero.Routing.Flavours.Dijkstra.Bidirectional;
 15using Itinero.Snapping;
 16
 17namespace Itinero.Routing;
 18
 19/// <summary>
 20/// Routes between two locations, doing the snapping and the routing as one operation.
 21/// </summary>
 22/// <remarks>
 23/// Each candidate is tried by expanding a <see cref="SearchHalf"/> from it, and that same half is
 24/// what the search continues with, so the connectivity check costs nothing the route would not.
 25/// </remarks>
 26/// <remarks>
 27/// One-to-one only: a half is consumed by the search that adopts it, so sharing an origin across
 28/// destinations would mean copying it.
 29/// </remarks>
 30public static class ReachabilityRouter
 31{
 32
 33    /// <summary>
 34    /// Calculates a path between two locations.
 35    /// </summary>
 36    /// <param name="network">The network.</param>
 37    /// <param name="settings">Routing settings; carries the profile.</param>
 38    /// <param name="origin">Where the route starts, as longitude/latitude.</param>
 39    /// <param name="destination">Where it ends.</param>
 40    /// <param name="bounds">How much network counts as connected, and the work ceiling.</param>
 41    /// <param name="searchBoxMeters">Half-size of the box searched for candidate edges.</param>
 42    /// <param name="cancellationToken">Cancellation.</param>
 43    /// <returns>The path, and the two snap points it was built between.</returns>
 44    public static async Task<Result<ReachabilityRoute>> PathAsync(
 45        this RoutingNetwork network,
 46        RoutingSettings settings,
 47        (double longitude, double latitude) origin,
 48        (double longitude, double latitude) destination,
 49        ReachabilityBounds bounds,
 50        double searchBoxMeters,
 51        CancellationToken cancellationToken = default)
 552    {
 553        var resolved = await network.ResolveAsync(settings, origin, destination, bounds,
 554            searchBoxMeters, pruneFactor: 1.0, onForwardRelaxed: null, onBackwardRelaxed: null,
 555            cancellationToken);
 656        if (resolved.IsError) return new Result<ReachabilityRoute>(resolved.ErrorMessage);
 57
 458        var r = resolved.Value;
 459        return new ReachabilityRoute(r.Path, r.Source, r.Target);
 560    }
 61
 62    /// <summary>
 63    /// Resolves, and keeps relaxing past the best meeting so a caller can map the region around
 64    /// the route out of the same search. Collected here because a pruned transition's tail is
 65    /// settled and never expanded again, so the band holding the alternatives cannot be re-found.
 66    /// </summary>
 67    /// <param name="pruneFactor">How far past the best meeting to go. 1.0 is an ordinary route.</param>
 68    internal static async Task<Result<ResolvedRoute>> ResolveAsync(
 69        this RoutingNetwork network,
 70        RoutingSettings settings,
 71        (double longitude, double latitude) origin,
 72        (double longitude, double latitude) destination,
 73        ReachabilityBounds bounds,
 74        double searchBoxMeters,
 75        double pruneFactor,
 76        RelaxedCallback? onForwardRelaxed,
 77        RelaxedCallback? onBackwardRelaxed,
 78        CancellationToken cancellationToken = default)
 2879    {
 2880        var profile = settings.Profile;
 2881        var costFunction = network.GetCostFunctionFor(profile);
 2882        if (settings.CostFunctionWrapper != null) costFunction = settings.CostFunctionWrapper(costFunction);
 83
 2884        var accessChecker = (IEdgeChecker)network.Snap([profile], s =>
 2885        {
 2886            s.CheckIslands = false;
 2887            s.CheckCanStopOn = false;
 2888            s.OffsetInMeter = searchBoxMeters;
 2889            s.OffsetInMeterMax = searchBoxMeters;
 2890            s.MaxDistance = double.MaxValue;
 5691        });
 92
 2893        await network.UsageNotifier.NotifyBox(network, BoxFor(origin, searchBoxMeters), cancellationToken);
 2894        await network.UsageNotifier.NotifyBox(network, BoxFor(destination, searchBoxMeters), cancellationToken);
 95
 2896        await using var originCandidates = network.NearestCandidatesAsync(
 2897            BoxFor(origin, searchBoxMeters), accessChecker, searchBoxMeters, cancellationToken)
 2898            .GetAsyncEnumerator(cancellationToken);
 2899        await using var destinationCandidates = network.NearestCandidatesAsync(
 28100            BoxFor(destination, searchBoxMeters), accessChecker, searchBoxMeters, cancellationToken)
 28101            .GetAsyncEnumerator(cancellationToken);
 102
 103        // Edges no longer worth snapping to, per direction, from the settled set of a half that
 104        // ran out of network: that set is closed, so every edge in it leads exactly as far.
 28105        var deadForOrigin = new HashSet<EdgeId>();
 28106        var deadForDestination = new HashSet<EdgeId>();
 107
 28108        var sourceSnap = await NextSnapAsync(network, costFunction, originCandidates, deadForOrigin);
 28109        if (sourceSnap == null)
 0110        {
 0111            return new Result<ResolvedRoute>(FormattableString.Invariant(
 0112                $"Could not snap origin to connected network: {origin.longitude},{origin.latitude}"));
 113        }
 114
 28115        var targetSnap = await NextSnapAsync(network, costFunction, destinationCandidates, deadForDestination);
 28116        if (targetSnap == null)
 0117        {
 0118            return new Result<ResolvedRoute>(FormattableString.Invariant(
 0119                $"Could not snap destination to connected network: {destination.longitude},{destination.latitude}"));
 120        }
 121
 28122        SearchHalf? forwardHalf = null;
 28123        SearchHalf? backwardHalf = null;
 124
 125        // A stranded candidate gets a second attempt with its pocket relabelled before we give up
 126        // on it and move further away. One attempt per candidate; null means no pocket yet.
 28127        ICostFunction? forwardCostFn = null;
 28128        ICostFunction? backwardCostFn = null;
 28129        var forwardPocketTried = false;
 28130        var backwardPocketTried = false;
 28131        var pocketBound = network.IslandManager.MaxIslandSize;
 132
 28133        var maxBox = settings.MaxBoxFor(network, [sourceSnap.Value, targetSnap.Value]);
 134
 135        // Goal direction, the same balanced potential the island-detection router uses. It depends
 136        // on both snap locations, so a candidate advance invalidates it and it is rebuilt below.
 28137        var potential = IRouterOneToOneExtensions.BuildBalancedPotential(
 28138            network, profile, sourceSnap.Value, targetSnap.Value);
 139
 28140        ReachabilityCounters.CountRoute();
 28141        var settledBefore = 0L;
 28142        var routeSettled = 0L;
 28143        var retried = false;
 144
 145        try
 28146        {
 32147            while (true)
 32148            {
 32149                cancellationToken.ThrowIfCancellationRequested();
 150
 151                // A half whose endpoint did not move is kept, settled set and frontier intact, and
 152                // carries on from where it stopped. Only the end that failed starts over.
 32153                forwardHalf ??= NewHalf(network, forwardCostFn ?? costFunction, sourceSnap.Value, true);
 32154                backwardHalf ??= NewHalf(network, backwardCostFn ?? costFunction, targetSnap.Value, false);
 155
 32156                var (path, pathCost) = await RouteAsync(forwardHalf, backwardHalf,
 32157                    sourceSnap.Value, targetSnap.Value, potential);
 158
 159                // Settled counts are cumulative per half and a surviving half keeps growing across
 160                // retries, so charge the increment rather than the total.
 32161                var settledNow = (long)forwardHalf.Settled.Count + backwardHalf.Settled.Count;
 32162                var settledDelta = settledNow >= settledBefore ? settledNow - settledBefore : settledNow;
 32163                ReachabilityCounters.CountSettled(settledDelta);
 32164                routeSettled += settledDelta;
 32165                settledBefore = settledNow;
 166
 32167                if (path != null)
 27168                {
 27169                    return new ResolvedRoute(path, pathCost, sourceSnap.Value, targetSnap.Value,
 27170                        forwardCostFn ?? costFunction, backwardCostFn ?? costFunction, routeSettled);
 171                }
 172
 5173                var originStranded = Stranded(forwardHalf, bounds.Threshold);
 5174                var destinationStranded = Stranded(backwardHalf, bounds.Threshold);
 175
 176                // Both halves got past the threshold and still did not meet: there is plenty of
 177                // network at both ends and it does not join up. Trying other edges nearby cannot
 178                // change that.
 5179                if (!originStranded && !destinationStranded)
 0180                {
 0181                    return new Result<ResolvedRoute>("Path not found");
 182                }
 183
 5184                if (originStranded && !forwardPocketTried)
 2185                {
 2186                    forwardPocketTried = true;
 2187                    ReachabilityCounters.CountPocketComposed();
 2188                    var pocket = LocalPocket.Compose(network, costFunction,
 2189                        SettledEdges(forwardHalf), asOrigin: true,
 2190                        componentAllowance: pocketBound, budget: pocketBound);
 191
 2192                    if (!pocket.Abandoned)
 2193                    {
 194                        // Same candidate, second attempt: the pocket's untagged members now read as
 195                        // local-access, so the half can cross them to reach its way out.
 2196                        forwardCostFn = new PocketCostFunction(costFunction, pocket.Members);
 2197                        forwardHalf = null;
 2198                        retried = true;
 2199                        continue;
 200                    }
 201
 0202                    ReachabilityCounters.CountPocketAbandoned();
 0203                }
 204
 3205                if (originStranded)
 2206                {
 15207                    foreach (var edge in SettledEdges(forwardHalf)) deadForOrigin.Add(edge);
 2208                    sourceSnap = await NextSnapAsync(network, costFunction, originCandidates, deadForOrigin);
 2209                    if (sourceSnap == null)
 1210                    {
 1211                        return new Result<ResolvedRoute>(FormattableString.Invariant(
 1212                            $"Could not snap origin to connected network: {origin.longitude},{origin.latitude}"));
 213                    }
 214
 1215                    ReachabilityCounters.CountOriginAdvance();
 1216                    ReachabilityCounters.CountWasted(forwardHalf.Settled.Count);
 1217                    retried = true;
 1218                    forwardHalf = null;
 1219                    forwardCostFn = null;
 1220                    forwardPocketTried = false;
 1221                }
 222
 2223                if (destinationStranded && !backwardPocketTried)
 1224                {
 1225                    backwardPocketTried = true;
 1226                    ReachabilityCounters.CountPocketComposed();
 1227                    var pocket = LocalPocket.Compose(network, costFunction,
 1228                        SettledEdges(backwardHalf), asOrigin: false,
 1229                        componentAllowance: pocketBound, budget: pocketBound);
 230
 1231                    if (!pocket.Abandoned)
 1232                    {
 1233                        backwardCostFn = new PocketCostFunction(costFunction, pocket.Members);
 1234                        backwardHalf = null;
 1235                        retried = true;
 1236                        continue;
 237                    }
 238
 0239                    ReachabilityCounters.CountPocketAbandoned();
 0240                }
 241
 1242                if (destinationStranded)
 0243                {
 0244                    foreach (var edge in SettledEdges(backwardHalf)) deadForDestination.Add(edge);
 0245                    targetSnap = await NextSnapAsync(network, costFunction, destinationCandidates, deadForDestination);
 0246                    if (targetSnap == null)
 0247                    {
 0248                        return new Result<ResolvedRoute>(FormattableString.Invariant(
 0249                            $"Could not snap destination to connected network: {destination.longitude},{destination.lati
 250                    }
 251
 0252                    ReachabilityCounters.CountDestinationAdvance();
 0253                    ReachabilityCounters.CountWasted(backwardHalf.Settled.Count);
 0254                    retried = true;
 0255                    backwardHalf = null;
 0256                    backwardCostFn = null;
 0257                    backwardPocketTried = false;
 0258                }
 259
 1260                maxBox = settings.MaxBoxFor(network, [sourceSnap.Value, targetSnap.Value]);
 261
 262                // An endpoint moved, so the goal direction did too. The surviving half's frontier
 263                // is keyed on the old one; the search re-keys it from stored costs on the next
 264                // call, which is why rebuilding here rather than adjusting in place is safe.
 1265                potential = IRouterOneToOneExtensions.BuildBalancedPotential(
 1266                    network, profile, sourceSnap.Value, targetSnap.Value);
 1267            }
 268        }
 269        finally
 28270        {
 271            // Every exit from the loop lands here, including the failures — a route that ran
 272            // out of candidates is exactly the kind the retry accounting must not omit.
 28273            ReachabilityCounters.CountRouteOutcome(retried, routeSettled);
 28274        }
 275
 276        async Task<(Path? path, double cost)> RouteAsync(SearchHalf fwd, SearchHalf bwd,
 277            SnapPoint from, SnapPoint to, HeuristicFunc? goalDirection)
 32278        {
 32279            ReachabilityCounters.CountSearch();
 32280            var search = SearchPool<BidirectionalDijkstra>.Rent();
 281            try
 32282            {
 32283                return await search.ContinueAsync(network, fwd, bwd, from, to, costFunction,
 32284                    SettleAsync, cancellationToken, isMainN: null, potential: goalDirection,
 32285                    localAccessRule: true,
 32286                    forwardCostFunction: forwardCostFn, backwardCostFunction: backwardCostFn,
 32287                    pruneFactor: pruneFactor,
 32288                    onForwardRelaxed: onForwardRelaxed, onBackwardRelaxed: onBackwardRelaxed);
 289            }
 290            finally
 32291            {
 32292                SearchPool<BidirectionalDijkstra>.Return(search);
 32293            }
 32294        }
 295
 296        async Task<bool> SettleAsync(VertexId v)
 565297        {
 565298            if (!network.UsageNotifier.IsVertexDataReady(network, v))
 0299            {
 0300                await network.UsageNotifier.NotifyVertex(network, v, cancellationToken);
 0301            }
 302
 565303            if (cancellationToken.IsCancellationRequested) return false;
 1130304            if (maxBox == null) return false;
 305
 0306            return !maxBox.Value.Overlaps(network.GetVertex(v));
 565307        }
 28308    }
 309
 310    /// A half seeded at a snap point.
 311    private static SearchHalf NewHalf(RoutingNetwork network, ICostFunction costFunction,
 312        SnapPoint snap, bool isForwardHalf)
 60313    {
 60314        var half = new SearchHalf(isForwardHalf);
 60315        half.PushTerminal(network.GetEdgeEnumerator(), snap, costFunction, potential: null);
 60316        return half;
 60317    }
 318
 319    /// <summary>
 320    /// Whether this half ran out of network rather than being stopped by anything else.
 321    /// </summary>
 322    /// <remarks>
 323    /// An empty heap below the threshold means everything reachable has been seen and there is
 324    /// not enough of it — the same verdict the candidate evaluation would reach.
 325    /// </remarks>
 326    private static bool Stranded(SearchHalf half, int threshold) =>
 10327        half.Heap.Count == 0 && half.Settled.Count < threshold;
 328
 329    /// The box searched for candidate edges around a location.
 330    private static ((double longitude, double, float? e) topLeft,
 331        (double longitude, double latitude, float? e) bottomRight) BoxFor(
 332        (double longitude, double latitude) location, double searchBoxMeters)
 112333    {
 112334        (double longitude, double latitude, float? e) at = (location.longitude, location.latitude, null);
 112335        return at.BoxAround(searchBoxMeters);
 112336    }
 337
 338    /// <summary>
 339    /// The next candidate that is not already known to be hopeless.
 340    /// </summary>
 341    /// <remarks>
 342    /// Skips everything the failed search settled: that set is closed and under threshold, so one
 343    /// failed search dismisses the whole dead end rather than one edge of it.
 344    /// </remarks>
 345    private static async Task<SnapPoint?> NextSnapAsync(
 346        RoutingNetwork network,
 347        ICostFunction costFunction,
 348        IAsyncEnumerator<SnapPoint> candidates,
 349        HashSet<EdgeId> dead)
 58350    {
 58351        var enumerator = network.GetEdgeEnumerator();
 59352        while (await candidates.MoveNextAsync())
 58353        {
 58354            var candidate = candidates.Current;
 59355            if (dead.Contains(candidate.EdgeId)) continue;
 356
 357            // Only "can the profile use this edge at all". Whether it leads anywhere is settled by
 358            // the search itself, and only paid for when it turns out not to.
 57359            if (!Routable(enumerator, costFunction, candidate.EdgeId)) continue;
 360
 57361            return candidate;
 362        }
 363
 1364        return null;
 58365    }
 366
 367    /// Whether the (masked) cost function can traverse this edge at all.
 368    private static bool Routable(RoutingNetworkEdgeEnumerator enumerator, ICostFunction routable,
 369        EdgeId edgeId)
 57370    {
 228371        foreach (var forward in new[] { true, false })
 57372        {
 57373            if (!enumerator.MoveTo(edgeId, forward)) continue;
 374
 57375            var (canAccess, _, _, cost, _) = routable.Get(enumerator, tailToHead: true);
 114376            if (canAccess && cost > 0) return true;
 0377        }
 378
 0379        return false;
 57380    }
 381
 382    /// The distinct edges a half has settled.
 383    private static HashSet<EdgeId> SettledEdges(SearchHalf half)
 5384    {
 5385        var edges = new HashSet<EdgeId>();
 51386        foreach (var (edge, _) in half.Settled) edges.Add(edge);
 5387        return edges;
 5388    }
 389
 390
 391}
 392
 393/// <summary>
 394/// A path, together with the snap points chosen for it.
 395/// </summary>
 396/// <remarks>
 397/// The snap points come back with the path because nobody else computed them — snapping happened
 398/// inside, as part of deciding which candidate edges a route can use.
 399/// </remarks>
 400/// <param name="Path">The path found.</param>
 401/// <param name="Source">Where the origin snapped.</param>
 402/// <param name="Target">Where the destination snapped.</param>
 403public readonly record struct ReachabilityRoute(Path Path, SnapPoint Source, SnapPoint Target);
 404
 405/// <summary>
 406/// A route plus what it was resolved against: the endpoints snapped to in the end, and the cost
 407/// functions those searches actually ran with — not the profile's, which may have been wrapped.
 408/// </summary>
 409/// <param name="Cost">As the search computed it; re-summing the path would have to reapply turn
 410/// costs and any wrapper in the same order.</param>
 411/// <param name="Settled">States both halves settled, across candidate retries. Diagnostic.</param>
 412public readonly record struct ResolvedRoute(
 413    Path Path,
 414    double Cost,
 415    SnapPoint Source,
 416    SnapPoint Target,
 417    ICostFunction ForwardCostFunction,
 418    ICostFunction BackwardCostFunction,
 419    long Settled);