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 |
|
| ... | ... |
@@ -244,14 +255,14 @@ |
| 244 | 255 |
arcs[arcs[n].prev_out].next_out = arcs[n].next_out; |
| 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 |
first_free_arc = n; |
|
| 251 |
|
|
| 261 |
first_free_arc = n; |
|
| 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)