< 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:115
Coverable lines:115
Total lines:190
Line coverage:0% (0 of 115)
Covered branches:0
Total branches:36
Branch coverage:0% (0 of 36)
Tag:263_26948838820

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, alternativeRouter.Target.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
 058        var isMainN = routingNetwork.GetIsMainNFunc(profile);
 59
 60        async Task<(Path? path, double cost)> RunDijkstraAsync(ICostFunction costFunction, CancellationToken cancellatio
 061        {
 062            var source = alternativeRouter.Source;
 063            var target = alternativeRouter.Target;
 64
 065            if (source.direction == null && target.direction == null)
 066            {
 67                // Run the undirected dijkstra
 068                return await Flavours.Dijkstra.Dijkstra.Default.RunAsync(routingNetwork, source.sp, target.sp,
 069                    costFunction.GetDijkstraWeightFunc(),
 070                    async v =>
 071                    {
 072                        await routingNetwork.UsageNotifier.NotifyVertex(routingNetwork, v.vertexId, cancellationToken);
 073                        if (cancellationToken.IsCancellationRequested) return false;
 074                        return CheckMaxDistance(v.vertexId);
 075                    }, cancellationToken: cancellationToken, isMainN: isMainN);
 76            }
 77
 78            // Run directed dijkstra
 079            return await Flavours.Dijkstra.Dijkstra.Default.RunAsync(routingNetwork, source, target,
 080                costFunction.GetDijkstraWeightFunc(),
 081                async v =>
 082                {
 083                    if (!routingNetwork.UsageNotifier.IsVertexDataReady(routingNetwork, v.vertexId))
 084                    {
 085                        await routingNetwork.UsageNotifier.NotifyVertex(routingNetwork, v.vertexId, cancellationToken);
 086                    }
 087                    if (cancellationToken.IsCancellationRequested) return false;
 088                    return CheckMaxDistance(v.vertexId);
 089                }, cancellationToken: cancellationToken, isMainN: isMainN);
 090        }
 91
 092        var (initialPath, initialCost) = await RunDijkstraAsync(costFunction, cancellationToken);
 093        if (initialPath == null)
 094        {
 095            return new Result<IReadOnlyList<Path>>("Not a single path found!");
 96        }
 97
 098        var results = new List<Path>(altSettings.MaxNumberOfAlternativeRoutes) {
 099                initialPath
 0100            };
 101
 0102        if (altSettings.MaxNumberOfAlternativeRoutes == 1) return results;
 103
 0104        var costThreshold = initialCost * altSettings.MaxWeightIncreasePercentage;
 105
 0106        var seenEdges = new Dictionary<EdgeId, int>();
 0107        foreach (var (edge, _, _, _) in initialPath)
 0108        {
 0109            var count = seenEdges.GetValueOrDefault(edge, 0);
 0110            seenEdges[edge] = count + 1;
 0111        }
 112
 0113        var maxTries = altSettings.MaxNumberOfAlternativeRoutes * 5;
 0114        while (results.Count < altSettings.MaxNumberOfAlternativeRoutes && maxTries > 0)
 0115        {
 0116            if (cancellationToken.IsCancellationRequested) break;
 117
 0118            maxTries--;
 0119            var altCostFunction = new AlternativeRouteCostFunction(costFunction, seenEdges,
 0120                altSettings.PenaltyFactor);
 0121            var (altPath, altCost) = await RunDijkstraAsync(altCostFunction, cancellationToken);
 122
 0123            if (altCost > costThreshold)
 0124            {
 125                // No more alternative routes can be found
 0126                break;
 127            }
 128
 0129            if (altPath == null)
 0130            {
 131                // No more alternative routes can be found
 0132                break;
 133            }
 134
 0135            var totalEdges = 0;
 0136            var alreadyKnownEdges = 0;
 137
 0138            foreach (var (edge, _, _, _) in altPath)
 0139            {
 0140                totalEdges++;
 0141                if (seenEdges.TryGetValue(edge, out var count))
 0142                {
 0143                    seenEdges[edge] = count + 1;
 144
 145                    // Already seen!
 0146                    alreadyKnownEdges++;
 0147                }
 148                else
 0149                {
 0150                    seenEdges[edge] = 1;
 0151                }
 0152            }
 153
 0154            var overlapPercentage = (double)alreadyKnownEdges / totalEdges;
 155
 0156            if (overlapPercentage > altSettings.MaxPercentageOfEqualEdges)
 0157            {
 0158                continue;
 159            }
 160
 0161            results.Add(altPath);
 0162        }
 163
 0164        return results;
 0165    }
 166
 167    public static async Task<Result<IReadOnlyList<Path>>> PathsAsync(
 168        this IRouterOneToOneWithAlternatives withAlternatives, CancellationToken cancellationToken = default)
 0169    {
 0170        return await withAlternatives.CalculatePathsAsync(cancellationToken);
 0171    }
 172
 173    public static async Task<Result<IReadOnlyList<Route>>> CalculateAsync(this IRouterOneToOneWithAlternatives withAlter
 0174    {
 0175        var paths = await withAlternatives.CalculatePathsAsync(cancellationToken);
 176
 0177        if (paths.IsError)
 0178        {
 0179            return new Result<IReadOnlyList<Route>>(paths.ErrorMessage);
 180        }
 181
 182
 0183        var routes = paths.Value.Select(path =>
 0184            withAlternatives.Settings.RouteBuilder.Build(withAlternatives.Network,
 0185                withAlternatives.Settings.Profile, path).Value
 0186        ).ToList();
 187
 0188        return new Result<IReadOnlyList<Route>>(routes);
 0189    }
 190}
Generated by: ReportGenerator 4.8.2.0
06/04/2026 - 11:29:09
GitHub | www.palmmedia.de

Methods/Properties

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