< 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:111
Coverable lines:111
Total lines:185
Line coverage:0% (0 of 111)
Covered branches:0
Total branches:36
Branch coverage:0% (0 of 36)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
CalculatePathsAsync()0%240%
<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);
 33
 34
 035        var maxBox = settings.MaxBoxFor(routingNetwork, alternativeRouter.Source.sp);
 36
 37        bool CheckMaxDistance(VertexId v)
 038        {
 039            if (maxBox == null)
 040            {
 041                return false;
 42            }
 43
 044            if (routingNetwork == null)
 045            {
 046                throw new Exception("Router cannot be null here.");
 47            }
 48
 049            var vertex = routingNetwork.GetVertex(v);
 050            if (!maxBox.Value.Overlaps(vertex))
 051            {
 052                return true;
 53            }
 54
 055            return false;
 056        }
 57
 58        async Task<(Path? path, double cost)> RunDijkstraAsync(ICostFunction costFunction, CancellationToken cancellatio
 059        {
 060            var source = alternativeRouter.Source;
 061            var target = alternativeRouter.Target;
 62
 063            if (source.direction == null && target.direction == null)
 064            {
 65                // Run the undirected dijkstra
 066                return await Dijkstra.Default.RunAsync(routingNetwork, source.sp, target.sp,
 067                    costFunction.GetDijkstraWeightFunc(),
 068                    async v =>
 069                    {
 070                        await routingNetwork.UsageNotifier.NotifyVertex(routingNetwork, v, cancellationToken);
 071                        if (cancellationToken.IsCancellationRequested) return false;
 072                        return CheckMaxDistance(v);
 073                    });
 74            }
 75
 76            // Run directed dijkstra
 077            return await Flavours.Dijkstra.EdgeBased.Dijkstra.Default.RunAsync(routingNetwork, source, target,
 078                costFunction.GetDijkstraWeightFunc(),
 079                async v =>
 080                {
 081                    await routingNetwork.UsageNotifier.NotifyVertex(routingNetwork, v.vertexId, cancellationToken);
 082                    if (cancellationToken.IsCancellationRequested) return false;
 083                    return CheckMaxDistance(v.vertexId);
 084                });
 085        }
 86
 087        var (initialPath, initialCost) = await RunDijkstraAsync(costFunction, cancellationToken);
 088        if (initialPath == null)
 089        {
 090            return new Result<IReadOnlyList<Path>>("Not a single path found!");
 91        }
 92
 093        var results = new List<Path>(altSettings.MaxNumberOfAlternativeRoutes) {
 094                initialPath
 095            };
 96
 097        if (altSettings.MaxNumberOfAlternativeRoutes == 1) return results;
 98
 099        var costThreshold = initialCost * altSettings.MaxWeightIncreasePercentage;
 100
 0101        var seenEdges = new Dictionary<EdgeId, int>();
 0102        foreach (var (edge, _, _, _) in initialPath)
 0103        {
 0104            var count = seenEdges.GetValueOrDefault(edge, 0);
 0105            seenEdges[edge] = count + 1;
 0106        }
 107
 0108        var maxTries = altSettings.MaxNumberOfAlternativeRoutes * 5;
 0109        while (results.Count < altSettings.MaxNumberOfAlternativeRoutes && maxTries > 0)
 0110        {
 0111            if (cancellationToken.IsCancellationRequested) break;
 112
 0113            maxTries--;
 0114            var altCostFunction = new AlternativeRouteCostFunction(costFunction, seenEdges,
 0115                altSettings.PenaltyFactor);
 0116            var (altPath, altCost) = await RunDijkstraAsync(altCostFunction, cancellationToken);
 117
 0118            if (altCost > costThreshold)
 0119            {
 120                // No more alternative routes can be found
 0121                break;
 122            }
 123
 0124            if (altPath == null)
 0125            {
 126                // No more alternative routes can be found
 0127                break;
 128            }
 129
 0130            var totalEdges = 0;
 0131            var alreadyKnownEdges = 0;
 132
 0133            foreach (var (edge, _, _, _) in altPath)
 0134            {
 0135                totalEdges++;
 0136                if (seenEdges.TryGetValue(edge, out var count))
 0137                {
 0138                    seenEdges[edge] = count + 1;
 139
 140                    // Already seen!
 0141                    alreadyKnownEdges++;
 0142                }
 143                else
 0144                {
 0145                    seenEdges[edge] = 1;
 0146                }
 0147            }
 148
 0149            var overlapPercentage = (double)alreadyKnownEdges / totalEdges;
 150
 0151            if (overlapPercentage > altSettings.MaxPercentageOfEqualEdges)
 0152            {
 0153                continue;
 154            }
 155
 0156            results.Add(altPath);
 0157        }
 158
 0159        return results;
 0160    }
 161
 162    public static async Task<Result<IReadOnlyList<Path>>> PathsAsync(
 163        this IRouterOneToOneWithAlternatives withAlternatives, CancellationToken cancellationToken = default)
 0164    {
 0165        return await withAlternatives.CalculatePathsAsync(cancellationToken);
 0166    }
 167
 168    public static async Task<Result<IReadOnlyList<Route>>> CalculateAsync(this IRouterOneToOneWithAlternatives withAlter
 0169    {
 0170        var paths = await withAlternatives.CalculatePathsAsync(cancellationToken);
 171
 0172        if (paths.IsError)
 0173        {
 0174            return new Result<IReadOnlyList<Route>>(paths.ErrorMessage);
 175        }
 176
 177
 0178        var routes = paths.Value.Select(path =>
 0179            withAlternatives.Settings.RouteBuilder.Build(withAlternatives.Network,
 0180                withAlternatives.Settings.Profile, path).Value
 0181        ).ToList();
 182
 0183        return new Result<IReadOnlyList<Route>>(routes);
 0184    }
 185}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

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