< Summary

Class:Itinero.Network.Search.Islands.IslandLabels
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/IslandLabels.cs
Covered lines:137
Uncovered lines:41
Coverable lines:178
Total lines:327
Line coverage:76.9% (137 of 178)
Covered branches:63
Total branches:98
Branch coverage:64.2% (63 of 98)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%1100%
get_Islands()100%2100%
AddNew(...)50%2100%
AddTo(...)50%873.33%
ConnectTo(...)100%6100%
Merge(...)0%60%
TryGet(...)100%10%
TryGetWithDetails(...)75%487.5%
SetAsFinal(...)50%280%
FindLoops(...)95%20100%
Merge(...)58.69%4670.68%
GetEnumerator()0%20%
System.Collections.IEnumerable.GetEnumerator()100%10%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/IslandLabels.cs

#LineLine coverage
 1using System;
 2using System.Collections;
 3using System.Collections.Generic;
 4using System.Linq;
 5using Itinero.Routing.DataStructures;
 6
 7namespace Itinero.Network.Search.Islands;
 8
 9internal class IslandLabels : IEnumerable<(EdgeId edge, uint label)>
 10{
 11    /// <summary>
 12    /// The not an island label.
 13    /// </summary>
 14    public const uint NotAnIslandLabel = 0;
 15
 16    /// <summary>
 17    /// Keeps a label for each edge.
 18    /// - Starting each edge starts with it's own unique Id.
 19    /// - When edges are bidirectionally connected they get take on the lowest Id of their neighbour.
 20    /// </summary>
 1321    private readonly Dictionary<EdgeId, uint> _labels = new();
 1322    private readonly Dictionary<uint, (uint size, bool final)> _islands = new(); // holds the size per island.
 1323    private readonly IslandLabelGraph _labelGraph = new();
 24    private readonly int _maxIslandSize;
 25
 1326    internal IslandLabels(int maxIslandSize)
 1327    {
 1328        _maxIslandSize = maxIslandSize;
 1329        _islands.Add(0, (uint.MaxValue, true));
 1330        _labelGraph.AddVertex();
 1331    }
 32
 33    /// <summary>
 34    /// Gets all the islands.
 35    /// </summary>
 36    public IEnumerable<(uint label, uint size, bool final)> Islands
 37    {
 38        get
 339        {
 1540            foreach (var (label, (size, final)) in _islands)
 341            {
 342                yield return (label, size, final);
 343            }
 344        }
 45    }
 46
 47    /// <summary>
 48    /// Creates a new label.
 49    /// </summary>
 50    /// <returns></returns>
 51    public (uint label, uint size, bool final) AddNew(EdgeId edge, bool final = false)
 2952    {
 2953        if (_labels.ContainsKey(edge)) throw new ArgumentOutOfRangeException(nameof(edge));
 54
 2955        var label = _labelGraph.AddVertex();
 56
 2957        _labels[edge] = label;
 2958        _islands[label] = (1, final);
 59
 2960        return (label, 1, final);
 2961    }
 62
 63    /// <summary>
 64    /// Adds an edge to an already existing island.
 65    /// </summary>
 66    /// <param name="label"></param>
 67    /// <param name="edge"></param>
 68    /// <returns></returns>
 69    public (uint label, uint size, bool final) AddTo(uint label, EdgeId edge)
 370    {
 371        if (!_islands.TryGetValue(label, out var islandDetails)) throw new ArgumentOutOfRangeException(nameof(label));
 72
 373        if (islandDetails.size < uint.MaxValue) islandDetails.size += 1;
 374        _islands[label] = (islandDetails.size, final: islandDetails.final);
 375        _labels[edge] = label;
 76
 377        if (_islands[label].size >= _maxIslandSize &&
 378            label != NotAnIslandLabel)
 079        {
 80            // this island just grew over the maximum.
 081            this.Merge([label, NotAnIslandLabel]);
 082            var labelDetails = _islands[NotAnIslandLabel];
 083            return (NotAnIslandLabel, labelDetails.size, final: islandDetails.final);
 84        }
 85        else
 386        {
 387            var labelDetails = _islands[label];
 388            return (label, labelDetails.size, final: islandDetails.final);
 89        }
 390    }
 91
 92    /// <summary>
 93    /// Connects the islands representing the two labels, tail -> head.
 94    /// </summary>
 95    /// <param name="tail">The tail label.</param>
 96    /// <param name="head">The head label.</param>
 97    internal bool ConnectTo(uint tail, uint head)
 3998    {
 4599        if (tail == head) return false;
 100
 34101        if (_labelGraph.HasEdge(tail, head)) return false;
 102
 32103        var headHasEdge = _labelGraph.HasEdge(head);
 32104        _labelGraph.AddEdge(tail, head);
 105
 46106        if (headHasEdge) return this.FindLoops(head);
 18107        return false;
 39108    }
 109
 110    /// <summary>
 111    /// Merges the two given islands.
 112    /// </summary>
 113    /// <param name="tail"></param>
 114    /// <param name="head"></param>
 115    internal void Merge(uint tail, uint head)
 0116    {
 0117        if (tail == head) return;
 118
 0119        if (!_labelGraph.HasVertex(tail)) throw new ArgumentException("Label does not exist", nameof(tail));
 0120        if (!_labelGraph.HasVertex(head)) throw new ArgumentException("Label does not exist", nameof(head));
 121
 0122        this.Merge([tail, head]);
 123
 124        // var edgesAdded = false;
 125        // if (!_labelGraph.HasEdge(tail, head))
 126        // {
 127        //     edgesAdded = true;
 128        //     _labelGraph.AddEdge(tail, head);
 129        // }
 130        // if (!_labelGraph.HasEdge(head, tail))
 131        // {
 132        //     edgesAdded = true;
 133        //     _labelGraph.AddEdge(head, tail);
 134        // }
 135        // if (!edgesAdded) return;
 136        //
 137        // this.FindLoops(head);
 0138    }
 139
 140    /// <summary>
 141    /// Gets the label for the given edge, if any.
 142    /// </summary>
 143    /// <param name="edge"></param>
 144    /// <param name="label"></param>
 145    /// <returns></returns>
 146    public bool TryGet(EdgeId edge, out uint label)
 0147    {
 0148        return _labels.TryGetValue(edge, out label);
 0149    }
 150
 151    /// <summary>
 152    /// Gets the island label for the given edge and its size, if any.
 153    /// </summary>
 154    /// <param name="edge"></param>
 155    /// <param name="island"></param>
 156    /// <returns></returns>
 157    public bool TryGetWithDetails(EdgeId edge, out (uint label, uint size, bool final) island)
 103158    {
 103159        island = (0, 0, false);
 135160        if (!_labels.TryGetValue(edge, out var label)) return false;
 161
 71162        if (!_islands.TryGetValue(label, out var islandState))
 0163            throw new Exception("Island does not exist");
 164
 71165        island = (label, islandState.size, final: islandState.final);
 71166        return true;
 103167    }
 168
 169    /// <summary>
 170    /// Sets the given island as final, it cannot grow any further.
 171    /// </summary>
 172    /// <param name="label">The label of the island.</param>
 173    public void SetAsFinal(uint label)
 8174    {
 8175        if (!_islands.TryGetValue(label, out var islandState))
 0176            throw new Exception("Island does not exist");
 177
 8178        _islands[label] = (islandState.size, true);
 8179    }
 180
 181    private bool FindLoops(uint label)
 14182    {
 14183        var pathTree = new PathTree();
 14184        var settled = new HashSet<uint>();
 14185        var queue = new Queue<uint>();
 14186        var loop = new HashSet<uint>(); // keeps all with a path back to label, initially only label.
 187
 14188        var loopFound = false;
 14189        var enumerator = _labelGraph.GetEdgeEnumerator();
 28190        while (true)
 28191        {
 28192            if (!enumerator.MoveTo(label)) throw new Exception("Cannot search for loops on label that does not exist");
 193
 28194            loop.Add(label);
 28195            queue.Enqueue(pathTree.Add(label, uint.MaxValue));
 196
 71197            while (queue.Count > 0)
 43198            {
 43199                var pointer = queue.Dequeue();
 43200                pathTree.Get(pointer, out var current, out var previous);
 201
 43202                if (!settled.Add(current)) continue;
 43203                if (!enumerator.MoveTo(current)) continue;
 204
 101205                while (enumerator.MoveNext())
 58206                {
 58207                    var n = enumerator.Head;
 87208                    if (!enumerator.Forward) continue;
 209
 29210                    if (loop.Contains(n))
 14211                    {
 212                        // yay, a loop!
 14213                        loop.Add(current);
 29214                        while (previous != uint.MaxValue)
 15215                        {
 15216                            pathTree.Get(previous, out current, out previous);
 15217                            loop.Add(current);
 15218                        }
 14219                    }
 220
 43221                    if (settled.Contains(n)) continue;
 15222                    queue.Enqueue(pathTree.Add(n, pointer));
 15223                }
 43224            }
 225
 42226            if (loop.Count <= 1) return loopFound;
 227
 14228            label = this.Merge(loop);
 14229            loopFound = true;
 230
 14231            loop.Clear();
 14232            pathTree.Clear();
 14233            settled.Clear();
 14234            queue.Clear();
 14235        }
 14236    }
 237
 238    private uint Merge(HashSet<uint> labels)
 14239    {
 19240        while (true)
 19241        {
 242            // build a list of neighbours of the labels to be removed.
 19243            var edgeEnumerator = _labelGraph.GetEdgeEnumerator();
 19244            var bestLabel = uint.MaxValue;
 19245            var neighbours = new Dictionary<uint, (bool forward, bool backward)>();
 135246            foreach (var label in labels)
 39247            {
 68248                if (label < bestLabel) bestLabel = label;
 39249                if (!edgeEnumerator.MoveTo(label)) continue;
 250
 97251                while (edgeEnumerator.MoveNext())
 58252                {
 58253                    var n = edgeEnumerator.Head;
 116254                    if (labels.Contains(n)) continue;
 255
 0256                    (bool forward, bool backward) data = edgeEnumerator.Forward ? (true, false) : (false, true);
 257
 0258                    if (neighbours.TryGetValue(n, out var existingData))
 0259                    {
 0260                        data = (existingData.forward || data.forward, existingData.backward || data.backward);
 0261                    }
 262
 0263                    neighbours[n] = data;
 0264                }
 39265            }
 19266            if (bestLabel == uint.MaxValue) throw new Exception("Cannot merge empty loop");
 267
 268            // add all edges to the neighbours again.
 57269            foreach (var (neighbour, data) in neighbours)
 0270            {
 0271                if (data.forward)
 0272                {
 0273                    if (!_labelGraph.HasEdge(bestLabel, neighbour)) _labelGraph.AddEdge(bestLabel, neighbour);
 0274                }
 275
 0276                if (data.backward)
 0277                {
 0278                    if (!_labelGraph.HasEdge(neighbour, bestLabel)) _labelGraph.AddEdge(neighbour, bestLabel);
 0279                }
 0280            }
 281
 19282            var bestData = _islands[bestLabel];
 135283            foreach (var label in labels)
 39284            {
 58285                if (label == bestLabel) continue;
 20286                _labelGraph.RemoveVertex(label);
 287
 20288                var data = _islands[label];
 31289                if (bestData.size < uint.MaxValue) bestData.size += data.size;
 20290                _islands.Remove(label);
 20291            }
 292
 19293            _islands[bestLabel] = bestData;
 294
 163295            foreach (var k in _labels.Keys.ToArray())
 53296            {
 53297                var val = _labels[k];
 73298                if (val == bestLabel) continue;
 36299                if (!labels.Contains(val)) continue;
 300
 30301                _labels[k] = bestLabel;
 30302            }
 303
 28304            if (bestLabel == NotAnIslandLabel) return bestLabel;
 10305            if (_islands[bestLabel].size < _maxIslandSize)
 5306            {
 5307                return bestLabel;
 308            }
 309
 5310            labels = [bestLabel, NotAnIslandLabel];
 5311            continue;
 312        }
 14313    }
 314
 315    public IEnumerator<(EdgeId edge, uint label)> GetEnumerator()
 0316    {
 0317        foreach (var (key, value) in _labels)
 0318        {
 0319            yield return (key, value);
 0320        }
 0321    }
 322
 323    IEnumerator IEnumerable.GetEnumerator()
 0324    {
 0325        return this.GetEnumerator();
 0326    }
 327}
Generated by: ReportGenerator 4.8.2.0
04/15/2025 - 13:59:49
GitHub | www.palmmedia.de

Methods/Properties

.ctor(...)
get_Islands()
AddNew(...)
AddTo(...)
ConnectTo(...)
Merge(...)
TryGet(...)
TryGetWithDetails(...)
SetAsFinal(...)
FindLoops(...)
Merge(...)
GetEnumerator()
System.Collections.IEnumerable.GetEnumerator()