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