< Summary

Class:Itinero.Network.Search.Islands.IslandLabelGraph
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Network/Search/Islands/IslandLabelGraph.cs
Covered lines:0
Uncovered lines:221
Coverable lines:221
Total lines:337
Line coverage:0% (0 of 221)
Covered branches:0
Total branches:96
Branch coverage:0% (0 of 96)
Tag:251_23667616543

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%10%
AddVertex()100%10%
HasVertex(...)0%40%
RemoveVertex(...)0%60%
AddEdge(...)0%60%
HasEdge(...)0%140%
RemoveEdges(...)0%60%
RemoveEdge(...)0%120%
RemoveEdgeFromVertex1(...)0%160%
RemoveEdgeFromVertex(...)0%160%
HasEdge(...)0%20%
GetEdgeEnumerator()100%10%
get_VertexCount()100%10%
get_EdgeCount()100%10%
AddEdgeInternal(...)100%10%
.ctor(...)100%10%
MoveNext()0%80%
get_Tail()100%10%
get_Head()100%10%
get_Forward()100%10%
MoveTo(...)0%40%
Reset()0%20%

File(s)

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

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3
 4namespace Itinero.Network.Search.Islands;
 5
 6internal class IslandLabelGraph
 7{
 8    private const uint NoEdge = uint.MaxValue;
 9    private const uint NoVertex = uint.MaxValue - 1;
 10
 011    private readonly List<uint> _vertices = new(); // Holds all vertices pointing to it's first edge.
 012    private readonly List<(uint vertex1, uint vertex2, uint pointer1, uint pointer2)> _edges = new();
 13
 14    public uint AddVertex()
 015    {
 016        var vertex = (uint)_vertices.Count;
 017        _vertices.Add(NoEdge);
 018        return vertex;
 019    }
 20
 21    public bool HasVertex(uint vertex)
 022    {
 023        if (vertex >= _vertices.Count) return false;
 024        if (_vertices[(int)vertex] == NoVertex) return false;
 25
 026        return true;
 027    }
 28
 29    public bool RemoveVertex(uint vertex)
 030    {
 031        if (!this.HasVertex(vertex)) return false;
 32
 033        this.RemoveEdges(vertex);
 34
 035        _vertices[(int)vertex] = NoVertex;
 36
 037        while (_vertices.Count > 0 &&
 038            _vertices[^1] == NoVertex)
 039        {
 040            _vertices.RemoveAt(_vertices.Count - 1);
 041        }
 42
 043        return true;
 044    }
 45
 46    public void AddEdge(uint vertex1, uint vertex2)
 047    {
 048        if (vertex1 == vertex2) { throw new ArgumentException("Given vertices must be different."); }
 049        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 050        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 51
 052        this.AddEdgeInternal(vertex1, vertex2);
 053    }
 54
 55    public bool HasEdge(uint vertex1, uint vertex2)
 056    {
 057        if (vertex1 == vertex2) { throw new ArgumentException("Given vertices must be different."); }
 058        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 059        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 60
 061        var edgeId = _vertices[(int)vertex1];
 062        while (edgeId != NoEdge)
 063        {
 64            // get the edge.
 065            var edge = _edges[(int)edgeId];
 066            if (edge.vertex1 == vertex1)
 067            {
 068                if (edge.vertex2 == vertex2)
 069                {
 070                    return true;
 71                }
 072                edgeId = edge.pointer1;
 073            }
 074            else if (edge.vertex2 == vertex1)
 075            {
 076                edgeId = edge.pointer2;
 077            }
 78            else
 079            {
 080                throw new Exception("Edge found on vertex set that does not contain vertex");
 81            }
 082        }
 83
 084        return false;
 085    }
 86
 87    public int RemoveEdges(uint vertex)
 088    {
 089        var removed = 0;
 090        var edges = this.GetEdgeEnumerator();
 091        while (edges.MoveTo(vertex) && edges.MoveNext())
 092        {
 093            if (edges.Forward)
 094            {
 095                this.RemoveEdge(vertex, edges.Head);
 096            }
 97            else
 098            {
 099                this.RemoveEdge(edges.Head, vertex);
 0100            }
 0101            removed++;
 0102        }
 103
 0104        return removed;
 0105    }
 106
 107    public bool RemoveEdge(uint vertex1, uint vertex2)
 0108    {
 0109        if (vertex1 == vertex2) throw new ArgumentException("Given vertices must be different.");
 0110        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 0111        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 112
 0113        var edgeId = this.RemoveEdgeFromVertex1(vertex1, vertex2);
 0114        if (edgeId == NoEdge) return false;
 115
 0116        this.RemoveEdgeFromVertex(vertex2, edgeId);
 117
 0118        _edges[(int)edgeId] = (NoVertex, NoVertex, NoEdge, NoEdge);
 119
 0120        while (_edges.Count > 0 && _edges[^1].vertex1 == NoVertex)
 0121        {
 0122            _edges.RemoveAt(_edges.Count - 1);
 0123        }
 0124        return true;
 0125    }
 126
 127    private uint RemoveEdgeFromVertex1(uint vertex1, uint vertex2)
 0128    {
 129        // find the edge and keep the previous edge id.
 0130        var edgeId = _vertices[(int)vertex1];
 0131        var previousEdgeId = NoEdge;
 0132        var foundEdgeId = NoEdge;
 0133        while (edgeId != NoEdge)
 0134        {
 135            // get the edge.
 0136            var edge = _edges[(int)edgeId];
 0137            if (edge.vertex1 == vertex1)
 0138            {
 0139                if (edge.vertex2 == vertex2)
 0140                {
 0141                    foundEdgeId = edgeId;
 0142                    edgeId = edge.pointer1;
 0143                    break;
 144                }
 0145                previousEdgeId = edgeId;
 0146                edgeId = edge.pointer1;
 0147            }
 0148            else if (edge.vertex2 == vertex1)
 0149            {
 0150                previousEdgeId = edgeId;
 0151                edgeId = edge.pointer2;
 0152            }
 153            else
 0154            {
 0155                throw new Exception("Edge found on vertex set that does not contain vertex");
 156            }
 0157        }
 158
 0159        if (foundEdgeId == NoEdge) return NoEdge;
 160
 161        // set pointer on last edge or vertex.
 0162        if (previousEdgeId == NoEdge)
 0163        {
 0164            _vertices[(int)vertex1] = edgeId;
 0165        }
 166        else
 0167        {
 0168            var edge = _edges[(int)previousEdgeId];
 0169            if (edge.vertex1 == vertex1)
 0170            {
 0171                edge.pointer1 = edgeId;
 0172            }
 0173            else if (edge.vertex2 == vertex1)
 0174            {
 0175                edge.pointer2 = edgeId;
 0176            }
 0177            _edges[(int)previousEdgeId] = edge;
 0178        }
 179
 0180        return foundEdgeId;
 0181    }
 182
 183    private void RemoveEdgeFromVertex(uint vertex, uint edgeIdToRemove)
 0184    {
 0185        if (edgeIdToRemove == NoEdge) throw new Exception("This edge has to exist, it existing in other vertex");
 186
 0187        var edgeId = _vertices[(int)vertex];
 0188        var previousEdgeId = NoEdge;
 0189        while (edgeId != NoEdge)
 0190        {
 191            // get the edge.
 0192            var edge = _edges[(int)edgeId];
 0193            var currentEdgeId = edgeId;
 194
 0195            if (edge.vertex1 == vertex)
 0196            {
 0197                edgeId = edge.pointer1;
 0198            }
 0199            else if (edge.vertex2 == vertex)
 0200            {
 0201                edgeId = edge.pointer2;
 0202            }
 203            else
 0204            {
 0205                throw new Exception("Edge found on vertex set that does not contain vertex");
 206            }
 207
 0208            if (currentEdgeId == edgeIdToRemove) break;
 0209            previousEdgeId = currentEdgeId;
 0210        }
 211
 0212        if (previousEdgeId == NoEdge)
 0213        {
 0214            _vertices[(int)vertex] = edgeId;
 0215        }
 216        else
 0217        {
 0218            var edge = _edges[(int)previousEdgeId];
 0219            if (edge.vertex1 == vertex)
 0220            {
 0221                edge.pointer1 = edgeId;
 0222            }
 0223            else if (edge.vertex2 == vertex)
 0224            {
 0225                edge.pointer2 = edgeId;
 0226            }
 0227            _edges[(int)previousEdgeId] = edge;
 0228        }
 0229    }
 230
 231    public bool HasEdge(uint vertex1)
 0232    {
 0233        var enumerator = this.GetEdgeEnumerator();
 0234        if (!enumerator.MoveTo(vertex1)) return false;
 235
 0236        return enumerator.MoveNext();
 0237    }
 238
 239    public EdgeEnumerator GetEdgeEnumerator()
 0240    {
 0241        return new EdgeEnumerator(this);
 0242    }
 243
 244    /// <summary>
 245    /// Returns the number of vertices in this graph.
 246    /// </summary>
 0247    public int VertexCount => _vertices.Count;
 248
 249    /// <summary>
 250    /// Returns the number of edges in this graph.
 251    /// </summary>
 0252    public long EdgeCount => _edges.Count;
 253
 254    private uint AddEdgeInternal(uint vertex1, uint vertex2)
 0255    {
 256        // this adds an edge without checking for duplicates!
 0257        var vertex1EdgeId = _vertices[(int)vertex1];
 0258        var vertex2EdgeId = _vertices[(int)vertex2];
 259
 0260        var newEdgeId = (uint)_edges.Count;
 0261        _vertices[(int)vertex1] = newEdgeId;
 0262        _vertices[(int)vertex2] = newEdgeId;
 263
 0264        _edges.Add((vertex1, vertex2, vertex1EdgeId, vertex2EdgeId));
 265
 0266        return newEdgeId;
 0267    }
 268
 269    /// <summary>
 270    /// An edge enumerator.
 271    /// </summary>
 272    public class EdgeEnumerator
 273    {
 274        private readonly IslandLabelGraph _islandLabelGraph;
 0275        private uint _nextEdgeId = NoEdge;
 276
 277        /// <summary>
 278        /// Creates a new edge enumerator.
 279        /// </summary>
 0280        internal EdgeEnumerator(IslandLabelGraph islandLabelGraph)
 0281        {
 0282            _islandLabelGraph = islandLabelGraph;
 0283        }
 284
 285        /// <summary>
 286        /// Move to the next edge.
 287        /// </summary>
 288        /// <returns></returns>
 289        public bool MoveNext()
 0290        {
 0291            if (this.Tail == NoVertex) return false;
 0292            if (_nextEdgeId == NoEdge) return false;
 293
 0294            var edge = _islandLabelGraph._edges[(int)_nextEdgeId];
 0295            if (edge.vertex1 == this.Tail)
 0296            {
 0297                this.Head = edge.vertex2;
 0298                _nextEdgeId = edge.pointer1;
 0299                this.Forward = true;
 0300                return true;
 301            }
 0302            if (edge.vertex2 == this.Tail)
 0303            {
 0304                this.Head = edge.vertex1;
 0305                _nextEdgeId = edge.pointer2;
 0306                this.Forward = false;
 0307                return true;
 308            }
 309
 0310            throw new Exception("Next edge does not have vertex");
 0311        }
 312
 0313        public uint Tail { get; private set; } = NoVertex;
 314
 0315        public uint Head { get; private set; } = NoVertex;
 316
 0317        public bool Forward { get; private set; } = true;
 318
 319        public bool MoveTo(uint vertex)
 0320        {
 0321            if (!_islandLabelGraph.HasVertex(vertex)) return false;
 322
 0323            _nextEdgeId = _islandLabelGraph._vertices[(int)vertex];
 0324            if (_nextEdgeId == NoVertex) return false;
 325
 0326            this.Tail = vertex;
 0327            return true;
 0328        }
 329
 330        public void Reset()
 0331        {
 0332            if (this.Tail == NoVertex) return;
 333
 0334            this.MoveTo(this.Tail);
 0335        }
 336    }
 337}
Generated by: ReportGenerator 4.8.2.0
03/27/2026 - 21:11:43
GitHub | www.palmmedia.de

Methods/Properties

.ctor()
AddVertex()
HasVertex(...)
RemoveVertex(...)
AddEdge(...)
HasEdge(...)
RemoveEdges(...)
RemoveEdge(...)
RemoveEdgeFromVertex1(...)
RemoveEdgeFromVertex(...)
HasEdge(...)
GetEdgeEnumerator()
get_VertexCount()
get_EdgeCount()
AddEdgeInternal(...)
.ctor(...)
MoveNext()
get_Tail()
get_Head()
get_Forward()
MoveTo(...)
Reset()