< Summary

Class:Itinero.Network.Search.Reachability.LocalPocket
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Reachability/LocalPocket.cs
Covered lines:106
Uncovered lines:3
Coverable lines:109
Total lines:214
Line coverage:97.2% (106 of 109)
Covered branches:66
Total branches:70
Branch coverage:94.2% (66 of 70)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_Members()100%1100%
get_Perimeter()100%1100%
get_Abandoned()100%1100%
Compose(...)91.66%2493.61%
Reachable()100%16100%
NonLocalComponent(...)90.9%22100%
EndsOf(...)100%8100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Reachability/LocalPocket.cs

#LineLine coverage
 1using System.Collections.Generic;
 2using System.Linq;
 3using Itinero.Network.Enumerators.Edges;
 4using Itinero.Routing.Costs;
 5
 6namespace Itinero.Network.Search.Reachability;
 7
 8/// <summary>
 9/// The local-access region around an endpoint: the edges a route may move through freely before it
 10/// is genuinely on the network.
 11/// </summary>
 12/// <remarks>
 13/// Reconstructs, lazily and around one endpoint, the class island detection precomputed per tile:
 14/// local-access edges plus the untagged segments enclosed by them.
 15/// </remarks>
 16internal static class LocalPocket
 17{
 18    /// <summary>
 19    /// Members are treated as local-access by the search; perimeter edges are the exits.
 20    /// </summary>
 21    /// <remarks>
 22    /// Abandoned means the region outgrew its budget, so it is not a pocket and the caller should
 23    /// behave as though none was found.
 24    /// </remarks>
 25    internal sealed class Result
 26    {
 3527        public required HashSet<EdgeId> Members { get; init; }
 2328        public required HashSet<EdgeId> Perimeter { get; init; }
 2829        public required bool Abandoned { get; init; }
 30    }
 31
 32    /// <summary>
 33    /// Composes the pocket around <paramref name="seeds"/>, in the half's own direction.
 34    /// </summary>
 35    /// <param name="seeds">
 36    /// The candidate edge, or the settled set of a half that stalled — already proved closed, so it
 37    /// costs nothing to start from.
 38    /// </param>
 39    /// <param name="asOrigin">True for a half leaving an origin, false for one arriving.</param>
 40    /// <param name="componentAllowance">
 41    /// How far an N component may be followed before it counts as main network. Exceeding it means
 42    /// "not absorbed", which is the safe direction: the strict rule then applies.
 43    /// </param>
 44    /// <param name="budget">Total members allowed before the region is too big to be a pocket.</param>
 45    public static Result Compose(
 46        RoutingNetwork network,
 47        ICostFunction costFunction,
 48        IEnumerable<EdgeId> seeds,
 49        bool asOrigin,
 50        int componentAllowance,
 51        int budget)
 1552    {
 1553        var members = new HashSet<EdgeId>(seeds);
 1554        var perimeter = new HashSet<EdgeId>();
 55
 56        // Edges in a component that outgrew its allowance. Main network is one component, so the
 57        // first seed to discover it answers for every later seed inside it.
 1558        var knownMain = new HashSet<EdgeId>();
 59
 1560        var changed = true;
 5861        while (changed)
 4462        {
 4463            if (members.Count > budget)
 164            {
 165                return new Result { Members = members, Perimeter = perimeter, Abandoned = true };
 66            }
 67
 4368            changed = false;
 69
 70            // (a) Grow over local-access edges, and collect the N edges we end up against.
 71            // Materialised: the loop below adds to members, and Reachable enumerates it lazily.
 4372            var nSeeds = new List<EdgeId>();
 44573            foreach (var edge in Reachable(network, costFunction, members, asOrigin).ToList())
 15874            {
 27575                if (members.Contains(edge.edge) || perimeter.Contains(edge.edge)) continue;
 76
 4177                if (edge.localAccess)
 2578                {
 2579                    members.Add(edge.edge);
 2580                    changed = true;
 2581                }
 82                else
 1683                {
 1684                    nSeeds.Add(edge.edge);
 1685                }
 4186            }
 87
 6788            if (changed) continue;
 89
 90            // (b) One pass over the N edges against the pocket, sharing knownMain so main network
 91            // is discovered once rather than per seed.
 8592            foreach (var seed in nSeeds)
 1493            {
 1494                if (members.Contains(seed) || perimeter.Contains(seed)) continue;
 95
 1496                if (knownMain.Contains(seed))
 097                {
 098                    perimeter.Add(seed);
 099                    continue;
 100                }
 101
 14102                var (component, escaped) = NonLocalComponent(
 14103                    network, costFunction, seed, asOrigin, componentAllowance, knownMain);
 104
 14105                if (escaped)
 9106                {
 9107                    knownMain.UnionWith(component);
 9108                    perimeter.Add(seed);
 9109                }
 110                else
 5111                {
 5112                    members.UnionWith(component);
 5113                    changed = true;
 5114                }
 14115            }
 19116        }
 117
 14118        return new Result { Members = members, Perimeter = perimeter, Abandoned = false };
 15119    }
 120
 121    /// The edges reachable in one step from any member, in the half's direction.
 122    private static IEnumerable<(EdgeId edge, bool localAccess)> Reachable(
 123        RoutingNetwork network, ICostFunction costFunction, HashSet<EdgeId> from, bool asOrigin)
 43124    {
 43125        var probe = network.GetEdgeEnumerator();
 43126        var seen = new HashSet<EdgeId>();
 127
 387128        foreach (var member in from)
 129129        {
 903130            foreach (var vertex in EndsOf(probe, member, costFunction, asOrigin))
 258131            {
 258132                if (!probe.MoveTo(vertex)) continue;
 133
 738134                while (probe.MoveNext())
 480135                {
 738136                    if (probe.EdgeId == member) continue;
 285137                    if (!seen.Add(probe.EdgeId)) continue;
 138
 159139                    var (canAccess, _, localAccess, cost, _) =
 159140                        costFunction.Get(probe, tailToHead: asOrigin);
 160141                    if (!canAccess || cost <= 0) continue;
 142
 158143                    yield return (probe.EdgeId, localAccess);
 158144                }
 258145            }
 129146        }
 43147    }
 148
 149    /// <summary>
 150    /// The component of <paramref name="seed"/> over non-local edges only.
 151    /// </summary>
 152    /// <returns>
 153    /// The edges found, and whether it escaped — outgrew the allowance or ran into known main
 154    /// network, either of which means it is not enclosed.
 155    /// </returns>
 156    private static (HashSet<EdgeId> component, bool escaped) NonLocalComponent(
 157        RoutingNetwork network, ICostFunction costFunction, EdgeId seed, bool asOrigin,
 158        int allowance, HashSet<EdgeId> knownMain)
 14159    {
 14160        var probe = network.GetEdgeEnumerator();
 14161        var component = new HashSet<EdgeId> { seed };
 14162        var queue = new Queue<EdgeId>();
 14163        queue.Enqueue(seed);
 164
 14165        var expansions = 0;
 86166        while (queue.Count > 0)
 81167        {
 90168            if (++expansions > allowance) return (component, true);
 169
 72170            var edge = queue.Dequeue();
 72171            if (knownMain.Contains(edge)) return (component, true);
 172
 488173            foreach (var vertex in EndsOf(probe, edge, costFunction, asOrigin))
 136174            {
 136175                if (!probe.MoveTo(vertex)) continue;
 176
 408177                while (probe.MoveNext())
 272178                {
 408179                    if (probe.EdgeId == edge) continue;
 180
 136181                    var (canAccess, _, localAccess, cost, _) =
 136182                        costFunction.Get(probe, tailToHead: asOrigin);
 136183                    if (!canAccess || cost <= 0) continue;
 184
 185                    // Local edges bound the component rather than extending it.
 154186                    if (localAccess) continue;
 169187                    if (!component.Add(probe.EdgeId)) continue;
 188
 67189                    queue.Enqueue(probe.EdgeId);
 67190                }
 136191            }
 72192        }
 193
 5194        return (component, false);
 14195    }
 196
 197    /// The vertices an edge can be left by, in the half's direction.
 198    private static List<VertexId> EndsOf(RoutingNetworkEdgeEnumerator probe, EdgeId edge,
 199        ICostFunction costFunction, bool asOrigin)
 201200    {
 201201        var ends = new List<VertexId>(2);
 1407202        foreach (var forward in new[] { true, false })
 402203        {
 402204            if (!probe.MoveTo(edge, forward)) continue;
 205
 402206            var (canAccess, _, _, cost, _) = costFunction.Get(probe, tailToHead: asOrigin);
 410207            if (!canAccess || cost <= 0) continue;
 208
 394209            ends.Add(probe.Head);
 394210        }
 211
 201212        return ends;
 201213    }
 214}