< 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:183
Uncovered lines:38
Coverable lines:221
Total lines:337
Line coverage:82.8% (183 of 221)
Covered branches:59
Total branches:96
Branch coverage:61.4% (59 of 96)
Tag:236_17851749384

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
AddVertex()100%1100%
HasVertex(...)50%4100%
RemoveVertex(...)66.66%6100%
AddEdge(...)50%6100%
HasEdge(...)71.42%1491.66%
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)
 33722    {
 33723        if (vertex >= _vertices.Count) return false;
 33724        if (_vertices[(int)vertex] == NoVertex) return false;
 25
 33726        return true;
 33727    }
 28
 29    public bool RemoveVertex(uint vertex)
 1730    {
 1731        if (!this.HasVertex(vertex)) return false;
 32
 1733        this.RemoveEdges(vertex);
 34
 1735        _vertices[(int)vertex] = NoVertex;
 36
 3437        while (_vertices.Count > 0 &&
 3438            _vertices[^1] == NoVertex)
 1739        {
 1740            _vertices.RemoveAt(_vertices.Count - 1);
 1741        }
 42
 1743        return true;
 1744    }
 45
 46    public void AddEdge(uint vertex1, uint vertex2)
 2947    {
 2948        if (vertex1 == vertex2) { throw new ArgumentException("Given vertices must be different."); }
 2949        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 2950        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 51
 2952        this.AddEdgeInternal(vertex1, vertex2);
 2953    }
 54
 55    public bool HasEdge(uint vertex1, uint vertex2)
 3256    {
 3257        if (vertex1 == vertex2) { throw new ArgumentException("Given vertices must be different."); }
 3258        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 3259        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 60
 3261        var edgeId = _vertices[(int)vertex1];
 4862        while (edgeId != NoEdge)
 1963        {
 64            // get the edge.
 1965            var edge = _edges[(int)edgeId];
 1966            if (edge.vertex1 == vertex1)
 467            {
 468                if (edge.vertex2 == vertex2)
 369                {
 370                    return true;
 71                }
 172                edgeId = edge.pointer1;
 173            }
 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            }
 1682        }
 83
 2984        return false;
 3285    }
 86
 87    public int RemoveEdges(uint vertex)
 1788    {
 1789        var removed = 0;
 1790        var edges = this.GetEdgeEnumerator();
 3991        while (edges.MoveTo(vertex) && edges.MoveNext())
 2292        {
 2293            if (edges.Forward)
 1094            {
 1095                this.RemoveEdge(vertex, edges.Head);
 1096            }
 97            else
 1298            {
 1299                this.RemoveEdge(edges.Head, vertex);
 12100            }
 22101            removed++;
 22102        }
 103
 17104        return removed;
 17105    }
 106
 107    public bool RemoveEdge(uint vertex1, uint vertex2)
 22108    {
 22109        if (vertex1 == vertex2) throw new ArgumentException("Given vertices must be different.");
 22110        if (!this.HasVertex(vertex1)) throw new ArgumentException($"Vertex {vertex1} does not exist.");
 22111        if (!this.HasVertex(vertex2)) throw new ArgumentException($"Vertex {vertex2} does not exist.");
 112
 22113        var edgeId = this.RemoveEdgeFromVertex1(vertex1, vertex2);
 22114        if (edgeId == NoEdge) return false;
 115
 22116        this.RemoveEdgeFromVertex(vertex2, edgeId);
 117
 22118        _edges[(int)edgeId] = (NoVertex, NoVertex, NoEdge, NoEdge);
 119
 44120        while (_edges.Count > 0 && _edges[^1].vertex1 == NoVertex)
 22121        {
 22122            _edges.RemoveAt(_edges.Count - 1);
 22123        }
 22124        return true;
 22125    }
 126
 127    private uint RemoveEdgeFromVertex1(uint vertex1, uint vertex2)
 22128    {
 129        // find the edge and keep the previous edge id.
 22130        var edgeId = _vertices[(int)vertex1];
 22131        var previousEdgeId = NoEdge;
 22132        var foundEdgeId = NoEdge;
 22133        while (edgeId != NoEdge)
 22134        {
 135            // get the edge.
 22136            var edge = _edges[(int)edgeId];
 22137            if (edge.vertex1 == vertex1)
 22138            {
 22139                if (edge.vertex2 == vertex2)
 22140                {
 22141                    foundEdgeId = edgeId;
 22142                    edgeId = edge.pointer1;
 22143                    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
 22159        if (foundEdgeId == NoEdge) return NoEdge;
 160
 161        // set pointer on last edge or vertex.
 22162        if (previousEdgeId == NoEdge)
 22163        {
 22164            _vertices[(int)vertex1] = edgeId;
 22165        }
 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
 22180        return foundEdgeId;
 22181    }
 182
 183    private void RemoveEdgeFromVertex(uint vertex, uint edgeIdToRemove)
 22184    {
 22185        if (edgeIdToRemove == NoEdge) throw new Exception("This edge has to exist, it existing in other vertex");
 186
 22187        var edgeId = _vertices[(int)vertex];
 22188        var previousEdgeId = NoEdge;
 24189        while (edgeId != NoEdge)
 24190        {
 191            // get the edge.
 24192            var edge = _edges[(int)edgeId];
 24193            var currentEdgeId = edgeId;
 194
 24195            if (edge.vertex1 == vertex)
 2196            {
 2197                edgeId = edge.pointer1;
 2198            }
 22199            else if (edge.vertex2 == vertex)
 22200            {
 22201                edgeId = edge.pointer2;
 22202            }
 203            else
 0204            {
 0205                throw new Exception("Edge found on vertex set that does not contain vertex");
 206            }
 207
 46208            if (currentEdgeId == edgeIdToRemove) break;
 2209            previousEdgeId = currentEdgeId;
 2210        }
 211
 22212        if (previousEdgeId == NoEdge)
 20213        {
 20214            _vertices[(int)vertex] = edgeId;
 20215        }
 216        else
 2217        {
 2218            var edge = _edges[(int)previousEdgeId];
 2219            if (edge.vertex1 == vertex)
 2220            {
 2221                edge.pointer1 = edgeId;
 2222            }
 0223            else if (edge.vertex2 == vertex)
 0224            {
 0225                edge.pointer2 = edgeId;
 0226            }
 2227            _edges[(int)previousEdgeId] = edge;
 2228        }
 22229    }
 230
 231    public bool HasEdge(uint vertex1)
 29232    {
 29233        var enumerator = this.GetEdgeEnumerator();
 29234        if (!enumerator.MoveTo(vertex1)) return false;
 235
 29236        return enumerator.MoveNext();
 29237    }
 238
 239    public EdgeEnumerator GetEdgeEnumerator()
 72240    {
 72241        return new EdgeEnumerator(this);
 72242    }
 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)
 29255    {
 256        // this adds an edge without checking for duplicates!
 29257        var vertex1EdgeId = _vertices[(int)vertex1];
 29258        var vertex2EdgeId = _vertices[(int)vertex2];
 259
 29260        var newEdgeId = (uint)_edges.Count;
 29261        _vertices[(int)vertex1] = newEdgeId;
 29262        _vertices[(int)vertex2] = newEdgeId;
 263
 29264        _edges.Add((vertex1, vertex2, vertex1EdgeId, vertex2EdgeId));
 265
 29266        return newEdgeId;
 29267    }
 268
 269    /// <summary>
 270    /// An edge enumerator.
 271    /// </summary>
 272    public class EdgeEnumerator
 273    {
 274        private readonly IslandLabelGraph _islandLabelGraph;
 72275        private uint _nextEdgeId = NoEdge;
 276
 277        /// <summary>
 278        /// Creates a new edge enumerator.
 279        /// </summary>
 72280        internal EdgeEnumerator(IslandLabelGraph islandLabelGraph)
 72281        {
 72282            _islandLabelGraph = islandLabelGraph;
 72283        }
 284
 285        /// <summary>
 286        /// Move to the next edge.
 287        /// </summary>
 288        /// <returns></returns>
 289        public bool MoveNext()
 223290        {
 223291            if (this.Tail == NoVertex) return false;
 323292            if (_nextEdgeId == NoEdge) return false;
 293
 123294            var edge = _islandLabelGraph._edges[(int)_nextEdgeId];
 123295            if (edge.vertex1 == this.Tail)
 64296            {
 64297                this.Head = edge.vertex2;
 64298                _nextEdgeId = edge.pointer1;
 64299                this.Forward = true;
 64300                return true;
 301            }
 59302            if (edge.vertex2 == this.Tail)
 59303            {
 59304                this.Head = edge.vertex1;
 59305                _nextEdgeId = edge.pointer2;
 59306                this.Forward = false;
 59307                return true;
 308            }
 309
 0310            throw new Exception("Next edge does not have vertex");
 223311        }
 312
 631313        public uint Tail { get; private set; } = NoVertex;
 314
 307315        public uint Head { get; private set; } = NoVertex;
 316
 263317        public bool Forward { get; private set; } = true;
 318
 319        public bool MoveTo(uint vertex)
 154320        {
 154321            if (!_islandLabelGraph.HasVertex(vertex)) return false;
 322
 154323            _nextEdgeId = _islandLabelGraph._vertices[(int)vertex];
 154324            if (_nextEdgeId == NoVertex) return false;
 325
 154326            this.Tail = vertex;
 154327            return true;
 154328        }
 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
09/19/2025 - 07:34:11
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()