Coverage Report

Created: 2026-10-31 06:44

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/geos/src/planargraph/PlanarGraph.cpp
Line
Count
Source
1
/**********************************************************************
2
 *
3
 * GEOS - Geometry Engine Open Source
4
 * http://geos.osgeo.org
5
 *
6
 * Copyright (C) 2005-2006 Refractions Research Inc.
7
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
8
 *
9
 * This is free software; you can redistribute and/or modify it under
10
 * the terms of the GNU Lesser General Licence as published
11
 * by the Free Software Foundation.
12
 * See the COPYING file for more information.
13
 *
14
 **********************************************************************
15
 *
16
 * Last port: planargraph/PlanarGraph.java rev. 107/138 (JTS-1.10)
17
 *
18
 **********************************************************************/
19
20
#include <geos/planargraph/PlanarGraph.h>
21
#include <geos/planargraph/Edge.h>
22
#include <geos/planargraph/NodeMap.h>
23
#include <geos/planargraph/Node.h>
24
#include <geos/planargraph/DirectedEdge.h>
25
26
#include <vector>
27
#include <map>
28
29
30
31
namespace geos {
32
namespace planargraph {
33
34
35
/*
36
 * Adds the Edge and its DirectedEdges with this PlanarGraph.
37
 * Assumes that the Edge has already been created with its associated
38
 * DirectEdges.
39
 * Only subclasses can add Edges, to ensure the edges added are of
40
 * the right class.
41
 */
42
void
43
PlanarGraph::add(Edge* edge)
44
0
{
45
0
    edges.push_back(edge);
46
0
    add(edge->getDirEdge(0));
47
0
    add(edge->getDirEdge(1));
48
0
}
49
50
51
/*
52
 * Removes an Edge and its associated DirectedEdges from their from-Nodes and
53
 * from this PlanarGraph. Note: This method does not remove the Nodes associated
54
 * with the Edge, even if the removal of the Edge reduces the degree of a
55
 * Node to zero.
56
 */
57
void
58
PlanarGraph::remove(Edge* edge)
59
0
{
60
0
    remove(edge->getDirEdge(0));
61
0
    remove(edge->getDirEdge(1));
62
0
    for(unsigned int i = 0; i < edges.size(); ++i) {
63
0
        if(edges[i] == edge) {
64
0
            edges.erase(std::next(edges.begin(), static_cast<int>(i)));
65
0
            --i;
66
0
        }
67
0
    }
68
0
}
69
70
/*
71
 * Removes DirectedEdge from its from-Node and from this PlanarGraph. Note:
72
 * This method does not remove the Nodes associated with the DirectedEdge,
73
 * even if the removal of the DirectedEdge reduces the degree of a Node to
74
 * zero.
75
 */
76
void
77
PlanarGraph::remove(DirectedEdge* de)
78
0
{
79
0
    DirectedEdge* sym = de->getSym();
80
0
    if(sym != nullptr) {
81
0
        sym->setSym(nullptr);
82
0
    }
83
0
    de->getFromNode()->getOutEdges()->remove(de);
84
0
    for(unsigned int i = 0; i < dirEdges.size(); ++i) {
85
0
        if(dirEdges[i] == de) {
86
0
            dirEdges.erase(std::next(dirEdges.begin(), static_cast<int>(i)));
87
0
            --i;
88
0
        }
89
0
    }
90
0
}
91
92
/*
93
 * Removes a node from the graph, along with any associated
94
 * DirectedEdges and Edges.
95
 */
96
void
97
PlanarGraph::remove(Node* node)
98
0
{
99
    // unhook all directed edges
100
0
    std::vector<DirectedEdge*>& outEdges = node->getOutEdges()->getEdges();
101
0
    for(unsigned int i = 0; i < outEdges.size(); ++i) {
102
0
        DirectedEdge* de = outEdges[i];
103
0
        DirectedEdge* sym = de->getSym();
104
        // remove the diredge that points to this node
105
0
        if(sym != nullptr) {
106
0
            remove(sym);
107
0
        }
108
        // remove this diredge from the graph collection
109
0
        for(unsigned int j = 0; j < dirEdges.size(); ++j) {
110
0
            if(dirEdges[j] == de) {
111
0
                dirEdges.erase(std::next(dirEdges.begin(), static_cast<int>(j)));
112
0
                --j;
113
0
            }
114
0
        }
115
0
        Edge* edge = de->getEdge();
116
0
        if(edge != nullptr) {
117
0
            for(unsigned int k = 0; k < edges.size(); ++k) {
118
0
                if(edges[k] == edge) {
119
0
                    edges.erase(std::next(edges.begin(), static_cast<int>(k)));
120
0
                    --k;
121
0
                }
122
0
            }
123
0
        }
124
0
    }
125
    // remove the node from the graph
126
0
    nodeMap.remove(node->getCoordinate());
127
    //nodes.remove(node);
128
0
}
129
130
/*public*/
131
std::vector<Node*>*
132
PlanarGraph::findNodesOfDegree(std::size_t degree)
133
0
{
134
0
    std::vector<Node*>* nodesFound = new std::vector<Node*>();
135
0
    findNodesOfDegree(degree, *nodesFound);
136
0
    return nodesFound;
137
0
}
138
139
/*public*/
140
void
141
PlanarGraph::findNodesOfDegree(std::size_t degree, std::vector<Node*>& nodesFound)
142
0
{
143
0
    NodeMap::container& nm = nodeMap.getNodeMap();
144
0
    for(NodeMap::container::iterator it = nm.begin(), itEnd = nm.end();
145
0
            it != itEnd; ++it) {
146
0
        Node* node = it->second;
147
0
        if(node->getDegree() == degree) {
148
0
            nodesFound.push_back(node);
149
0
        }
150
0
    }
151
0
}
152
153
} // namespace planargraph
154
} // namespace geos
155