< 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:181
Uncovered lines:40
Coverable lines:221
Total lines:337
Line coverage:81.9% (181 of 221)
Covered branches:58
Total branches:96
Branch coverage:60.4% (58 of 96)
Tag:224_14471318300

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
AddVertex()100%1100%
HasVertex(...)50%4100%
RemoveVertex(...)66.66%6100%
AddEdge(...)50%6100%
HasEdge(...)64.28%1483.33%
RemoveEdges(...)83.33%6100%
RemoveEdge(...)66.66%12100%
RemoveEdgeFromVertex1(...)37.5%1647.72%
RemoveEdgeFromVertex(...)75%1684.21%
HasEdge(...)50%2100%
GetEdgeEnumerator()100%1100%
get_VertexCount()100%10%
get_EdgeCount()100%10%
AddEdgeInternal(...)100%1100%
.ctor(...)100%1100%
MoveNext()75%894.44%
get_Tail()100%1100%
get_Head()100%1100%
get_Forward()100%1100%
MoveTo(...)50%4100%
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
 1311    private readonly List<uint> _vertices = new(); // Holds all vertices pointing to it's first edge.
 1312    private readonly List<(uint vertex1, uint vertex2, uint pointer1, uint pointer2)> _edges = new();
 13
 14    public uint AddVertex()
 4215    {
 4216        var vertex = (uint)_vertices.Count;
 4217        _vertices.Add(NoEdge);
 4218        return vertex;
 4219    }
 20
 21    public bool HasVertex(uint vertex)
 39922    {
 39923        if (vertex >= _vertices.Count) return false;
 39924        if (_vertices[(int)vertex] == NoVertex) return false;
 25
 39926        return true;
 39927    }
 28
 29    public bool RemoveVertex(uint vertex)
 2030    {
 2031        if (!this.HasVertex(vertex)) return false;
 32
 2033        this.RemoveEdges(vertex);
 34
 2035        _vertices[(int)vertex] = NoVertex;
 36
 4037        while (_vertices.Count > 0 &&
 4038            _vertices[^1] == NoVertex)
 2039        {
 2040            _vertices.RemoveAt(_vertices.Count - 1);
 2041        }
 42
 2043        return true;
 2044    }
 45
 46    public void AddEdge(uint vertex1, uint vertex2)
 3247    {
 3248        if (vertex1 == vertex2) { throw new ArgumentException("Given vertices must be different."); }
 3249        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 3250        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 51
 3252        this.AddEdgeInternal(vertex1, vertex2);
 3253    }
 54
 55    public bool HasEdge(uint vertex1, uint vertex2)
 3356    {
 3357        if (vertex1 == vertex2) { throw new ArgumentException("Given vertices must be different."); }
 3358        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 3359        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 60
 3361        var edgeId = _vertices[(int)vertex1];
 4862        while (edgeId != NoEdge)
 1663        {
 64            // get the edge.
 1665            var edge = _edges[(int)edgeId];
 1666            if (edge.vertex1 == vertex1)
 167            {
 168                if (edge.vertex2 == vertex2)
 169                {
 170                    return true;
 71                }
 072                edgeId = edge.pointer1;
 073            }
 1574            else if (edge.vertex2 == vertex1)
 1575            {
 1576                edgeId = edge.pointer2;
 1577            }
 78            else
 079            {
 080                throw new Exception("Edge found on vertex set that does not contain vertex");
 81            }
 1582        }
 83
 3284        return false;
 3385    }
 86
 87    public int RemoveEdges(uint vertex)
 2088    {
 2089        var removed = 0;
 2090        var edges = this.GetEdgeEnumerator();
 4991        while (edges.MoveTo(vertex) && edges.MoveNext())
 2992        {
 2993            if (edges.Forward)
 1494            {
 1495                this.RemoveEdge(vertex, edges.Head);
 1496            }
 97            else
 1598            {
 1599                this.RemoveEdge(edges.Head, vertex);
 15100            }
 29101            removed++;
 29102        }
 103
 20104        return removed;
 20105    }
 106
 107    public bool RemoveEdge(uint vertex1, uint vertex2)
 29108    {
 29109        if (vertex1 == vertex2) throw new ArgumentException("Given vertices must be different.");
 29110        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 29111        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 112
 29113        var edgeId = this.RemoveEdgeFromVertex1(vertex1, vertex2);
 29114        if (edgeId == NoEdge) return false;
 115
 29116        this.RemoveEdgeFromVertex(vertex2, edgeId);
 117
 29118        _edges[(int)edgeId] = (NoVertex, NoVertex, NoEdge, NoEdge);
 119
 58120        while (_edges.Count > 0 && _edges[^1].vertex1 == NoVertex)
 29121        {
 29122            _edges.RemoveAt(_edges.Count - 1);
 29123        }
 29124        return true;
 29125    }
 126
 127    private uint RemoveEdgeFromVertex1(uint vertex1, uint vertex2)
 29128    {
 129        // find the edge and keep the previous edge id.
 29130        var edgeId = _vertices[(int)vertex1];
 29131        var previousEdgeId = NoEdge;
 29132        var foundEdgeId = NoEdge;
 29133        while (edgeId != NoEdge)
 29134        {
 135            // get the edge.
 29136            var edge = _edges[(int)edgeId];
 29137            if (edge.vertex1 == vertex1)
 29138            {
 29139                if (edge.vertex2 == vertex2)
 29140                {
 29141                    foundEdgeId = edgeId;
 29142                    edgeId = edge.pointer1;
 29143                    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
 29159        if (foundEdgeId == NoEdge) return NoEdge;
 160
 161        // set pointer on last edge or vertex.
 29162        if (previousEdgeId == NoEdge)
 29163        {
 29164            _vertices[(int)vertex1] = edgeId;
 29165        }
 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
 29180        return foundEdgeId;
 29181    }
 182
 183    private void RemoveEdgeFromVertex(uint vertex, uint edgeIdToRemove)
 29184    {
 29185        if (edgeIdToRemove == NoEdge) throw new Exception("This edge has to exist, it existing in other vertex");
 186
 29187        var edgeId = _vertices[(int)vertex];
 29188        var previousEdgeId = NoEdge;
 30189        while (edgeId != NoEdge)
 30190        {
 191            // get the edge.
 30192            var edge = _edges[(int)edgeId];
 30193            var currentEdgeId = edgeId;
 194
 30195            if (edge.vertex1 == vertex)
 1196            {
 1197                edgeId = edge.pointer1;
 1198            }
 29199            else if (edge.vertex2 == vertex)
 29200            {
 29201                edgeId = edge.pointer2;
 29202            }
 203            else
 0204            {
 0205                throw new Exception("Edge found on vertex set that does not contain vertex");
 206            }
 207
 59208            if (currentEdgeId == edgeIdToRemove) break;
 1209            previousEdgeId = currentEdgeId;
 1210        }
 211
 29212        if (previousEdgeId == NoEdge)
 28213        {
 28214            _vertices[(int)vertex] = edgeId;
 28215        }
 216        else
 1217        {
 1218            var edge = _edges[(int)previousEdgeId];
 1219            if (edge.vertex1 == vertex)
 1220            {
 1221                edge.pointer1 = edgeId;
 1222            }
 0223            else if (edge.vertex2 == vertex)
 0224            {
 0225                edge.pointer2 = edgeId;
 0226            }
 1227            _edges[(int)previousEdgeId] = edge;
 1228        }
 29229    }
 230
 231    public bool HasEdge(uint vertex1)
 32232    {
 32233        var enumerator = this.GetEdgeEnumerator();
 32234        if (!enumerator.MoveTo(vertex1)) return false;
 235
 32236        return enumerator.MoveNext();
 32237    }
 238
 239    public EdgeEnumerator GetEdgeEnumerator()
 85240    {
 85241        return new EdgeEnumerator(this);
 85242    }
 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)
 32255    {
 256        // this adds an edge without checking for duplicates!
 32257        var vertex1EdgeId = _vertices[(int)vertex1];
 32258        var vertex2EdgeId = _vertices[(int)vertex2];
 259
 32260        var newEdgeId = (uint)_edges.Count;
 32261        _vertices[(int)vertex1] = newEdgeId;
 32262        _vertices[(int)vertex2] = newEdgeId;
 263
 32264        _edges.Add((vertex1, vertex2, vertex1EdgeId, vertex2EdgeId));
 265
 32266        return newEdgeId;
 32267    }
 268
 269    /// <summary>
 270    /// An edge enumerator.
 271    /// </summary>
 272    public class EdgeEnumerator
 273    {
 274        private readonly IslandLabelGraph _islandLabelGraph;
 85275        private uint _nextEdgeId = NoEdge;
 276
 277        /// <summary>
 278        /// Creates a new edge enumerator.
 279        /// </summary>
 85280        internal EdgeEnumerator(IslandLabelGraph islandLabelGraph)
 85281        {
 85282            _islandLabelGraph = islandLabelGraph;
 85283        }
 284
 285        /// <summary>
 286        /// Move to the next edge.
 287        /// </summary>
 288        /// <returns></returns>
 289        public bool MoveNext()
 279290        {
 279291            if (this.Tail == NoVertex) return false;
 399292            if (_nextEdgeId == NoEdge) return false;
 293
 159294            var edge = _islandLabelGraph._edges[(int)_nextEdgeId];
 159295            if (edge.vertex1 == this.Tail)
 86296            {
 86297                this.Head = edge.vertex2;
 86298                _nextEdgeId = edge.pointer1;
 86299                this.Forward = true;
 86300                return true;
 301            }
 73302            if (edge.vertex2 == this.Tail)
 73303            {
 73304                this.Head = edge.vertex1;
 73305                _nextEdgeId = edge.pointer2;
 73306                this.Forward = false;
 73307                return true;
 308            }
 309
 0310            throw new Exception("Next edge does not have vertex");
 279311        }
 312
 787313        public uint Tail { get; private set; } = NoVertex;
 314
 389315        public uint Head { get; private set; } = NoVertex;
 316
 331317        public bool Forward { get; private set; } = true;
 318
 319        public bool MoveTo(uint vertex)
 191320        {
 191321            if (!_islandLabelGraph.HasVertex(vertex)) return false;
 322
 191323            _nextEdgeId = _islandLabelGraph._vertices[(int)vertex];
 191324            if (_nextEdgeId == NoVertex) return false;
 325
 191326            this.Tail = vertex;
 191327            return true;
 191328        }
 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
04/15/2025 - 13:59:49
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()