r388:2d87dbd7f8c8
Fri, 07 Nov 2008 14:14:22
[Not Reviewed]
0 comments (0 inline)
0
4
0
| ... | ... |
@@ -737,8 +737,8 @@ |
| 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 |
} |
| ... | ... |
@@ -28,7 +28,7 @@ |
| 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 |
|
| ... | ... |
@@ -57,7 +57,208 @@ |
| 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 |
|
| ... | ... |
@@ -76,39 +277,15 @@ |
| 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() {
|
| ... | ... |
@@ -195,13 +372,51 @@ |
| 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
|
| ... | ... |
@@ -30,12 +30,13 @@ |
| 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(), |
| ... | ... |
@@ -43,48 +44,36 @@ |
| 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 |
|
| ... | ... |
@@ -96,6 +85,183 @@ |
| 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); |
| ... | ... |
@@ -366,11 +532,15 @@ |
| 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
|
| ... | ... |
@@ -117,6 +117,15 @@ |
| 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) {
|
0 comments (0 inline)