< Summary

Class:Itinero.Routing.Alternatives.IRouterOneToOneWithAlternativesExtensions
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Alternatives/IRouterOneToOneWithAlternativesExtensions.cs
Covered lines:0
Uncovered lines:116
Coverable lines:116
Total lines:191
Line coverage:0% (0 of 116)
Covered branches:0
Total branches:38
Branch coverage:0% (0 of 38)
Tag:267_28791001112

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
CalculatePathsAsync()0%260%
<CalculatePathsAsync()0%40%
PathsAsync()100%10%
CalculateAsync()0%20%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Alternatives/IRouterOneToOneWithAlternativesExtensions.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using System.Net.Http.Headers;
 5using System.Threading;
 6using System.Threading.Tasks;
 7using Itinero.Geo;
 8using Itinero.Network;
 9using Itinero.Routes;
 10using Itinero.Routes.Paths;
 11using Itinero.Routing.Costs;
 12using Itinero.Routing.Flavours.Dijkstra;
 13
 14namespace Itinero.Routing.Alternatives;
 15
 16public static class IRouterOneToOneWithAlternativesExtensions
 17{
 18    internal static async Task<Result<IReadOnlyList<Path>>> CalculatePathsAsync(
 19        this IRouterOneToOneWithAlternatives alternativeRouter, CancellationToken cancellationToken)
 020    {
 021        var settings = alternativeRouter.Settings;
 022        var altSettings = alternativeRouter.AlternativeRouteSettings;
 023        var routingNetwork = alternativeRouter.Network;
 24
 025        if (routingNetwork == null)
 026        {
 027            throw new NullReferenceException(
 028                "RoutingNetwork is null, cannot do route planning without a routing network");
 29        }
 30
 031        var profile = settings.Profile;
 032        var costFunction = routingNetwork.GetCostFunctionFor(profile);
 033        if (settings.CostFunctionWrapper != null) costFunction = settings.CostFunctionWrapper(costFunction);
 34
 35
 036        var maxBox = settings.MaxBoxFor(routingNetwork, [alternativeRouter.Source.sp, alternativeRouter.Target.sp]);
 37
 38        bool CheckMaxDistance(VertexId v)
 039        {
 040            if (maxBox == null)
 041            {
 042                return false;
 43            }
 44
 045            if (routingNetwork == null)
 046            {
 047                throw new Exception("Router cannot be null here.");
 48            }
 49
 050            var vertex = routingNetwork.GetVertex(v);
 051            if (!maxBox.Value.Overlaps(vertex))
 052            {
 053                return true;
 54            }
 55
 056            return false;
 057        }
 58
 059        var isMainN = routingNetwork.GetIsMainNFunc(profile);
 60
 61        async Task<(Path? path, double cost)> RunDijkstraAsync(ICostFunction costFunction, CancellationToken cancellatio
 062        {
 063            var source = alternativeRouter.Source;
 064            var target = alternativeRouter.Target;
 65
 066            if (source.direction == null && target.direction == null)
 067            {
 68                // Run the undirected dijkstra
 069                return await Flavours.Dijkstra.Dijkstra.Default.RunAsync(routingNetwork, source.sp, target.sp,
 070                    costFunction.GetDijkstraWeightFunc(),
 071                    async v =>
 072                    {
 073                        await routingNetwork.UsageNotifier.NotifyVertex(routingNetwork, v.vertexId, cancellationToken);
 074                        if (cancellationToken.IsCancellationRequested) return false;
 075                        return CheckMaxDistance(v.vertexId);
 076                    }, cancellationToken: cancellationToken, isMainN: isMainN);
 77            }
 78
 79            // Run directed dijkstra
 080            return await Flavours.Dijkstra.Dijkstra.Default.RunAsync(routingNetwork, source, target,
 081                costFunction.GetDijkstraWeightFunc(),
 082                async v =>
 083                {
 084                    if (!routingNetwork.UsageNotifier.IsVertexDataReady(routingNetwork, v.vertexId))
 085                    {
 086                        await routingNetwork.UsageNotifier.NotifyVertex(routingNetwork, v.vertexId, cancellationToken);
 087                    }
 088                    if (cancellationToken.IsCancellationRequested) return false;
 089                    return CheckMaxDistance(v.vertexId);
 090                }, cancellationToken: cancellationToken, isMainN: isMainN);
 091        }
 92
 093        var (initialPath, initialCost) = await RunDijkstraAsync(costFunction, cancellationToken);
 094        if (initialPath == null)
 095        {
 096            return new Result<IReadOnlyList<Path>>("Not a single path found!");
 97        }
 98
 099        var results = new List<Path>(altSettings.MaxNumberOfAlternativeRoutes) {
 0100                initialPath
 0101            };
 102
 0103        if (altSettings.MaxNumberOfAlternativeRoutes == 1) return results;
 104
 0105        var costThreshold = initialCost * altSettings.MaxWeightIncreasePercentage;
 106
 0107        var seenEdges = new Dictionary<EdgeId, int>();
 0108        foreach (var (edge, _, _, _) in initialPath)
 0109        {
 0110            var count = seenEdges.GetValueOrDefault(edge, 0);
 0111            seenEdges[edge] = count + 1;
 0112        }
 113
 0114        var maxTries = altSettings.MaxNumberOfAlternativeRoutes * 5;
 0115        while (results.Count < altSettings.MaxNumberOfAlternativeRoutes && maxTries > 0)
 0116        {
 0117            if (cancellationToken.IsCancellationRequested) break;
 118
 0119            maxTries--;
 0120            var altCostFunction = new AlternativeRouteCostFunction(costFunction, seenEdges,
 0121                altSettings.PenaltyFactor);
 0122            var (altPath, altCost) = await RunDijkstraAsync(altCostFunction, cancellationToken);
 123
 0124            if (altCost > costThreshold)
 0125            {
 126                // No more alternative routes can be found
 0127                break;
 128            }
 129
 0130            if (altPath == null)
 0131            {
 132                // No more alternative routes can be found
 0133                break;
 134            }
 135
 0136            var totalEdges = 0;
 0137            var alreadyKnownEdges = 0;
 138
 0139            foreach (var (edge, _, _, _) in altPath)
 0140            {
 0141                totalEdges++;
 0142                if (seenEdges.TryGetValue(edge, out var count))
 0143                {
 0144                    seenEdges[edge] = count + 1;
 145
 146                    // Already seen!
 0147                    alreadyKnownEdges++;
 0148                }
 149                else
 0150                {
 0151                    seenEdges[edge] = 1;
 0152                }
 0153            }
 154
 0155            var overlapPercentage = (double)alreadyKnownEdges / totalEdges;
 156
 0157            if (overlapPercentage > altSettings.MaxPercentageOfEqualEdges)
 0158            {
 0159                continue;
 160            }
 161
 0162            results.Add(altPath);
 0163        }
 164
 0165        return results;
 0166    }
 167
 168    public static async Task<Result<IReadOnlyList<Path>>> PathsAsync(
 169        this IRouterOneToOneWithAlternatives withAlternatives, CancellationToken cancellationToken = default)
 0170    {
 0171        return await withAlternatives.CalculatePathsAsync(cancellationToken);
 0172    }
 173
 174    public static async Task<Result<IReadOnlyList<Route>>> CalculateAsync(this IRouterOneToOneWithAlternatives withAlter
 0175    {
 0176        var paths = await withAlternatives.CalculatePathsAsync(cancellationToken);
 177
 0178        if (paths.IsError)
 0179        {
 0180            return new Result<IReadOnlyList<Route>>(paths.ErrorMessage);
 181        }
 182
 183
 0184        var routes = paths.Value.Select(path =>
 0185            withAlternatives.Settings.RouteBuilder.Build(withAlternatives.Network,
 0186                withAlternatives.Settings.Profile, path).Value
 0187        ).ToList();
 188
 0189        return new Result<IReadOnlyList<Route>>(routes);
 0190    }
 191}
Generated by: ReportGenerator 4.8.2.0
07/06/2026 - 12:21:39
GitHub | www.palmmedia.de

Methods/Properties

CalculatePathsAsync()
<CalculatePathsAsync()
PathsAsync()
CalculateAsync()