r149:2f7ae34e1333
Thu, 24 Apr 2008 14:53:09
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -154,2 +154,12 @@ |
| 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() {
|
| ... | ... |
@@ -221,2 +231,3 @@ |
| 221 | 231 |
first_free_node = n; |
| 232 |
nodes[n].prev = -2; |
|
| 222 | 233 |
|
| ... | ... |
@@ -249,4 +260,4 @@ |
| 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 |
} |
| ... | ... |
@@ -352,2 +363,22 @@ |
| 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 |
| ... | ... |
@@ -947,2 +978,17 @@ |
| 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() {
|
| ... | ... |
@@ -1015,3 +1061,3 @@ |
| 1015 | 1061 |
first_free_node = n; |
| 1016 |
|
|
| 1062 |
nodes[n].prev = -2; |
|
| 1017 | 1063 |
} |
| ... | ... |
@@ -1043,2 +1089,4 @@ |
| 1043 | 1089 |
first_free_arc = n; |
| 1090 |
arcs[n].prev_out = -2; |
|
| 1091 |
arcs[n | 1].prev_out = -2; |
|
| 1044 | 1092 |
|
| ... | ... |
@@ -1159,2 +1207,29 @@ |
| 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 |
| ... | ... |
@@ -117,2 +117,9 @@ |
| 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 {
|
| ... | ... |
@@ -263,2 +270,20 @@ |
| 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. |
| ... | ... |
@@ -552,2 +577,12 @@ |
| 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() {
|
| ... | ... |
@@ -644,2 +679,29 @@ |
| 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. |
| ... | ... |
@@ -24,3 +24,3 @@ |
| 24 | 24 |
|
| 25 |
|
|
| 25 |
#include <lemon/graph_utils.h> |
|
| 26 | 26 |
|
| ... | ... |
@@ -84,42 +84,5 @@ |
| 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; |
| ... | ... |
@@ -137,4 +100,2 @@ |
| 137 | 100 |
|
| 138 |
// print_items(g); |
|
| 139 |
|
|
| 140 | 101 |
check_item_counts(g,3,2); |
| ... | ... |
@@ -142,2 +103,66 @@ |
| 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) {
|
| ... | ... |
@@ -189,4 +214,7 @@ |
| 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 |
|
0 comments (0 inline)