| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Threading; |
| | | 4 | | using Itinero.Network; |
| | | 5 | | using Itinero.Routes.Paths; |
| | | 6 | | |
| | | 7 | | namespace 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> |
| | | 17 | | public 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) |
| | 20 | 46 | | { |
| | 21 | 47 | | if (maxOverlap is < 0 or > 1) throw new ArgumentOutOfRangeException(nameof(maxOverlap), |
| | 1 | 48 | | "An overlap share is a fraction of the candidate's length."); |
| | 19 | 49 | | if (maxAlternatives < 0) throw new ArgumentOutOfRangeException(nameof(maxAlternatives)); |
| | 19 | 50 | | if (localDetourFactor < 1) throw new ArgumentOutOfRangeException(nameof(localDetourFactor), |
| | 0 | 51 | | "A detour cannot be required to beat the stretch it replaces."); |
| | | 52 | | |
| | 19 | 53 | | var found = new List<Path>(); |
| | 20 | 54 | | if (maxAlternatives == 0 || corridor.Edges.Count == 0) return found; |
| | | 55 | | |
| | 18 | 56 | | var outgoing = new List<int>[corridor.States.Count]; |
| | 18 | 57 | | var incoming = new List<int>[corridor.States.Count]; |
| | 400 | 58 | | for (var e = 0; e < corridor.Edges.Count; e++) |
| | 182 | 59 | | { |
| | 182 | 60 | | var edge = corridor.Edges[e]; |
| | 182 | 61 | | (outgoing[edge.Tail] ??= new List<int>()).Add(e); |
| | 182 | 62 | | (incoming[edge.Head] ??= new List<int>()).Add(e); |
| | 182 | 63 | | } |
| | | 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. |
| | 18 | 67 | | var optimal = Descend(RouteCorridor.SourceNode, toDestination: true); |
| | 18 | 68 | | 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. |
| | 18 | 72 | | var shared = new HashSet<EdgeId>(); |
| | 378 | 73 | | foreach (var e in optimal) shared.Add(corridor.Edges[e].Edge); |
| | | 74 | | |
| | 18 | 75 | | var candidates = new List<(double Cost, int Edge)>(); |
| | 400 | 76 | | for (var e = 0; e < corridor.Edges.Count; e++) |
| | 182 | 77 | | { |
| | 182 | 78 | | var edge = corridor.Edges[e]; |
| | 330 | 79 | | if (shared.Contains(edge.Edge)) continue; |
| | | 80 | | |
| | 34 | 81 | | var before = corridor.CostFromOrigin[edge.Tail]; |
| | 34 | 82 | | var after = corridor.CostToDestination[edge.Head]; |
| | 34 | 83 | | if (double.IsPositiveInfinity(before) || double.IsPositiveInfinity(after)) continue; |
| | | 84 | | |
| | 34 | 85 | | candidates.Add((before + edge.Cost + after, e)); |
| | 34 | 86 | | } |
| | | 87 | | |
| | 48 | 88 | | candidates.Sort((x, y) => x.Cost.CompareTo(y.Cost)); |
| | | 89 | | |
| | 18 | 90 | | var seen = new HashSet<string>(); |
| | 18 | 91 | | var examined = 0; |
| | 116 | 92 | | foreach (var (_, via) in candidates) |
| | 32 | 93 | | { |
| | | 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. |
| | 48 | 96 | | if ((examined++ & 0xFF) == 0) cancellationToken.ThrowIfCancellationRequested(); |
| | | 97 | | |
| | 32 | 98 | | if (found.Count >= maxAlternatives) break; |
| | | 99 | | |
| | 30 | 100 | | var edges = PathThrough(via); |
| | 40 | 101 | | if (edges == null) continue; |
| | | 102 | | |
| | | 103 | | // Different via edges on the same detour rebuild the same path. |
| | 20 | 104 | | if (!seen.Add(string.Join(",", edges))) continue; |
| | | 105 | | |
| | 20 | 106 | | var length = 0d; |
| | 20 | 107 | | var overlap = 0d; |
| | 260 | 108 | | foreach (var e in edges) |
| | 100 | 109 | | { |
| | 100 | 110 | | var edge = corridor.Edges[e]; |
| | 100 | 111 | | length += edge.Length; |
| | 180 | 112 | | if (shared.Contains(edge.Edge)) overlap += edge.Length; |
| | 100 | 113 | | } |
| | | 114 | | |
| | 22 | 115 | | if (length <= 0 || overlap / length > maxOverlap) continue; |
| | 20 | 116 | | if (!DetourIsWorthIt(edges)) continue; |
| | | 117 | | |
| | 16 | 118 | | var path = Build(edges); |
| | 16 | 119 | | if (path == null) continue; |
| | | 120 | | |
| | 288 | 121 | | foreach (var e in edges) shared.Add(corridor.Edges[e].Edge); |
| | 16 | 122 | | found.Add(path); |
| | 16 | 123 | | } |
| | | 124 | | |
| | 17 | 125 | | 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) |
| | 18 | 130 | | { |
| | 18 | 131 | | var head = 0; |
| | 90 | 132 | | while (head < edges.Count && head < optimal.Count && edges[head] == optimal[head]) head++; |
| | | 133 | | |
| | 18 | 134 | | var tail = 0; |
| | 36 | 135 | | while (tail < edges.Count - head && tail < optimal.Count - head && |
| | 54 | 136 | | edges[edges.Count - 1 - tail] == optimal[optimal.Count - 1 - tail]) tail++; |
| | | 137 | | |
| | 18 | 138 | | var replaced = 0d; |
| | 198 | 139 | | for (var i = head; i < optimal.Count - tail; i++) replaced += corridor.Edges[optimal[i]].Cost; |
| | | 140 | | |
| | 18 | 141 | | var detour = 0d; |
| | 144 | 142 | | 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. |
| | 18 | 145 | | if (replaced <= 0) return detour <= 0; |
| | | 146 | | |
| | 18 | 147 | | return detour <= replaced * localDetourFactor; |
| | 18 | 148 | | } |
| | | 149 | | |
| | | 150 | | List<int>? PathThrough(int via) |
| | 30 | 151 | | { |
| | 30 | 152 | | var before = Descend(corridor.Edges[via].Tail, toDestination: false); |
| | 30 | 153 | | var after = Descend(corridor.Edges[via].Head, toDestination: true); |
| | 30 | 154 | | if (before == null || after == null) return null; |
| | | 155 | | |
| | 30 | 156 | | before.Add(via); |
| | 30 | 157 | | 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. |
| | 30 | 161 | | var visited = new HashSet<int> { corridor.Edges[before[0]].Tail }; |
| | 400 | 162 | | foreach (var e in before) |
| | 160 | 163 | | { |
| | 170 | 164 | | if (!visited.Add(corridor.Edges[e].Head)) return null; |
| | 150 | 165 | | } |
| | | 166 | | |
| | 20 | 167 | | return before; |
| | 30 | 168 | | } |
| | | 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) |
| | 78 | 173 | | { |
| | 78 | 174 | | var steps = new List<int>(); |
| | 78 | 175 | | var node = from; |
| | 78 | 176 | | var stop = toDestination ? RouteCorridor.TargetNode : RouteCorridor.SourceNode; |
| | 341 | 177 | | while (node != stop) |
| | 263 | 178 | | { |
| | 263 | 179 | | var step = Realising(toDestination ? outgoing[node] : incoming[node], node, toDestination); |
| | 263 | 180 | | if (step < 0) return null; |
| | | 181 | | |
| | 263 | 182 | | steps.Add(step); |
| | 263 | 183 | | node = toDestination ? corridor.Edges[step].Head : corridor.Edges[step].Tail; |
| | 263 | 184 | | if (steps.Count > corridor.Edges.Count) return null; |
| | 263 | 185 | | } |
| | | 186 | | |
| | 108 | 187 | | if (!toDestination) steps.Reverse(); |
| | 78 | 188 | | return steps; |
| | 78 | 189 | | } |
| | | 190 | | |
| | | 191 | | int Realising(List<int>? adjacent, int node, bool toDestination) |
| | 263 | 192 | | { |
| | 263 | 193 | | if (adjacent == null) return -1; |
| | | 194 | | |
| | 263 | 195 | | var target = toDestination ? corridor.CostToDestination[node] : corridor.CostFromOrigin[node]; |
| | 263 | 196 | | var best = -1; |
| | 263 | 197 | | var bestGap = double.MaxValue; |
| | 1423 | 198 | | foreach (var e in adjacent) |
| | 317 | 199 | | { |
| | 317 | 200 | | var edge = corridor.Edges[e]; |
| | 317 | 201 | | var from = toDestination |
| | 317 | 202 | | ? corridor.CostToDestination[edge.Head] |
| | 317 | 203 | | : corridor.CostFromOrigin[edge.Tail]; |
| | 317 | 204 | | 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. |
| | 317 | 208 | | var gap = Math.Abs(from + edge.Cost - target); |
| | 349 | 209 | | if (gap >= bestGap) continue; |
| | | 210 | | |
| | 285 | 211 | | bestGap = gap; |
| | 285 | 212 | | best = e; |
| | 285 | 213 | | } |
| | | 214 | | |
| | 263 | 215 | | return best; |
| | 263 | 216 | | } |
| | | 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) |
| | 16 | 221 | | { |
| | 16 | 222 | | var path = new Path(network); |
| | | 223 | | try |
| | 16 | 224 | | { |
| | 208 | 225 | | foreach (var e in edges) |
| | 80 | 226 | | { |
| | 80 | 227 | | var edge = corridor.Edges[e]; |
| | 80 | 228 | | path.Append(edge.Edge, edge.Forward); |
| | 80 | 229 | | } |
| | 16 | 230 | | } |
| | 0 | 231 | | catch (Exception) |
| | 0 | 232 | | { |
| | 0 | 233 | | return null; |
| | | 234 | | } |
| | | 235 | | |
| | 16 | 236 | | path.Offset1 = path.First.direction |
| | 16 | 237 | | ? route.Source.Offset |
| | 16 | 238 | | : (ushort)(ushort.MaxValue - route.Source.Offset); |
| | 16 | 239 | | path.Offset2 = path.Last.direction |
| | 16 | 240 | | ? route.Target.Offset |
| | 16 | 241 | | : (ushort)(ushort.MaxValue - route.Target.Offset); |
| | 16 | 242 | | return path; |
| | 16 | 243 | | } |
| | 18 | 244 | | } |
| | | 245 | | } |