r388:2d87dbd7f8c8
Fri, 07 Nov 2008 14:14:22
[Not Reviewed]
0 comments (0 inline)
0
4
0
| ... | ... |
@@ -728,26 +728,26 @@ |
| 728 | 728 |
} |
| 729 | 729 |
|
| 730 | 730 |
void restoreSnapshot(const Snapshot &s) |
| 731 | 731 |
{
|
| 732 | 732 |
while(s.arc_num<arcs.size()) {
|
| 733 | 733 |
int n=arcs.size()-1; |
| 734 | 734 |
Edge arc=edgeFromId(n/2); |
| 735 | 735 |
Parent::notifier(Edge()).erase(arc); |
| 736 | 736 |
std::vector<Arc> dir; |
| 737 | 737 |
dir.push_back(arcFromId(n)); |
| 738 | 738 |
dir.push_back(arcFromId(n-1)); |
| 739 | 739 |
Parent::notifier(Arc()).erase(dir); |
| 740 |
nodes[arcs[n].target].first_out=arcs[n].next_out; |
|
| 741 |
nodes[arcs[n-1].target].first_out=arcs[n-1].next_out; |
|
| 740 |
nodes[arcs[n-1].target].first_out=arcs[n].next_out; |
|
| 741 |
nodes[arcs[n].target].first_out=arcs[n-1].next_out; |
|
| 742 | 742 |
arcs.pop_back(); |
| 743 | 743 |
arcs.pop_back(); |
| 744 | 744 |
} |
| 745 | 745 |
while(s.node_num<nodes.size()) {
|
| 746 | 746 |
int n=nodes.size()-1; |
| 747 | 747 |
Node node = nodeFromId(n); |
| 748 | 748 |
Parent::notifier(Node()).erase(node); |
| 749 | 749 |
nodes.pop_back(); |
| 750 | 750 |
} |
| 751 | 751 |
} |
| 752 | 752 |
|
| 753 | 753 |
public: |
| ... | ... |
@@ -19,25 +19,25 @@ |
| 19 | 19 |
#include <lemon/concepts/digraph.h> |
| 20 | 20 |
#include <lemon/list_graph.h> |
| 21 | 21 |
#include <lemon/smart_graph.h> |
| 22 | 22 |
#include <lemon/full_graph.h> |
| 23 | 23 |
|
| 24 | 24 |
#include "test_tools.h" |
| 25 | 25 |
#include "graph_test.h" |
| 26 | 26 |
|
| 27 | 27 |
using namespace lemon; |
| 28 | 28 |
using namespace lemon::concepts; |
| 29 | 29 |
|
| 30 | 30 |
template <class Digraph> |
| 31 |
void |
|
| 31 |
void checkDigraphBuild() {
|
|
| 32 | 32 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
| 33 | 33 |
Digraph G; |
| 34 | 34 |
|
| 35 | 35 |
checkGraphNodeList(G, 0); |
| 36 | 36 |
checkGraphArcList(G, 0); |
| 37 | 37 |
|
| 38 | 38 |
Node |
| 39 | 39 |
n1 = G.addNode(), |
| 40 | 40 |
n2 = G.addNode(), |
| 41 | 41 |
n3 = G.addNode(); |
| 42 | 42 |
checkGraphNodeList(G, 3); |
| 43 | 43 |
checkGraphArcList(G, 0); |
| ... | ... |
@@ -48,76 +48,253 @@ |
| 48 | 48 |
checkGraphArcList(G, 1); |
| 49 | 49 |
|
| 50 | 50 |
checkGraphOutArcList(G, n1, 1); |
| 51 | 51 |
checkGraphOutArcList(G, n2, 0); |
| 52 | 52 |
checkGraphOutArcList(G, n3, 0); |
| 53 | 53 |
|
| 54 | 54 |
checkGraphInArcList(G, n1, 0); |
| 55 | 55 |
checkGraphInArcList(G, n2, 1); |
| 56 | 56 |
checkGraphInArcList(G, n3, 0); |
| 57 | 57 |
|
| 58 | 58 |
checkGraphConArcList(G, 1); |
| 59 | 59 |
|
| 60 |
Arc a2 = G.addArc(n2, n1), |
|
| 60 |
Arc a2 = G.addArc(n2, n1), |
|
| 61 |
a3 = G.addArc(n2, n3), |
|
| 62 |
a4 = G.addArc(n2, n3); |
|
| 63 |
|
|
| 64 |
checkGraphNodeList(G, 3); |
|
| 65 |
checkGraphArcList(G, 4); |
|
| 66 |
|
|
| 67 |
checkGraphOutArcList(G, n1, 1); |
|
| 68 |
checkGraphOutArcList(G, n2, 3); |
|
| 69 |
checkGraphOutArcList(G, n3, 0); |
|
| 70 |
|
|
| 71 |
checkGraphInArcList(G, n1, 1); |
|
| 72 |
checkGraphInArcList(G, n2, 1); |
|
| 73 |
checkGraphInArcList(G, n3, 2); |
|
| 74 |
|
|
| 75 |
checkGraphConArcList(G, 4); |
|
| 76 |
|
|
| 77 |
checkNodeIds(G); |
|
| 78 |
checkArcIds(G); |
|
| 79 |
checkGraphNodeMap(G); |
|
| 80 |
checkGraphArcMap(G); |
|
| 81 |
} |
|
| 82 |
|
|
| 83 |
template <class Digraph> |
|
| 84 |
void checkDigraphSplit() {
|
|
| 85 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
| 86 |
|
|
| 87 |
Digraph G; |
|
| 88 |
Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); |
|
| 89 |
Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), |
|
| 90 |
a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); |
|
| 91 |
|
|
| 92 |
Node n4 = G.split(n2); |
|
| 93 |
|
|
| 94 |
check(G.target(OutArcIt(G, n2)) == n4 && |
|
| 95 |
G.source(InArcIt(G, n4)) == n2, |
|
| 96 |
"Wrong split."); |
|
| 97 |
|
|
| 98 |
checkGraphNodeList(G, 4); |
|
| 99 |
checkGraphArcList(G, 5); |
|
| 100 |
|
|
| 101 |
checkGraphOutArcList(G, n1, 1); |
|
| 102 |
checkGraphOutArcList(G, n2, 1); |
|
| 103 |
checkGraphOutArcList(G, n3, 0); |
|
| 104 |
checkGraphOutArcList(G, n4, 3); |
|
| 105 |
|
|
| 106 |
checkGraphInArcList(G, n1, 1); |
|
| 107 |
checkGraphInArcList(G, n2, 1); |
|
| 108 |
checkGraphInArcList(G, n3, 2); |
|
| 109 |
checkGraphInArcList(G, n4, 1); |
|
| 110 |
|
|
| 111 |
checkGraphConArcList(G, 5); |
|
| 112 |
} |
|
| 113 |
|
|
| 114 |
template <class Digraph> |
|
| 115 |
void checkDigraphAlter() {
|
|
| 116 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
| 117 |
|
|
| 118 |
Digraph G; |
|
| 119 |
Node n1 = G.addNode(), n2 = G.addNode(), |
|
| 120 |
n3 = G.addNode(), n4 = G.addNode(); |
|
| 121 |
Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), |
|
| 122 |
a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3), |
|
| 123 |
a5 = G.addArc(n2, n4); |
|
| 124 |
|
|
| 125 |
checkGraphNodeList(G, 4); |
|
| 126 |
checkGraphArcList(G, 5); |
|
| 127 |
|
|
| 128 |
// Check changeSource() and changeTarget() |
|
| 129 |
G.changeTarget(a4, n1); |
|
| 130 |
|
|
| 131 |
checkGraphNodeList(G, 4); |
|
| 132 |
checkGraphArcList(G, 5); |
|
| 133 |
|
|
| 134 |
checkGraphOutArcList(G, n1, 1); |
|
| 135 |
checkGraphOutArcList(G, n2, 1); |
|
| 136 |
checkGraphOutArcList(G, n3, 0); |
|
| 137 |
checkGraphOutArcList(G, n4, 3); |
|
| 138 |
|
|
| 139 |
checkGraphInArcList(G, n1, 2); |
|
| 140 |
checkGraphInArcList(G, n2, 1); |
|
| 141 |
checkGraphInArcList(G, n3, 1); |
|
| 142 |
checkGraphInArcList(G, n4, 1); |
|
| 143 |
|
|
| 144 |
checkGraphConArcList(G, 5); |
|
| 145 |
|
|
| 146 |
G.changeSource(a4, n3); |
|
| 147 |
|
|
| 148 |
checkGraphNodeList(G, 4); |
|
| 149 |
checkGraphArcList(G, 5); |
|
| 150 |
|
|
| 151 |
checkGraphOutArcList(G, n1, 1); |
|
| 152 |
checkGraphOutArcList(G, n2, 1); |
|
| 153 |
checkGraphOutArcList(G, n3, 1); |
|
| 154 |
checkGraphOutArcList(G, n4, 2); |
|
| 155 |
|
|
| 156 |
checkGraphInArcList(G, n1, 2); |
|
| 157 |
checkGraphInArcList(G, n2, 1); |
|
| 158 |
checkGraphInArcList(G, n3, 1); |
|
| 159 |
checkGraphInArcList(G, n4, 1); |
|
| 160 |
|
|
| 161 |
checkGraphConArcList(G, 5); |
|
| 162 |
|
|
| 163 |
// Check contract() |
|
| 164 |
G.contract(n2, n4, false); |
|
| 165 |
|
|
| 166 |
checkGraphNodeList(G, 3); |
|
| 167 |
checkGraphArcList(G, 5); |
|
| 168 |
|
|
| 169 |
checkGraphOutArcList(G, n1, 1); |
|
| 170 |
checkGraphOutArcList(G, n2, 3); |
|
| 171 |
checkGraphOutArcList(G, n3, 1); |
|
| 172 |
|
|
| 173 |
checkGraphInArcList(G, n1, 2); |
|
| 174 |
checkGraphInArcList(G, n2, 2); |
|
| 175 |
checkGraphInArcList(G, n3, 1); |
|
| 176 |
|
|
| 177 |
checkGraphConArcList(G, 5); |
|
| 178 |
|
|
| 179 |
G.contract(n2, n1); |
|
| 180 |
|
|
| 181 |
checkGraphNodeList(G, 2); |
|
| 182 |
checkGraphArcList(G, 3); |
|
| 183 |
|
|
| 184 |
checkGraphOutArcList(G, n2, 2); |
|
| 185 |
checkGraphOutArcList(G, n3, 1); |
|
| 186 |
|
|
| 187 |
checkGraphInArcList(G, n2, 2); |
|
| 188 |
checkGraphInArcList(G, n3, 1); |
|
| 189 |
|
|
| 190 |
checkGraphConArcList(G, 3); |
|
| 191 |
} |
|
| 192 |
|
|
| 193 |
template <class Digraph> |
|
| 194 |
void checkDigraphErase() {
|
|
| 195 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
| 196 |
|
|
| 197 |
Digraph G; |
|
| 198 |
Node n1 = G.addNode(), n2 = G.addNode(), |
|
| 199 |
n3 = G.addNode(), n4 = G.addNode(); |
|
| 200 |
Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1), |
|
| 201 |
a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1), |
|
| 202 |
a5 = G.addArc(n2, n4); |
|
| 203 |
|
|
| 204 |
// Check arc deletion |
|
| 205 |
G.erase(a1); |
|
| 206 |
|
|
| 207 |
checkGraphNodeList(G, 4); |
|
| 208 |
checkGraphArcList(G, 4); |
|
| 209 |
|
|
| 210 |
checkGraphOutArcList(G, n1, 0); |
|
| 211 |
checkGraphOutArcList(G, n2, 1); |
|
| 212 |
checkGraphOutArcList(G, n3, 1); |
|
| 213 |
checkGraphOutArcList(G, n4, 2); |
|
| 214 |
|
|
| 215 |
checkGraphInArcList(G, n1, 2); |
|
| 216 |
checkGraphInArcList(G, n2, 0); |
|
| 217 |
checkGraphInArcList(G, n3, 1); |
|
| 218 |
checkGraphInArcList(G, n4, 1); |
|
| 219 |
|
|
| 220 |
checkGraphConArcList(G, 4); |
|
| 221 |
|
|
| 222 |
// Check node deletion |
|
| 223 |
G.erase(n4); |
|
| 224 |
|
|
| 225 |
checkGraphNodeList(G, 3); |
|
| 226 |
checkGraphArcList(G, 1); |
|
| 227 |
|
|
| 228 |
checkGraphOutArcList(G, n1, 0); |
|
| 229 |
checkGraphOutArcList(G, n2, 0); |
|
| 230 |
checkGraphOutArcList(G, n3, 1); |
|
| 231 |
checkGraphOutArcList(G, n4, 0); |
|
| 232 |
|
|
| 233 |
checkGraphInArcList(G, n1, 1); |
|
| 234 |
checkGraphInArcList(G, n2, 0); |
|
| 235 |
checkGraphInArcList(G, n3, 0); |
|
| 236 |
checkGraphInArcList(G, n4, 0); |
|
| 237 |
|
|
| 238 |
checkGraphConArcList(G, 1); |
|
| 239 |
} |
|
| 240 |
|
|
| 241 |
|
|
| 242 |
template <class Digraph> |
|
| 243 |
void checkDigraphSnapshot() {
|
|
| 244 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
| 245 |
|
|
| 246 |
Digraph G; |
|
| 247 |
Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); |
|
| 248 |
Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1), |
|
| 249 |
a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); |
|
| 250 |
|
|
| 251 |
typename Digraph::Snapshot snapshot(G); |
|
| 252 |
|
|
| 253 |
Node n = G.addNode(); |
|
| 254 |
G.addArc(n3, n); |
|
| 255 |
G.addArc(n, n3); |
|
| 256 |
|
|
| 257 |
checkGraphNodeList(G, 4); |
|
| 258 |
checkGraphArcList(G, 6); |
|
| 259 |
|
|
| 260 |
snapshot.restore(); |
|
| 261 |
|
|
| 61 | 262 |
checkGraphNodeList(G, 3); |
| 62 | 263 |
checkGraphArcList(G, 4); |
| 63 | 264 |
|
| 64 | 265 |
checkGraphOutArcList(G, n1, 1); |
| 65 | 266 |
checkGraphOutArcList(G, n2, 3); |
| 66 | 267 |
checkGraphOutArcList(G, n3, 0); |
| 67 | 268 |
|
| 68 | 269 |
checkGraphInArcList(G, n1, 1); |
| 69 | 270 |
checkGraphInArcList(G, n2, 1); |
| 70 | 271 |
checkGraphInArcList(G, n3, 2); |
| 71 | 272 |
|
| 72 | 273 |
checkGraphConArcList(G, 4); |
| 73 | 274 |
|
| 74 | 275 |
checkNodeIds(G); |
| 75 | 276 |
checkArcIds(G); |
| 76 | 277 |
checkGraphNodeMap(G); |
| 77 | 278 |
checkGraphArcMap(G); |
| 78 | 279 |
|
| 79 |
|
|
| 280 |
G.addNode(); |
|
| 281 |
snapshot.save(G); |
|
| 80 | 282 |
|
| 81 |
void checkFullDigraph(int num) {
|
|
| 82 |
typedef FullDigraph Digraph; |
|
| 83 |
DIGRAPH_TYPEDEFS(Digraph); |
|
| 84 |
Digraph G(num); |
|
| 283 |
G.addArc(G.addNode(), G.addNode()); |
|
| 85 | 284 |
|
| 86 |
checkGraphNodeList(G, num); |
|
| 87 |
checkGraphArcList(G, num * num); |
|
| 285 |
snapshot.restore(); |
|
| 88 | 286 |
|
| 89 |
for (NodeIt n(G); n != INVALID; ++n) {
|
|
| 90 |
checkGraphOutArcList(G, n, num); |
|
| 91 |
checkGraphInArcList(G, n, num); |
|
| 92 |
} |
|
| 93 |
|
|
| 94 |
checkGraphConArcList(G, num * num); |
|
| 95 |
|
|
| 96 |
checkNodeIds(G); |
|
| 97 |
checkArcIds(G); |
|
| 98 |
checkGraphNodeMap(G); |
|
| 99 |
checkGraphArcMap(G); |
|
| 100 |
|
|
| 101 |
for (int i = 0; i < G.nodeNum(); ++i) {
|
|
| 102 |
check(G.index(G(i)) == i, "Wrong index"); |
|
| 103 |
} |
|
| 104 |
|
|
| 105 |
for (NodeIt s(G); s != INVALID; ++s) {
|
|
| 106 |
for (NodeIt t(G); t != INVALID; ++t) {
|
|
| 107 |
Arc a = G.arc(s, t); |
|
| 108 |
check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); |
|
| 109 |
} |
|
| 110 |
} |
|
| 111 |
|
|
| 287 |
checkGraphNodeList(G, 4); |
|
| 288 |
checkGraphArcList(G, 4); |
|
| 112 | 289 |
} |
| 113 | 290 |
|
| 114 | 291 |
void checkConcepts() {
|
| 115 | 292 |
{ // Checking digraph components
|
| 116 | 293 |
checkConcept<BaseDigraphComponent, BaseDigraphComponent >(); |
| 117 | 294 |
|
| 118 | 295 |
checkConcept<IDableDigraphComponent<>, |
| 119 | 296 |
IDableDigraphComponent<> >(); |
| 120 | 297 |
|
| 121 | 298 |
checkConcept<IterableDigraphComponent<>, |
| 122 | 299 |
IterableDigraphComponent<> >(); |
| 123 | 300 |
|
| ... | ... |
@@ -186,31 +363,69 @@ |
| 186 | 363 |
g.erase(n1); |
| 187 | 364 |
|
| 188 | 365 |
check(!g.valid(n1), "Wrong validity check"); |
| 189 | 366 |
check(g.valid(n2), "Wrong validity check"); |
| 190 | 367 |
check(g.valid(n3), "Wrong validity check"); |
| 191 | 368 |
check(!g.valid(e1), "Wrong validity check"); |
| 192 | 369 |
check(g.valid(e2), "Wrong validity check"); |
| 193 | 370 |
|
| 194 | 371 |
check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
| 195 | 372 |
check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
| 196 | 373 |
} |
| 197 | 374 |
|
| 375 |
void checkFullDigraph(int num) {
|
|
| 376 |
typedef FullDigraph Digraph; |
|
| 377 |
DIGRAPH_TYPEDEFS(Digraph); |
|
| 378 |
Digraph G(num); |
|
| 379 |
|
|
| 380 |
checkGraphNodeList(G, num); |
|
| 381 |
checkGraphArcList(G, num * num); |
|
| 382 |
|
|
| 383 |
for (NodeIt n(G); n != INVALID; ++n) {
|
|
| 384 |
checkGraphOutArcList(G, n, num); |
|
| 385 |
checkGraphInArcList(G, n, num); |
|
| 386 |
} |
|
| 387 |
|
|
| 388 |
checkGraphConArcList(G, num * num); |
|
| 389 |
|
|
| 390 |
checkNodeIds(G); |
|
| 391 |
checkArcIds(G); |
|
| 392 |
checkGraphNodeMap(G); |
|
| 393 |
checkGraphArcMap(G); |
|
| 394 |
|
|
| 395 |
for (int i = 0; i < G.nodeNum(); ++i) {
|
|
| 396 |
check(G.index(G(i)) == i, "Wrong index"); |
|
| 397 |
} |
|
| 398 |
|
|
| 399 |
for (NodeIt s(G); s != INVALID; ++s) {
|
|
| 400 |
for (NodeIt t(G); t != INVALID; ++t) {
|
|
| 401 |
Arc a = G.arc(s, t); |
|
| 402 |
check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup"); |
|
| 403 |
} |
|
| 404 |
} |
|
| 405 |
} |
|
| 406 |
|
|
| 198 | 407 |
void checkDigraphs() {
|
| 199 | 408 |
{ // Checking ListDigraph
|
| 200 |
|
|
| 409 |
checkDigraphBuild<ListDigraph>(); |
|
| 410 |
checkDigraphSplit<ListDigraph>(); |
|
| 411 |
checkDigraphAlter<ListDigraph>(); |
|
| 412 |
checkDigraphErase<ListDigraph>(); |
|
| 413 |
checkDigraphSnapshot<ListDigraph>(); |
|
| 201 | 414 |
checkDigraphValidityErase<ListDigraph>(); |
| 202 | 415 |
} |
| 203 | 416 |
{ // Checking SmartDigraph
|
| 204 |
|
|
| 417 |
checkDigraphBuild<SmartDigraph>(); |
|
| 418 |
checkDigraphSplit<SmartDigraph>(); |
|
| 419 |
checkDigraphSnapshot<SmartDigraph>(); |
|
| 205 | 420 |
checkDigraphValidity<SmartDigraph>(); |
| 206 | 421 |
} |
| 207 | 422 |
{ // Checking FullDigraph
|
| 208 | 423 |
checkFullDigraph(8); |
| 209 | 424 |
} |
| 210 | 425 |
} |
| 211 | 426 |
|
| 212 | 427 |
int main() {
|
| 213 | 428 |
checkDigraphs(); |
| 214 | 429 |
checkConcepts(); |
| 215 | 430 |
return 0; |
| 216 | 431 |
} |
| ... | ... |
@@ -21,90 +21,256 @@ |
| 21 | 21 |
#include <lemon/smart_graph.h> |
| 22 | 22 |
#include <lemon/full_graph.h> |
| 23 | 23 |
#include <lemon/grid_graph.h> |
| 24 | 24 |
#include <lemon/hypercube_graph.h> |
| 25 | 25 |
|
| 26 | 26 |
#include "test_tools.h" |
| 27 | 27 |
#include "graph_test.h" |
| 28 | 28 |
|
| 29 | 29 |
using namespace lemon; |
| 30 | 30 |
using namespace lemon::concepts; |
| 31 | 31 |
|
| 32 | 32 |
template <class Graph> |
| 33 |
void |
|
| 33 |
void checkGraphBuild() {
|
|
| 34 | 34 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
| 35 | 35 |
|
| 36 | 36 |
Graph G; |
| 37 | 37 |
checkGraphNodeList(G, 0); |
| 38 | 38 |
checkGraphEdgeList(G, 0); |
| 39 |
checkGraphArcList(G, 0); |
|
| 39 | 40 |
|
| 40 | 41 |
Node |
| 41 | 42 |
n1 = G.addNode(), |
| 42 | 43 |
n2 = G.addNode(), |
| 43 | 44 |
n3 = G.addNode(); |
| 44 | 45 |
checkGraphNodeList(G, 3); |
| 45 | 46 |
checkGraphEdgeList(G, 0); |
| 47 |
checkGraphArcList(G, 0); |
|
| 46 | 48 |
|
| 47 | 49 |
Edge e1 = G.addEdge(n1, n2); |
| 48 | 50 |
check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), |
| 49 | 51 |
"Wrong edge"); |
| 52 |
|
|
| 50 | 53 |
checkGraphNodeList(G, 3); |
| 54 |
checkGraphEdgeList(G, 1); |
|
| 51 | 55 |
checkGraphArcList(G, 2); |
| 52 |
checkGraphEdgeList(G, 1); |
|
| 53 | 56 |
|
| 54 |
checkGraphOutArcList(G, n1, 1); |
|
| 55 |
checkGraphOutArcList(G, n2, 1); |
|
| 56 |
|
|
| 57 |
checkGraphIncEdgeArcLists(G, n1, 1); |
|
| 58 |
checkGraphIncEdgeArcLists(G, n2, 1); |
|
| 59 |
checkGraphIncEdgeArcLists(G, n3, 0); |
|
| 57 | 60 |
|
| 58 |
checkGraphInArcList(G, n1, 1); |
|
| 59 |
checkGraphInArcList(G, n2, 1); |
|
| 60 |
|
|
| 61 |
checkGraphConEdgeList(G, 1); |
|
| 62 |
checkGraphConArcList(G, 2); |
|
| 61 | 63 |
|
| 62 |
checkGraphIncEdgeList(G, n1, 1); |
|
| 63 |
checkGraphIncEdgeList(G, n2, 1); |
|
| 64 |
|
|
| 64 |
Edge e2 = G.addEdge(n2, n1), |
|
| 65 |
e3 = G.addEdge(n2, n3); |
|
| 65 | 66 |
|
| 66 |
checkGraphConArcList(G, 2); |
|
| 67 |
checkGraphConEdgeList(G, 1); |
|
| 67 |
checkGraphNodeList(G, 3); |
|
| 68 |
checkGraphEdgeList(G, 3); |
|
| 69 |
checkGraphArcList(G, 6); |
|
| 68 | 70 |
|
| 69 |
Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); |
|
| 70 |
checkGraphNodeList(G, 3); |
|
| 71 |
checkGraphArcList(G, 6); |
|
| 72 |
checkGraphEdgeList(G, 3); |
|
| 71 |
checkGraphIncEdgeArcLists(G, n1, 2); |
|
| 72 |
checkGraphIncEdgeArcLists(G, n2, 3); |
|
| 73 |
checkGraphIncEdgeArcLists(G, n3, 1); |
|
| 73 | 74 |
|
| 74 |
checkGraphOutArcList(G, n1, 2); |
|
| 75 |
checkGraphOutArcList(G, n2, 3); |
|
| 76 |
checkGraphOutArcList(G, n3, 1); |
|
| 77 |
|
|
| 78 |
checkGraphInArcList(G, n1, 2); |
|
| 79 |
checkGraphInArcList(G, n2, 3); |
|
| 80 |
checkGraphInArcList(G, n3, 1); |
|
| 81 |
|
|
| 82 |
checkGraphIncEdgeList(G, n1, 2); |
|
| 83 |
checkGraphIncEdgeList(G, n2, 3); |
|
| 84 |
checkGraphIncEdgeList(G, n3, 1); |
|
| 85 |
|
|
| 75 |
checkGraphConEdgeList(G, 3); |
|
| 86 | 76 |
checkGraphConArcList(G, 6); |
| 87 |
checkGraphConEdgeList(G, 3); |
|
| 88 | 77 |
|
| 89 | 78 |
checkArcDirections(G); |
| 90 | 79 |
|
| 91 | 80 |
checkNodeIds(G); |
| 92 | 81 |
checkArcIds(G); |
| 93 | 82 |
checkEdgeIds(G); |
| 94 | 83 |
checkGraphNodeMap(G); |
| 95 | 84 |
checkGraphArcMap(G); |
| 96 | 85 |
checkGraphEdgeMap(G); |
| 97 | 86 |
} |
| 98 | 87 |
|
| 88 |
template <class Graph> |
|
| 89 |
void checkGraphAlter() {
|
|
| 90 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
| 91 |
|
|
| 92 |
Graph G; |
|
| 93 |
Node n1 = G.addNode(), n2 = G.addNode(), |
|
| 94 |
n3 = G.addNode(), n4 = G.addNode(); |
|
| 95 |
Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), |
|
| 96 |
e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), |
|
| 97 |
e5 = G.addEdge(n4, n3); |
|
| 98 |
|
|
| 99 |
checkGraphNodeList(G, 4); |
|
| 100 |
checkGraphEdgeList(G, 5); |
|
| 101 |
checkGraphArcList(G, 10); |
|
| 102 |
|
|
| 103 |
// Check changeU() and changeV() |
|
| 104 |
if (G.u(e2) == n2) {
|
|
| 105 |
G.changeU(e2, n3); |
|
| 106 |
} else {
|
|
| 107 |
G.changeV(e2, n3); |
|
| 108 |
} |
|
| 109 |
|
|
| 110 |
checkGraphNodeList(G, 4); |
|
| 111 |
checkGraphEdgeList(G, 5); |
|
| 112 |
checkGraphArcList(G, 10); |
|
| 113 |
|
|
| 114 |
checkGraphIncEdgeArcLists(G, n1, 3); |
|
| 115 |
checkGraphIncEdgeArcLists(G, n2, 2); |
|
| 116 |
checkGraphIncEdgeArcLists(G, n3, 3); |
|
| 117 |
checkGraphIncEdgeArcLists(G, n4, 2); |
|
| 118 |
|
|
| 119 |
checkGraphConEdgeList(G, 5); |
|
| 120 |
checkGraphConArcList(G, 10); |
|
| 121 |
|
|
| 122 |
if (G.u(e2) == n1) {
|
|
| 123 |
G.changeU(e2, n2); |
|
| 124 |
} else {
|
|
| 125 |
G.changeV(e2, n2); |
|
| 126 |
} |
|
| 127 |
|
|
| 128 |
checkGraphNodeList(G, 4); |
|
| 129 |
checkGraphEdgeList(G, 5); |
|
| 130 |
checkGraphArcList(G, 10); |
|
| 131 |
|
|
| 132 |
checkGraphIncEdgeArcLists(G, n1, 2); |
|
| 133 |
checkGraphIncEdgeArcLists(G, n2, 3); |
|
| 134 |
checkGraphIncEdgeArcLists(G, n3, 3); |
|
| 135 |
checkGraphIncEdgeArcLists(G, n4, 2); |
|
| 136 |
|
|
| 137 |
checkGraphConEdgeList(G, 5); |
|
| 138 |
checkGraphConArcList(G, 10); |
|
| 139 |
|
|
| 140 |
// Check contract() |
|
| 141 |
G.contract(n1, n4, false); |
|
| 142 |
|
|
| 143 |
checkGraphNodeList(G, 3); |
|
| 144 |
checkGraphEdgeList(G, 5); |
|
| 145 |
checkGraphArcList(G, 10); |
|
| 146 |
|
|
| 147 |
checkGraphIncEdgeArcLists(G, n1, 4); |
|
| 148 |
checkGraphIncEdgeArcLists(G, n2, 3); |
|
| 149 |
checkGraphIncEdgeArcLists(G, n3, 3); |
|
| 150 |
|
|
| 151 |
checkGraphConEdgeList(G, 5); |
|
| 152 |
checkGraphConArcList(G, 10); |
|
| 153 |
|
|
| 154 |
G.contract(n2, n3); |
|
| 155 |
|
|
| 156 |
checkGraphNodeList(G, 2); |
|
| 157 |
checkGraphEdgeList(G, 3); |
|
| 158 |
checkGraphArcList(G, 6); |
|
| 159 |
|
|
| 160 |
checkGraphIncEdgeArcLists(G, n1, 4); |
|
| 161 |
checkGraphIncEdgeArcLists(G, n2, 2); |
|
| 162 |
|
|
| 163 |
checkGraphConEdgeList(G, 3); |
|
| 164 |
checkGraphConArcList(G, 6); |
|
| 165 |
} |
|
| 166 |
|
|
| 167 |
template <class Graph> |
|
| 168 |
void checkGraphErase() {
|
|
| 169 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
| 170 |
|
|
| 171 |
Graph G; |
|
| 172 |
Node n1 = G.addNode(), n2 = G.addNode(), |
|
| 173 |
n3 = G.addNode(), n4 = G.addNode(); |
|
| 174 |
Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), |
|
| 175 |
e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4), |
|
| 176 |
e5 = G.addEdge(n4, n3); |
|
| 177 |
|
|
| 178 |
// Check edge deletion |
|
| 179 |
G.erase(e2); |
|
| 180 |
|
|
| 181 |
checkGraphNodeList(G, 4); |
|
| 182 |
checkGraphEdgeList(G, 4); |
|
| 183 |
checkGraphArcList(G, 8); |
|
| 184 |
|
|
| 185 |
checkGraphIncEdgeArcLists(G, n1, 2); |
|
| 186 |
checkGraphIncEdgeArcLists(G, n2, 2); |
|
| 187 |
checkGraphIncEdgeArcLists(G, n3, 2); |
|
| 188 |
checkGraphIncEdgeArcLists(G, n4, 2); |
|
| 189 |
|
|
| 190 |
checkGraphConEdgeList(G, 4); |
|
| 191 |
checkGraphConArcList(G, 8); |
|
| 192 |
|
|
| 193 |
// Check node deletion |
|
| 194 |
G.erase(n3); |
|
| 195 |
|
|
| 196 |
checkGraphNodeList(G, 3); |
|
| 197 |
checkGraphEdgeList(G, 2); |
|
| 198 |
checkGraphArcList(G, 4); |
|
| 199 |
|
|
| 200 |
checkGraphIncEdgeArcLists(G, n1, 2); |
|
| 201 |
checkGraphIncEdgeArcLists(G, n2, 1); |
|
| 202 |
checkGraphIncEdgeArcLists(G, n4, 1); |
|
| 203 |
|
|
| 204 |
checkGraphConEdgeList(G, 2); |
|
| 205 |
checkGraphConArcList(G, 4); |
|
| 206 |
} |
|
| 207 |
|
|
| 208 |
|
|
| 209 |
template <class Graph> |
|
| 210 |
void checkGraphSnapshot() {
|
|
| 211 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
|
| 212 |
|
|
| 213 |
Graph G; |
|
| 214 |
Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode(); |
|
| 215 |
Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1), |
|
| 216 |
e3 = G.addEdge(n2, n3); |
|
| 217 |
|
|
| 218 |
checkGraphNodeList(G, 3); |
|
| 219 |
checkGraphEdgeList(G, 3); |
|
| 220 |
checkGraphArcList(G, 6); |
|
| 221 |
|
|
| 222 |
typename Graph::Snapshot snapshot(G); |
|
| 223 |
|
|
| 224 |
Node n = G.addNode(); |
|
| 225 |
G.addEdge(n3, n); |
|
| 226 |
G.addEdge(n, n3); |
|
| 227 |
G.addEdge(n3, n2); |
|
| 228 |
|
|
| 229 |
checkGraphNodeList(G, 4); |
|
| 230 |
checkGraphEdgeList(G, 6); |
|
| 231 |
checkGraphArcList(G, 12); |
|
| 232 |
|
|
| 233 |
snapshot.restore(); |
|
| 234 |
|
|
| 235 |
checkGraphNodeList(G, 3); |
|
| 236 |
checkGraphEdgeList(G, 3); |
|
| 237 |
checkGraphArcList(G, 6); |
|
| 238 |
|
|
| 239 |
checkGraphIncEdgeArcLists(G, n1, 2); |
|
| 240 |
checkGraphIncEdgeArcLists(G, n2, 3); |
|
| 241 |
checkGraphIncEdgeArcLists(G, n3, 1); |
|
| 242 |
|
|
| 243 |
checkGraphConEdgeList(G, 3); |
|
| 244 |
checkGraphConArcList(G, 6); |
|
| 245 |
|
|
| 246 |
checkNodeIds(G); |
|
| 247 |
checkEdgeIds(G); |
|
| 248 |
checkArcIds(G); |
|
| 249 |
checkGraphNodeMap(G); |
|
| 250 |
checkGraphEdgeMap(G); |
|
| 251 |
checkGraphArcMap(G); |
|
| 252 |
|
|
| 253 |
G.addNode(); |
|
| 254 |
snapshot.save(G); |
|
| 255 |
|
|
| 256 |
G.addEdge(G.addNode(), G.addNode()); |
|
| 257 |
|
|
| 258 |
snapshot.restore(); |
|
| 259 |
|
|
| 260 |
checkGraphNodeList(G, 4); |
|
| 261 |
checkGraphEdgeList(G, 3); |
|
| 262 |
checkGraphArcList(G, 6); |
|
| 263 |
} |
|
| 264 |
|
|
| 99 | 265 |
void checkFullGraph(int num) {
|
| 100 | 266 |
typedef FullGraph Graph; |
| 101 | 267 |
GRAPH_TYPEDEFS(Graph); |
| 102 | 268 |
|
| 103 | 269 |
Graph G(num); |
| 104 | 270 |
checkGraphNodeList(G, num); |
| 105 | 271 |
checkGraphEdgeList(G, num * (num - 1) / 2); |
| 106 | 272 |
|
| 107 | 273 |
for (NodeIt n(G); n != INVALID; ++n) {
|
| 108 | 274 |
checkGraphOutArcList(G, n, num - 1); |
| 109 | 275 |
checkGraphInArcList(G, n, num - 1); |
| 110 | 276 |
checkGraphIncEdgeList(G, n, num - 1); |
| ... | ... |
@@ -357,29 +523,33 @@ |
| 357 | 523 |
checkArcDirections(G); |
| 358 | 524 |
|
| 359 | 525 |
checkNodeIds(G); |
| 360 | 526 |
checkArcIds(G); |
| 361 | 527 |
checkEdgeIds(G); |
| 362 | 528 |
checkGraphNodeMap(G); |
| 363 | 529 |
checkGraphArcMap(G); |
| 364 | 530 |
checkGraphEdgeMap(G); |
| 365 | 531 |
} |
| 366 | 532 |
|
| 367 | 533 |
void checkGraphs() {
|
| 368 | 534 |
{ // Checking ListGraph
|
| 369 |
|
|
| 535 |
checkGraphBuild<ListGraph>(); |
|
| 536 |
checkGraphAlter<ListGraph>(); |
|
| 537 |
checkGraphErase<ListGraph>(); |
|
| 538 |
checkGraphSnapshot<ListGraph>(); |
|
| 370 | 539 |
checkGraphValidityErase<ListGraph>(); |
| 371 | 540 |
} |
| 372 | 541 |
{ // Checking SmartGraph
|
| 373 |
|
|
| 542 |
checkGraphBuild<SmartGraph>(); |
|
| 543 |
checkGraphSnapshot<SmartGraph>(); |
|
| 374 | 544 |
checkGraphValidity<SmartGraph>(); |
| 375 | 545 |
} |
| 376 | 546 |
{ // Checking FullGraph
|
| 377 | 547 |
checkFullGraph(7); |
| 378 | 548 |
checkFullGraph(8); |
| 379 | 549 |
} |
| 380 | 550 |
{ // Checking GridGraph
|
| 381 | 551 |
checkGridGraph(5, 8); |
| 382 | 552 |
checkGridGraph(8, 5); |
| 383 | 553 |
checkGridGraph(5, 5); |
| 384 | 554 |
checkGridGraph(0, 0); |
| 385 | 555 |
checkGridGraph(1, 1); |
| ... | ... |
@@ -108,24 +108,33 @@ |
| 108 | 108 |
check(e!=INVALID,"Wrong IncEdge list linking."); |
| 109 | 109 |
check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking."); |
| 110 | 110 |
check(n==G.baseNode(e),"Wrong OutArc list linking."); |
| 111 | 111 |
check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e), |
| 112 | 112 |
"Wrong OutArc list linking."); |
| 113 | 113 |
++e; |
| 114 | 114 |
} |
| 115 | 115 |
check(e==INVALID,"Wrong IncEdge list linking."); |
| 116 | 116 |
check(countIncEdges(G,n)==cnt,"Wrong IncEdge number."); |
| 117 | 117 |
} |
| 118 | 118 |
|
| 119 | 119 |
template <class Graph> |
| 120 |
void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n, |
|
| 121 |
int cnt) |
|
| 122 |
{
|
|
| 123 |
checkGraphIncEdgeList(G, n, cnt); |
|
| 124 |
checkGraphOutArcList(G, n, cnt); |
|
| 125 |
checkGraphInArcList(G, n, cnt); |
|
| 126 |
} |
|
| 127 |
|
|
| 128 |
template <class Graph> |
|
| 120 | 129 |
void checkGraphConArcList(const Graph &G, int cnt) {
|
| 121 | 130 |
int i = 0; |
| 122 | 131 |
for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
|
| 123 | 132 |
for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
|
| 124 | 133 |
for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
|
| 125 | 134 |
check(G.source(a) == u, "Wrong iterator."); |
| 126 | 135 |
check(G.target(a) == v, "Wrong iterator."); |
| 127 | 136 |
++i; |
| 128 | 137 |
} |
| 129 | 138 |
} |
| 130 | 139 |
} |
| 131 | 140 |
check(cnt == i, "Wrong iterator."); |
0 comments (0 inline)