/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 | | |