0
3
0
... | ... |
@@ -149,12 +149,22 @@ |
149 | 149 |
static int id(Node v) { return v.id; } |
150 | 150 |
static int id(Arc e) { return e.id; } |
151 | 151 |
|
152 | 152 |
static Node nodeFromId(int id) { return Node(id);} |
153 | 153 |
static Arc arcFromId(int id) { return Arc(id);} |
154 | 154 |
|
155 |
bool valid(Node n) const { |
|
156 |
return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && |
|
157 |
nodes[n.id].prev != -2; |
|
158 |
} |
|
159 |
|
|
160 |
bool valid(Arc a) const { |
|
161 |
return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && |
|
162 |
arcs[a.id].prev_in != -2; |
|
163 |
} |
|
164 |
|
|
155 | 165 |
Node addNode() { |
156 | 166 |
int n; |
157 | 167 |
|
158 | 168 |
if(first_free_node==-1) { |
159 | 169 |
n = nodes.size(); |
160 | 170 |
nodes.push_back(NodeT()); |
... | ... |
@@ -216,12 +226,13 @@ |
216 | 226 |
} else { |
217 | 227 |
first_node = nodes[n].next; |
218 | 228 |
} |
219 | 229 |
|
220 | 230 |
nodes[n].next = first_free_node; |
221 | 231 |
first_free_node = n; |
232 |
nodes[n].prev = -2; |
|
222 | 233 |
|
223 | 234 |
} |
224 | 235 |
|
225 | 236 |
void erase(const Arc& arc) { |
226 | 237 |
int n = arc.id; |
227 | 238 |
|
... | ... |
@@ -245,13 +256,13 @@ |
245 | 256 |
} else { |
246 | 257 |
nodes[arcs[n].source].first_out = arcs[n].next_out; |
247 | 258 |
} |
248 | 259 |
|
249 | 260 |
arcs[n].next_in = first_free_arc; |
250 | 261 |
first_free_arc = n; |
251 |
|
|
262 |
arcs[n].prev_in = -2; |
|
252 | 263 |
} |
253 | 264 |
|
254 | 265 |
void clear() { |
255 | 266 |
arcs.clear(); |
256 | 267 |
nodes.clear(); |
257 | 268 |
first_node = first_free_node = first_free_arc = -1; |
... | ... |
@@ -347,12 +358,32 @@ |
347 | 358 |
///and target node \c t. |
348 | 359 |
///\return the new arc. |
349 | 360 |
Arc addArc(const Node& s, const Node& t) { |
350 | 361 |
return Parent::addArc(s, t); |
351 | 362 |
} |
352 | 363 |
|
364 |
/// Node validity check |
|
365 |
|
|
366 |
/// This function gives back true if the given node is valid, |
|
367 |
/// ie. it is a real node of the graph. |
|
368 |
/// |
|
369 |
/// \warning A Node pointing to a removed item |
|
370 |
/// could become valid again later if new nodes are |
|
371 |
/// added to the graph. |
|
372 |
bool valid(Node n) const { return Parent::valid(n); } |
|
373 |
|
|
374 |
/// Arc validity check |
|
375 |
|
|
376 |
/// This function gives back true if the given arc is valid, |
|
377 |
/// ie. it is a real arc of the graph. |
|
378 |
/// |
|
379 |
/// \warning An Arc pointing to a removed item |
|
380 |
/// could become valid again later if new nodes are |
|
381 |
/// added to the graph. |
|
382 |
bool valid(Arc a) const { return Parent::valid(a); } |
|
383 |
|
|
353 | 384 |
/// Change the target of \c e to \c n |
354 | 385 |
|
355 | 386 |
/// Change the target of \c e to \c n |
356 | 387 |
/// |
357 | 388 |
///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing |
358 | 389 |
///the changed arc remain valid. However <tt>InArcIt</tt>s are |
... | ... |
@@ -942,12 +973,27 @@ |
942 | 973 |
static int id(Edge e) { return e.id; } |
943 | 974 |
|
944 | 975 |
static Node nodeFromId(int id) { return Node(id);} |
945 | 976 |
static Arc arcFromId(int id) { return Arc(id);} |
946 | 977 |
static Edge edgeFromId(int id) { return Edge(id);} |
947 | 978 |
|
979 |
bool valid(Node n) const { |
|
980 |
return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && |
|
981 |
nodes[n.id].prev != -2; |
|
982 |
} |
|
983 |
|
|
984 |
bool valid(Arc a) const { |
|
985 |
return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && |
|
986 |
arcs[a.id].prev_out != -2; |
|
987 |
} |
|
988 |
|
|
989 |
bool valid(Edge e) const { |
|
990 |
return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && |
|
991 |
arcs[2 * e.id].prev_out != -2; |
|
992 |
} |
|
993 |
|
|
948 | 994 |
Node addNode() { |
949 | 995 |
int n; |
950 | 996 |
|
951 | 997 |
if(first_free_node==-1) { |
952 | 998 |
n = nodes.size(); |
953 | 999 |
nodes.push_back(NodeT()); |
... | ... |
@@ -1010,13 +1056,13 @@ |
1010 | 1056 |
} else { |
1011 | 1057 |
first_node = nodes[n].next; |
1012 | 1058 |
} |
1013 | 1059 |
|
1014 | 1060 |
nodes[n].next = first_free_node; |
1015 | 1061 |
first_free_node = n; |
1016 |
|
|
1062 |
nodes[n].prev = -2; |
|
1017 | 1063 |
} |
1018 | 1064 |
|
1019 | 1065 |
void erase(const Edge& edge) { |
1020 | 1066 |
int n = edge.id * 2; |
1021 | 1067 |
|
1022 | 1068 |
if (arcs[n].next_out != -1) { |
... | ... |
@@ -1038,12 +1084,14 @@ |
1038 | 1084 |
} else { |
1039 | 1085 |
nodes[arcs[n].target].first_out = arcs[n | 1].next_out; |
1040 | 1086 |
} |
1041 | 1087 |
|
1042 | 1088 |
arcs[n].next_out = first_free_arc; |
1043 | 1089 |
first_free_arc = n; |
1090 |
arcs[n].prev_out = -2; |
|
1091 |
arcs[n | 1].prev_out = -2; |
|
1044 | 1092 |
|
1045 | 1093 |
} |
1046 | 1094 |
|
1047 | 1095 |
void clear() { |
1048 | 1096 |
arcs.clear(); |
1049 | 1097 |
nodes.clear(); |
... | ... |
@@ -1154,12 +1202,39 @@ |
1154 | 1202 |
/// Add a new edge to the graph with source node \c s |
1155 | 1203 |
/// and target node \c t. |
1156 | 1204 |
/// \return the new edge. |
1157 | 1205 |
Edge addEdge(const Node& s, const Node& t) { |
1158 | 1206 |
return Parent::addEdge(s, t); |
1159 | 1207 |
} |
1208 |
/// Node validity check |
|
1209 |
|
|
1210 |
/// This function gives back true if the given node is valid, |
|
1211 |
/// ie. it is a real node of the graph. |
|
1212 |
/// |
|
1213 |
/// \warning A Node pointing to a removed item |
|
1214 |
/// could become valid again later if new nodes are |
|
1215 |
/// added to the graph. |
|
1216 |
bool valid(Node n) const { return Parent::valid(n); } |
|
1217 |
/// Arc validity check |
|
1218 |
|
|
1219 |
/// This function gives back true if the given arc is valid, |
|
1220 |
/// ie. it is a real arc of the graph. |
|
1221 |
/// |
|
1222 |
/// \warning An Arc pointing to a removed item |
|
1223 |
/// could become valid again later if new edges are |
|
1224 |
/// added to the graph. |
|
1225 |
bool valid(Arc a) const { return Parent::valid(a); } |
|
1226 |
/// Edge validity check |
|
1227 |
|
|
1228 |
/// This function gives back true if the given edge is valid, |
|
1229 |
/// ie. it is a real arc of the graph. |
|
1230 |
/// |
|
1231 |
/// \warning A Edge pointing to a removed item |
|
1232 |
/// could become valid again later if new edges are |
|
1233 |
/// added to the graph. |
|
1234 |
bool valid(Edge e) const { return Parent::valid(e); } |
|
1160 | 1235 |
/// \brief Change the source of \c e to \c n |
1161 | 1236 |
/// |
1162 | 1237 |
/// This function changes the source of \c e to \c n. |
1163 | 1238 |
/// |
1164 | 1239 |
///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
1165 | 1240 |
///referencing the changed arc remain |
... | ... |
@@ -112,12 +112,19 @@ |
112 | 112 |
static int id(Node v) { return v._id; } |
113 | 113 |
static int id(Arc a) { return a._id; } |
114 | 114 |
|
115 | 115 |
static Node nodeFromId(int id) { return Node(id);} |
116 | 116 |
static Arc arcFromId(int id) { return Arc(id);} |
117 | 117 |
|
118 |
bool valid(Node n) const { |
|
119 |
return n._id >= 0 && n._id < static_cast<int>(nodes.size()); |
|
120 |
} |
|
121 |
bool valid(Arc a) const { |
|
122 |
return a._id >= 0 && a._id < static_cast<int>(arcs.size()); |
|
123 |
} |
|
124 |
|
|
118 | 125 |
class Node { |
119 | 126 |
friend class SmartDigraphBase; |
120 | 127 |
friend class SmartDigraph; |
121 | 128 |
|
122 | 129 |
protected: |
123 | 130 |
int _id; |
... | ... |
@@ -258,12 +265,30 @@ |
258 | 265 |
/// be very large (e.g. it will contain millions of nodes and/or arcs) |
259 | 266 |
/// then it is worth reserving space for this amount before starting |
260 | 267 |
/// to build the digraph. |
261 | 268 |
/// \sa reserveNode |
262 | 269 |
void reserveArc(int m) { arcs.reserve(m); }; |
263 | 270 |
|
271 |
/// \brief Node validity check |
|
272 |
/// |
|
273 |
/// This function gives back true if the given node is valid, |
|
274 |
/// ie. it is a real node of the graph. |
|
275 |
/// |
|
276 |
/// \warning A removed node (using Snapshot) could become valid again |
|
277 |
/// when new nodes are added to the graph. |
|
278 |
bool valid(Node n) const { return Parent::valid(n); } |
|
279 |
|
|
280 |
/// \brief Arc validity check |
|
281 |
/// |
|
282 |
/// This function gives back true if the given arc is valid, |
|
283 |
/// ie. it is a real arc of the graph. |
|
284 |
/// |
|
285 |
/// \warning A removed arc (using Snapshot) could become valid again |
|
286 |
/// when new arcs are added to the graph. |
|
287 |
bool valid(Arc a) const { return Parent::valid(a); } |
|
288 |
|
|
264 | 289 |
///Clear the digraph. |
265 | 290 |
|
266 | 291 |
///Erase all the nodes and arcs from the digraph. |
267 | 292 |
/// |
268 | 293 |
void clear() { |
269 | 294 |
Parent::clear(); |
... | ... |
@@ -547,12 +572,22 @@ |
547 | 572 |
static int id(Edge e) { return e._id; } |
548 | 573 |
|
549 | 574 |
static Node nodeFromId(int id) { return Node(id);} |
550 | 575 |
static Arc arcFromId(int id) { return Arc(id);} |
551 | 576 |
static Edge edgeFromId(int id) { return Edge(id);} |
552 | 577 |
|
578 |
bool valid(Node n) const { |
|
579 |
return n._id >= 0 && n._id < static_cast<int>(nodes.size()); |
|
580 |
} |
|
581 |
bool valid(Arc a) const { |
|
582 |
return a._id >= 0 && a._id < static_cast<int>(arcs.size()); |
|
583 |
} |
|
584 |
bool valid(Edge e) const { |
|
585 |
return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); |
|
586 |
} |
|
587 |
|
|
553 | 588 |
Node addNode() { |
554 | 589 |
int n = nodes.size(); |
555 | 590 |
nodes.push_back(NodeT()); |
556 | 591 |
nodes[n].first_out = -1; |
557 | 592 |
|
558 | 593 |
return Node(n); |
... | ... |
@@ -639,12 +674,39 @@ |
639 | 674 |
///and \c t. |
640 | 675 |
///\return the new edge. |
641 | 676 |
Edge addEdge(const Node& s, const Node& t) { |
642 | 677 |
return Parent::addEdge(s, t); |
643 | 678 |
} |
644 | 679 |
|
680 |
/// \brief Node validity check |
|
681 |
/// |
|
682 |
/// This function gives back true if the given node is valid, |
|
683 |
/// ie. it is a real node of the graph. |
|
684 |
/// |
|
685 |
/// \warning A removed node (using Snapshot) could become valid again |
|
686 |
/// when new nodes are added to the graph. |
|
687 |
bool valid(Node n) const { return Parent::valid(n); } |
|
688 |
|
|
689 |
/// \brief Arc validity check |
|
690 |
/// |
|
691 |
/// This function gives back true if the given arc is valid, |
|
692 |
/// ie. it is a real arc of the graph. |
|
693 |
/// |
|
694 |
/// \warning A removed arc (using Snapshot) could become valid again |
|
695 |
/// when new edges are added to the graph. |
|
696 |
bool valid(Arc a) const { return Parent::valid(a); } |
|
697 |
|
|
698 |
/// \brief Edge validity check |
|
699 |
/// |
|
700 |
/// This function gives back true if the given edge is valid, |
|
701 |
/// ie. it is a real edge of the graph. |
|
702 |
/// |
|
703 |
/// \warning A removed edge (using Snapshot) could become valid again |
|
704 |
/// when new edges are added to the graph. |
|
705 |
bool valid(Edge e) const { return Parent::valid(e); } |
|
706 |
|
|
645 | 707 |
///Clear the graph. |
646 | 708 |
|
647 | 709 |
///Erase all the nodes and edges from the graph. |
648 | 710 |
/// |
649 | 711 |
void clear() { |
650 | 712 |
Parent::clear(); |
... | ... |
@@ -19,13 +19,13 @@ |
19 | 19 |
#include <lemon/concepts/graph.h> |
20 | 20 |
#include <lemon/list_graph.h> |
21 | 21 |
#include <lemon/smart_graph.h> |
22 | 22 |
// #include <lemon/full_graph.h> |
23 | 23 |
// #include <lemon/grid_graph.h> |
24 | 24 |
|
25 |
|
|
25 |
#include <lemon/graph_utils.h> |
|
26 | 26 |
|
27 | 27 |
#include "test_tools.h" |
28 | 28 |
|
29 | 29 |
|
30 | 30 |
using namespace lemon; |
31 | 31 |
using namespace lemon::concepts; |
... | ... |
@@ -79,52 +79,15 @@ |
79 | 79 |
|
80 | 80 |
check(uee == e, "Wrong edge number."); |
81 | 81 |
// check(countEdges(g) == e, "Wrong edge number."); |
82 | 82 |
} |
83 | 83 |
|
84 | 84 |
template <typename Graph> |
85 |
void |
|
85 |
void check_graph_counts() { |
|
86 | 86 |
|
87 |
typedef typename Graph::NodeIt NodeIt; |
|
88 |
typedef typename Graph::EdgeIt EdgeIt; |
|
89 |
typedef typename Graph::ArcIt ArcIt; |
|
90 |
|
|
91 |
std::cout << "Nodes" << std::endl; |
|
92 |
int i=0; |
|
93 |
for(NodeIt it(g); it!=INVALID; ++it, ++i) { |
|
94 |
std::cout << " " << i << ": " << g.id(it) << std::endl; |
|
95 |
} |
|
96 |
|
|
97 |
std::cout << "Edge" << std::endl; |
|
98 |
i=0; |
|
99 |
for(EdgeIt it(g); it!=INVALID; ++it, ++i) { |
|
100 |
std::cout << " " << i << ": " << g.id(it) |
|
101 |
<< " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) |
|
102 |
<< ")" << std::endl; |
|
103 |
} |
|
104 |
|
|
105 |
std::cout << "Arc" << std::endl; |
|
106 |
i=0; |
|
107 |
for(ArcIt it(g); it!=INVALID; ++it, ++i) { |
|
108 |
std::cout << " " << i << ": " << g.id(it) |
|
109 |
<< " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) |
|
110 |
<< ")" << std::endl; |
|
111 |
} |
|
112 |
|
|
113 |
} |
|
114 |
|
|
115 |
template <typename Graph> |
|
116 |
void check_graph() { |
|
117 |
|
|
118 |
typedef typename Graph::Node Node; |
|
119 |
typedef typename Graph::Edge Edge; |
|
120 |
typedef typename Graph::Arc Arc; |
|
121 |
typedef typename Graph::NodeIt NodeIt; |
|
122 |
typedef typename Graph::EdgeIt EdgeIt; |
|
123 |
typedef typename Graph::ArcIt ArcIt; |
|
124 |
|
|
87 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
125 | 88 |
Graph g; |
126 | 89 |
|
127 | 90 |
check_item_counts(g,0,0); |
128 | 91 |
|
129 | 92 |
Node |
130 | 93 |
n1 = g.addNode(), |
... | ... |
@@ -132,17 +95,79 @@ |
132 | 95 |
n3 = g.addNode(); |
133 | 96 |
|
134 | 97 |
Edge |
135 | 98 |
e1 = g.addEdge(n1, n2), |
136 | 99 |
e2 = g.addEdge(n2, n3); |
137 | 100 |
|
138 |
// print_items(g); |
|
139 |
|
|
140 | 101 |
check_item_counts(g,3,2); |
141 | 102 |
} |
142 | 103 |
|
104 |
template <typename Graph> |
|
105 |
void check_graph_validity() { |
|
106 |
|
|
107 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
108 |
Graph g; |
|
109 |
|
|
110 |
check_item_counts(g,0,0); |
|
111 |
|
|
112 |
Node |
|
113 |
n1 = g.addNode(), |
|
114 |
n2 = g.addNode(), |
|
115 |
n3 = g.addNode(); |
|
116 |
|
|
117 |
Edge |
|
118 |
e1 = g.addEdge(n1, n2), |
|
119 |
e2 = g.addEdge(n2, n3); |
|
120 |
|
|
121 |
check(g.valid(n1), "Validity check"); |
|
122 |
check(g.valid(e1), "Validity check"); |
|
123 |
check(g.valid(g.direct(e1, true)), "Validity check"); |
|
124 |
|
|
125 |
check(!g.valid(g.nodeFromId(-1)), "Validity check"); |
|
126 |
check(!g.valid(g.edgeFromId(-1)), "Validity check"); |
|
127 |
check(!g.valid(g.arcFromId(-1)), "Validity check"); |
|
128 |
|
|
129 |
} |
|
130 |
|
|
131 |
template <typename Graph> |
|
132 |
void check_graph_validity_erase() { |
|
133 |
|
|
134 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
135 |
Graph g; |
|
136 |
|
|
137 |
check_item_counts(g,0,0); |
|
138 |
|
|
139 |
Node |
|
140 |
n1 = g.addNode(), |
|
141 |
n2 = g.addNode(), |
|
142 |
n3 = g.addNode(); |
|
143 |
|
|
144 |
Edge |
|
145 |
e1 = g.addEdge(n1, n2), |
|
146 |
e2 = g.addEdge(n2, n3); |
|
147 |
|
|
148 |
check(g.valid(n1), "Validity check"); |
|
149 |
check(g.valid(e1), "Validity check"); |
|
150 |
check(g.valid(g.direct(e1, true)), "Validity check"); |
|
151 |
|
|
152 |
g.erase(n1); |
|
153 |
|
|
154 |
check(!g.valid(n1), "Validity check"); |
|
155 |
check(g.valid(n2), "Validity check"); |
|
156 |
check(g.valid(n3), "Validity check"); |
|
157 |
check(!g.valid(e1), "Validity check"); |
|
158 |
check(g.valid(e2), "Validity check"); |
|
159 |
|
|
160 |
check(!g.valid(g.nodeFromId(-1)), "Validity check"); |
|
161 |
check(!g.valid(g.edgeFromId(-1)), "Validity check"); |
|
162 |
check(!g.valid(g.arcFromId(-1)), "Validity check"); |
|
163 |
|
|
164 |
} |
|
165 |
|
|
166 |
|
|
167 |
|
|
143 | 168 |
// void checkGridGraph(const GridGraph& g, int w, int h) { |
144 | 169 |
// check(g.width() == w, "Wrong width"); |
145 | 170 |
// check(g.height() == h, "Wrong height"); |
146 | 171 |
|
147 | 172 |
// for (int i = 0; i < w; ++i) { |
148 | 173 |
// for (int j = 0; j < h; ++j) { |
... | ... |
@@ -184,14 +209,17 @@ |
184 | 209 |
// } |
185 | 210 |
// } |
186 | 211 |
|
187 | 212 |
int main() { |
188 | 213 |
check_concepts(); |
189 | 214 |
|
190 |
check_graph<ListGraph>(); |
|
191 |
check_graph<SmartGraph>(); |
|
215 |
check_graph_counts<ListGraph>(); |
|
216 |
check_graph_counts<SmartGraph>(); |
|
217 |
|
|
218 |
check_graph_validity_erase<ListGraph>(); |
|
219 |
check_graph_validity<SmartGraph>(); |
|
192 | 220 |
|
193 | 221 |
// { |
194 | 222 |
// FullGraph g(5); |
195 | 223 |
// check_item_counts(g, 5, 10); |
196 | 224 |
// } |
197 | 225 |
|
0 comments (0 inline)