< 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:0
Uncovered lines:178
Coverable lines:178
Total lines:327
Line coverage:0% (0 of 178)
Covered branches:0
Total branches:98
Branch coverage:0% (0 of 98)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor(...)100%10%
get_Islands()0%20%
AddNew(...)0%20%
AddTo(...)0%80%
ConnectTo(...)0%60%
Merge(...)0%60%
TryGet(...)100%10%
TryGetWithDetails(...)0%40%
SetAsFinal(...)0%20%
FindLoops(...)0%200%
Merge(...)0%460%
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>
 021    private readonly Dictionary<EdgeId, uint> _labels = new();
 022    private readonly Dictionary<uint, (uint size, bool final)> _islands = new(); // holds the size per island.
 023    private readonly IslandLabelGraph _labelGraph = new();
 24    private readonly int _maxIslandSize;
 25
 026    internal IslandLabels(int maxIslandSize)
 027    {
 028        _maxIslandSize = maxIslandSize;
 029        _islands.Add(0, (uint.MaxValue, true));
 030        _labelGraph.AddVertex();
 031    }
 32
 33    /// <summary>
 34    /// Gets all the islands.
 35    /// </summary>
 36    public IEnumerable<(uint label, uint size, bool final)> Islands
 37    {
 38        get
 039        {
 040            foreach (var (label, (size, final)) in _islands)
 041            {
 042                yield return (label, size, final);
 043            }
 044        }
 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)
 052    {
 053        if (_labels.ContainsKey(edge)) throw new ArgumentOutOfRangeException(nameof(edge));
 54
 055        var label = _labelGraph.AddVertex();
 56
 057        _labels[edge] = label;
 058        _islands[label] = (1, final);
 59
 060        return (label, 1, final);
 061    }
 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)
 070    {
 071        if (!_islands.TryGetValue(label, out var islandDetails)) throw new ArgumentOutOfRangeException(nameof(label));
 72
 073        if (islandDetails.size < uint.MaxValue) islandDetails.size += 1;
 074        _islands[label] = (islandDetails.size, final: islandDetails.final);
 075        _labels[edge] = label;
 76
 077        if (_islands[label].size >= _maxIslandSize &&
 078            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
 086        {
 087            var labelDetails = _islands[label];
 088            return (label, labelDetails.size, final: islandDetails.final);
 89        }
 090    }
 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)
 098    {
 099        if (tail == head) return false;
 100
 0101        if (_labelGraph.HasEdge(tail, head)) return false;
 102
 0103        var headHasEdge = _labelGraph.HasEdge(head);
 0104        _labelGraph.AddEdge(tail, head);
 105
 0106        if (headHasEdge) return this.FindLoops(head);
 0107        return false;
 0108    }
 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)
 0158    {
 0159        island = (0, 0, false);
 0160        if (!_labels.TryGetValue(edge, out var label)) return false;
 161
 0162        if (!_islands.TryGetValue(label, out var islandState))
 0163            throw new Exception("Island does not exist");
 164
 0165        island = (label, islandState.size, final: islandState.final);
 0166        return true;
 0167    }
 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)
 0174    {
 0175        if (!_islands.TryGetValue(label, out var islandState))
 0176            throw new Exception("Island does not exist");
 177
 0178        _islands[label] = (islandState.size, true);
 0179    }
 180
 181    private bool FindLoops(uint label)
 0182    {
 0183        var pathTree = new PathTree();
 0184        var settled = new HashSet<uint>();
 0185        var queue = new Queue<uint>();
 0186        var loop = new HashSet<uint>(); // keeps all with a path back to label, initially only label.
 187
 0188        var loopFound = false;
 0189        var enumerator = _labelGraph.GetEdgeEnumerator();
 0190        while (true)
 0191        {
 0192            if (!enumerator.MoveTo(label)) throw new Exception("Cannot search for loops on label that does not exist");
 193
 0194            loop.Add(label);
 0195            queue.Enqueue(pathTree.Add(label, uint.MaxValue));
 196
 0197            while (queue.Count > 0)
 0198            {
 0199                var pointer = queue.Dequeue();
 0200                pathTree.Get(pointer, out var current, out var previous);
 201
 0202                if (!settled.Add(current)) continue;
 0203                if (!enumerator.MoveTo(current)) continue;
 204
 0205                while (enumerator.MoveNext())
 0206                {
 0207                    var n = enumerator.Head;
 0208                    if (!enumerator.Forward) continue;
 209
 0210                    if (loop.Contains(n))
 0211                    {
 212                        // yay, a loop!
 0213                        loop.Add(current);
 0214                        while (previous != uint.MaxValue)
 0215                        {
 0216                            pathTree.Get(previous, out current, out previous);
 0217                            loop.Add(current);
 0218                        }
 0219                    }
 220
 0221                    if (settled.Contains(n)) continue;
 0222                    queue.Enqueue(pathTree.Add(n, pointer));
 0223                }
 0224            }
 225
 0226            if (loop.Count <= 1) return loopFound;
 227
 0228            label = this.Merge(loop);
 0229            loopFound = true;
 230
 0231            loop.Clear();
 0232            pathTree.Clear();
 0233            settled.Clear();
 0234            queue.Clear();
 0235        }
 0236    }
 237
 238    private uint Merge(HashSet<uint> labels)
 0239    {
 0240        while (true)
 0241        {
 242            // build a list of neighbours of the labels to be removed.
 0243            var edgeEnumerator = _labelGraph.GetEdgeEnumerator();
 0244            var bestLabel = uint.MaxValue;
 0245            var neighbours = new Dictionary<uint, (bool forward, bool backward)>();
 0246            foreach (var label in labels)
 0247            {
 0248                if (label < bestLabel) bestLabel = label;
 0249                if (!edgeEnumerator.MoveTo(label)) continue;
 250
 0251                while (edgeEnumerator.MoveNext())
 0252                {
 0253                    var n = edgeEnumerator.Head;
 0254                    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                }
 0265            }
 0266            if (bestLabel == uint.MaxValue) throw new Exception("Cannot merge empty loop");
 267
 268            // add all edges to the neighbours again.
 0269            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
 0282            var bestData = _islands[bestLabel];
 0283            foreach (var label in labels)
 0284            {
 0285                if (label == bestLabel) continue;
 0286                _labelGraph.RemoveVertex(label);
 287
 0288                var data = _islands[label];
 0289                if (bestData.size < uint.MaxValue) bestData.size += data.size;
 0290                _islands.Remove(label);
 0291            }
 292
 0293            _islands[bestLabel] = bestData;
 294
 0295            foreach (var k in _labels.Keys.ToArray())
 0296            {
 0297                var val = _labels[k];
 0298                if (val == bestLabel) continue;
 0299                if (!labels.Contains(val)) continue;
 300
 0301                _labels[k] = bestLabel;
 0302            }
 303
 0304            if (bestLabel == NotAnIslandLabel) return bestLabel;
 0305            if (_islands[bestLabel].size < _maxIslandSize)
 0306            {
 0307                return bestLabel;
 308            }
 309
 0310            labels = [bestLabel, NotAnIslandLabel];
 0311            continue;
 312        }
 0313    }
 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
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

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