r149:2f7ae34e1333
Thu, 24 Apr 2008 14:53:09
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -152,6 +152,16 @@ |
| 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 |
|
| ... | ... |
@@ -219,6 +229,7 @@ |
| 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 |
|
| ... | ... |
@@ -247,8 +258,8 @@ |
| 247 | 258 |
} |
| 248 | 259 |
|
| 249 | 260 |
arcs[n].next_in = first_free_arc; |
| 250 |
first_free_arc = n; |
|
| 251 |
|
|
| 261 |
first_free_arc = n; |
|
| 262 |
arcs[n].prev_in = -2; |
|
| 252 | 263 |
} |
| 253 | 264 |
|
| 254 | 265 |
void clear() {
|
| ... | ... |
@@ -350,6 +361,26 @@ |
| 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 |
| ... | ... |
@@ -945,6 +976,21 @@ |
| 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 |
|
| ... | ... |
@@ -1013,7 +1059,7 @@ |
| 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) {
|
| ... | ... |
@@ -1041,6 +1087,8 @@ |
| 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 |
|
| ... | ... |
@@ -1157,6 +1205,33 @@ |
| 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. |
| ... | ... |
@@ -115,6 +115,13 @@ |
| 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; |
| ... | ... |
@@ -261,6 +268,24 @@ |
| 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. |
| ... | ... |
@@ -550,6 +575,16 @@ |
| 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()); |
| ... | ... |
@@ -642,6 +677,33 @@ |
| 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. |
| ... | ... |
@@ -22,7 +22,7 @@ |
| 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 |
|
| ... | ... |
@@ -82,46 +82,9 @@ |
| 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); |
| ... | ... |
@@ -135,11 +98,73 @@ |
| 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"); |
| ... | ... |
@@ -187,8 +212,11 @@ |
| 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); |
0 comments (0 inline)