< Summary

Class:Itinero.Routing.Corridors.CorridorAlternative
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Routing/Corridors/CorridorAlternative.cs
Covered lines:133
Uncovered lines:4
Coverable lines:137
Total lines:245
Line coverage:97% (133 of 137)
Covered branches:97
Total branches:114
Branch coverage:85% (97 of 114)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
AlternativesFor(...)91.07%5698.24%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Routing/Corridors/CorridorAlternative.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Threading;
 4using Itinero.Network;
 5using Itinero.Routes.Paths;
 6
 7namespace Itinero.Routing.Corridors;
 8
 9/// <summary>
 10/// Picks alternative routes out of a corridor: cheapest first, each sharing no more than a given
 11/// share of its length with the routes already chosen, and each detouring for a reason.
 12/// </summary>
 13/// <remarks>
 14/// No searching: an edge's cheapest path is <c>CostFromOrigin[tail] + cost +
 15/// CostToDestination[head]</c>, and the budget defined the corridor, so it is never tested.
 16/// </remarks>
 17public static class CorridorAlternative
 18{
 19    /// <summary>
 20    /// Alternatives to the resolved route, cheapest first.
 21    /// </summary>
 22    /// <param name="maxOverlap">
 23    /// Share of a candidate's own length that may run along routes already chosen, 0 to 1. By
 24    /// length, and against the union of those chosen, so each differs from its predecessors too.
 25    /// </param>
 26    /// <param name="maxAlternatives">
 27    /// At most this many. <see cref="int.MaxValue"/> returns everything the corridor admits.
 28    /// </param>
 29    /// <param name="localDetourFactor">
 30    /// How much worse the stretch a candidate diverges over may be than the one it replaces.
 31    /// Without it a candidate can meet the budget overall and still spend it on one absurd loop.
 32    /// </param>
 33    /// <returns>Empty when the corridor admits none — an answer, not a failure.</returns>
 34    /// <remarks>
 35    /// Sound but not complete: each candidate is the cheapest path through one edge, so an
 36    /// alternative needing two distant edges at once is not reachable this way.
 37    /// </remarks>
 38    public static IReadOnlyList<Path> AlternativesFor(
 39        this RoutingNetwork network,
 40        ResolvedRoute route,
 41        RouteCorridor corridor,
 42        double maxOverlap,
 43        int maxAlternatives = 1,
 44        double localDetourFactor = 2.0,
 45        CancellationToken cancellationToken = default)
 2046    {
 2147        if (maxOverlap is < 0 or > 1) throw new ArgumentOutOfRangeException(nameof(maxOverlap),
 148            "An overlap share is a fraction of the candidate's length.");
 1949        if (maxAlternatives < 0) throw new ArgumentOutOfRangeException(nameof(maxAlternatives));
 1950        if (localDetourFactor < 1) throw new ArgumentOutOfRangeException(nameof(localDetourFactor),
 051            "A detour cannot be required to beat the stretch it replaces.");
 52
 1953        var found = new List<Path>();
 2054        if (maxAlternatives == 0 || corridor.Edges.Count == 0) return found;
 55
 1856        var outgoing = new List<int>[corridor.States.Count];
 1857        var incoming = new List<int>[corridor.States.Count];
 40058        for (var e = 0; e < corridor.Edges.Count; e++)
 18259        {
 18260            var edge = corridor.Edges[e];
 18261            (outgoing[edge.Tail] ??= new List<int>()).Add(e);
 18262            (incoming[edge.Head] ??= new List<int>()).Add(e);
 18263        }
 64
 65        // The optimum as corridor edges: the cheapest path through the corridor is the route it
 66        // was built around, which is what the detour test measures divergence against.
 1867        var optimal = Descend(RouteCorridor.SourceNode, toDestination: true);
 1868        if (optimal == null) return found;
 69
 70        // Seeded with the original and grown as alternatives are accepted, so each one has to
 71        // differ from its predecessors too.
 1872        var shared = new HashSet<EdgeId>();
 37873        foreach (var e in optimal) shared.Add(corridor.Edges[e].Edge);
 74
 1875        var candidates = new List<(double Cost, int Edge)>();
 40076        for (var e = 0; e < corridor.Edges.Count; e++)
 18277        {
 18278            var edge = corridor.Edges[e];
 33079            if (shared.Contains(edge.Edge)) continue;
 80
 3481            var before = corridor.CostFromOrigin[edge.Tail];
 3482            var after = corridor.CostToDestination[edge.Head];
 3483            if (double.IsPositiveInfinity(before) || double.IsPositiveInfinity(after)) continue;
 84
 3485            candidates.Add((before + edge.Cost + after, e));
 3486        }
 87
 4888        candidates.Sort((x, y) => x.Cost.CompareTo(y.Cost));
 89
 1890        var seen = new HashSet<string>();
 1891        var examined = 0;
 11692        foreach (var (_, via) in candidates)
 3293        {
 94            // Every corridor edge is a candidate when the count is unbounded, and each one
 95            // rebuilds a path, so this is where a cancelled request would otherwise keep going.
 4896            if ((examined++ & 0xFF) == 0) cancellationToken.ThrowIfCancellationRequested();
 97
 3298            if (found.Count >= maxAlternatives) break;
 99
 30100            var edges = PathThrough(via);
 40101            if (edges == null) continue;
 102
 103            // Different via edges on the same detour rebuild the same path.
 20104            if (!seen.Add(string.Join(",", edges))) continue;
 105
 20106            var length = 0d;
 20107            var overlap = 0d;
 260108            foreach (var e in edges)
 100109            {
 100110                var edge = corridor.Edges[e];
 100111                length += edge.Length;
 180112                if (shared.Contains(edge.Edge)) overlap += edge.Length;
 100113            }
 114
 22115            if (length <= 0 || overlap / length > maxOverlap) continue;
 20116            if (!DetourIsWorthIt(edges)) continue;
 117
 16118            var path = Build(edges);
 16119            if (path == null) continue;
 120
 288121            foreach (var e in edges) shared.Add(corridor.Edges[e].Edge);
 16122            found.Add(path);
 16123        }
 124
 17125        return found;
 126
 127        // Shortest prefix plus shortest suffix, so a candidate leaves the optimum once and
 128        // rejoins once: that single stretch is what this compares.
 129        bool DetourIsWorthIt(List<int> edges)
 18130        {
 18131            var head = 0;
 90132            while (head < edges.Count && head < optimal.Count && edges[head] == optimal[head]) head++;
 133
 18134            var tail = 0;
 36135            while (tail < edges.Count - head && tail < optimal.Count - head &&
 54136                   edges[edges.Count - 1 - tail] == optimal[optimal.Count - 1 - tail]) tail++;
 137
 18138            var replaced = 0d;
 198139            for (var i = head; i < optimal.Count - tail; i++) replaced += corridor.Edges[optimal[i]].Cost;
 140
 18141            var detour = 0d;
 144142            for (var i = head; i < edges.Count - tail; i++) detour += corridor.Edges[edges[i]].Cost;
 143
 144            // Nothing replaced means the candidate only adds, which no factor can excuse.
 18145            if (replaced <= 0) return detour <= 0;
 146
 18147            return detour <= replaced * localDetourFactor;
 18148        }
 149
 150        List<int>? PathThrough(int via)
 30151        {
 30152            var before = Descend(corridor.Edges[via].Tail, toDestination: false);
 30153            var after = Descend(corridor.Edges[via].Head, toDestination: true);
 30154            if (before == null || after == null) return null;
 155
 30156            before.Add(via);
 30157            before.AddRange(after);
 158
 159            // Built from opposite ends, the halves can meet in the middle and the join then holds
 160            // a loop. Cutting it out would remove the via edge, so drop the candidate.
 30161            var visited = new HashSet<int> { corridor.Edges[before[0]].Tail };
 400162            foreach (var e in before)
 160163            {
 170164                if (!visited.Add(corridor.Edges[e].Head)) return null;
 150165            }
 166
 20167            return before;
 30168        }
 169
 170        // Walk a field to its end. Every edge costs something, so each step strictly reduces
 171        // what remains and the walk cannot loop.
 172        List<int>? Descend(int from, bool toDestination)
 78173        {
 78174            var steps = new List<int>();
 78175            var node = from;
 78176            var stop = toDestination ? RouteCorridor.TargetNode : RouteCorridor.SourceNode;
 341177            while (node != stop)
 263178            {
 263179                var step = Realising(toDestination ? outgoing[node] : incoming[node], node, toDestination);
 263180                if (step < 0) return null;
 181
 263182                steps.Add(step);
 263183                node = toDestination ? corridor.Edges[step].Head : corridor.Edges[step].Tail;
 263184                if (steps.Count > corridor.Edges.Count) return null;
 263185            }
 186
 108187            if (!toDestination) steps.Reverse();
 78188            return steps;
 78189        }
 190
 191        int Realising(List<int>? adjacent, int node, bool toDestination)
 263192        {
 263193            if (adjacent == null) return -1;
 194
 263195            var target = toDestination ? corridor.CostToDestination[node] : corridor.CostFromOrigin[node];
 263196            var best = -1;
 263197            var bestGap = double.MaxValue;
 1423198            foreach (var e in adjacent)
 317199            {
 317200                var edge = corridor.Edges[e];
 317201                var from = toDestination
 317202                    ? corridor.CostToDestination[edge.Head]
 317203                    : corridor.CostFromOrigin[edge.Tail];
 317204                if (double.IsPositiveInfinity(from)) continue;
 205
 206                // Exact arithmetic would give equality; costs are accumulated doubles, so take
 207                // the closest instead of trusting it.
 317208                var gap = Math.Abs(from + edge.Cost - target);
 349209                if (gap >= bestGap) continue;
 210
 285211                bestGap = gap;
 285212                best = e;
 285213            }
 214
 263215            return best;
 263216        }
 217
 218        // Offsets follow the rule the router's own path building uses: they trim the first and
 219        // last edge, which for any path between these two snap points are the snapped edges.
 220        Path? Build(List<int> edges)
 16221        {
 16222            var path = new Path(network);
 223            try
 16224            {
 208225                foreach (var e in edges)
 80226                {
 80227                    var edge = corridor.Edges[e];
 80228                    path.Append(edge.Edge, edge.Forward);
 80229                }
 16230            }
 0231            catch (Exception)
 0232            {
 0233                return null;
 234            }
 235
 16236            path.Offset1 = path.First.direction
 16237                ? route.Source.Offset
 16238                : (ushort)(ushort.MaxValue - route.Source.Offset);
 16239            path.Offset2 = path.Last.direction
 16240                ? route.Target.Offset
 16241                : (ushort)(ushort.MaxValue - route.Target.Offset);
 16242            return path;
 16243        }
 18244    }
 245}

Methods/Properties

AlternativesFor(...)