Changeset 375:2d87dbd7f8c8 in lemon-1.2
- Timestamp:
- 11/07/08 14:14:22 (16 years ago)
- Branch:
- default
- Parents:
- 372:7b6466ed488a (diff), 374:49d9a36b3b84 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/smart_graph.h
r371 r375 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(); -
lemon/smart_graph.h
r373 r375 68 68 69 69 typedef True NodeNumTag; 70 typedef True EdgeNumTag;70 typedef True ArcNumTag; 71 71 72 72 int nodeNum() const { return nodes.size(); } … … 467 467 468 468 public: 469 operator Edge() const { 470 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 469 operator Edge() const { 470 return _id != -1 ? edgeFromId(_id / 2) : INVALID; 471 471 } 472 472 … … 483 483 : nodes(), arcs() {} 484 484 485 typedef True NodeNumTag; 486 typedef True EdgeNumTag; 487 typedef True ArcNumTag; 488 489 int nodeNum() const { return nodes.size(); } 490 int edgeNum() const { return arcs.size() / 2; } 491 int arcNum() const { return arcs.size(); } 485 492 486 493 int maxNodeId() const { return nodes.size()-1; } -
test/digraph_test.cc
r365 r375 29 29 30 30 template <class Digraph> 31 void checkDigraph () {31 void checkDigraphBuild() { 32 32 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 33 33 Digraph G; … … 58 58 checkGraphConArcList(G, 1); 59 59 60 Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 60 Arc a2 = G.addArc(n2, n1), 61 a3 = G.addArc(n2, n3), 62 a4 = G.addArc(n2, n3); 63 61 64 checkGraphNodeList(G, 3); 62 65 checkGraphArcList(G, 4); … … 76 79 checkGraphNodeMap(G); 77 80 checkGraphArcMap(G); 78 79 } 80 81 void checkFullDigraph(int num) { 82 typedef FullDigraph Digraph; 83 DIGRAPH_TYPEDEFS(Digraph); 84 Digraph G(num); 85 86 checkGraphNodeList(G, num); 87 checkGraphArcList(G, num * num); 88 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); 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 262 checkGraphNodeList(G, 3); 263 checkGraphArcList(G, 4); 264 265 checkGraphOutArcList(G, n1, 1); 266 checkGraphOutArcList(G, n2, 3); 267 checkGraphOutArcList(G, n3, 0); 268 269 checkGraphInArcList(G, n1, 1); 270 checkGraphInArcList(G, n2, 1); 271 checkGraphInArcList(G, n3, 2); 272 273 checkGraphConArcList(G, 4); 95 274 96 275 checkNodeIds(G); … … 99 278 checkGraphArcMap(G); 100 279 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 280 G.addNode(); 281 snapshot.save(G); 282 283 G.addArc(G.addNode(), G.addNode()); 284 285 snapshot.restore(); 286 287 checkGraphNodeList(G, 4); 288 checkGraphArcList(G, 4); 112 289 } 113 290 … … 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 checkDigraph<ListDigraph>(); 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 checkDigraph<SmartDigraph>(); 417 checkDigraphBuild<SmartDigraph>(); 418 checkDigraphSplit<SmartDigraph>(); 419 checkDigraphSnapshot<SmartDigraph>(); 205 420 checkDigraphValidity<SmartDigraph>(); 206 421 } -
test/digraph_test.cc
r374 r375 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 //#include <lemon/full_graph.h> 23 //#include <lemon/hypercube_graph.h> 22 #include <lemon/full_graph.h> 24 23 25 24 #include "test_tools.h" … … 319 318 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 320 319 } 321 // { // Checking FullDigraph 322 // checkConcept<Digraph, FullDigraph>(); 323 // } 324 // { // Checking HyperCubeDigraph 325 // checkConcept<Digraph, HyperCubeDigraph>(); 326 // } 320 { // Checking FullDigraph 321 checkConcept<Digraph, FullDigraph>(); 322 } 327 323 } 328 324 … … 375 371 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); 376 372 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 373 } 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 } 377 405 } 378 406 … … 392 420 checkDigraphValidity<SmartDigraph>(); 393 421 } 422 { // Checking FullDigraph 423 checkFullDigraph(8); 424 } 394 425 } 395 426 -
test/graph_test.cc
r372 r375 31 31 32 32 template <class Graph> 33 void checkGraph () {33 void checkGraphBuild() { 34 34 TEMPLATE_GRAPH_TYPEDEFS(Graph); 35 35 … … 37 37 checkGraphNodeList(G, 0); 38 38 checkGraphEdgeList(G, 0); 39 checkGraphArcList(G, 0); 39 40 40 41 Node … … 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"); 50 checkGraphNodeList(G, 3); 52 53 checkGraphNodeList(G, 3); 54 checkGraphEdgeList(G, 1); 51 55 checkGraphArcList(G, 2); 52 checkGraphEdgeList(G, 1); 53 54 checkGraphOutArcList(G, n1, 1); 55 checkGraphOutArcList(G, n2, 1); 56 checkGraphOutArcList(G, n3, 0); 57 58 checkGraphInArcList(G, n1, 1); 59 checkGraphInArcList(G, n2, 1); 60 checkGraphInArcList(G, n3, 0); 61 62 checkGraphIncEdgeList(G, n1, 1); 63 checkGraphIncEdgeList(G, n2, 1); 64 checkGraphIncEdgeList(G, n3, 0); 65 56 57 checkGraphIncEdgeArcLists(G, n1, 1); 58 checkGraphIncEdgeArcLists(G, n2, 1); 59 checkGraphIncEdgeArcLists(G, n3, 0); 60 61 checkGraphConEdgeList(G, 1); 66 62 checkGraphConArcList(G, 2); 67 checkGraphConEdgeList(G, 1); 68 69 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); 70 checkGraphNodeList(G, 3); 63 64 Edge e2 = G.addEdge(n2, n1), 65 e3 = G.addEdge(n2, n3); 66 67 checkGraphNodeList(G, 3); 68 checkGraphEdgeList(G, 3); 71 69 checkGraphArcList(G, 6); 72 checkGraphEdgeList(G, 3); 73 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 70 71 checkGraphIncEdgeArcLists(G, n1, 2); 72 checkGraphIncEdgeArcLists(G, n2, 3); 73 checkGraphIncEdgeArcLists(G, n3, 1); 74 75 checkGraphConEdgeList(G, 3); 86 76 checkGraphConArcList(G, 6); 87 checkGraphConEdgeList(G, 3);88 77 89 78 checkArcDirections(G); … … 95 84 checkGraphArcMap(G); 96 85 checkGraphEdgeMap(G); 86 } 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); 97 263 } 98 264 … … 367 533 void checkGraphs() { 368 534 { // Checking ListGraph 369 checkGraph<ListGraph>(); 535 checkGraphBuild<ListGraph>(); 536 checkGraphAlter<ListGraph>(); 537 checkGraphErase<ListGraph>(); 538 checkGraphSnapshot<ListGraph>(); 370 539 checkGraphValidityErase<ListGraph>(); 371 540 } 372 541 { // Checking SmartGraph 373 checkGraph<SmartGraph>(); 542 checkGraphBuild<SmartGraph>(); 543 checkGraphSnapshot<SmartGraph>(); 374 544 checkGraphValidity<SmartGraph>(); 375 545 } -
test/graph_test.cc
r374 r375 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 // #include <lemon/full_graph.h> 23 // #include <lemon/grid_graph.h> 22 #include <lemon/full_graph.h> 23 #include <lemon/grid_graph.h> 24 #include <lemon/hypercube_graph.h> 24 25 25 26 #include "test_tools.h" … … 262 263 } 263 264 265 void checkFullGraph(int num) { 266 typedef FullGraph Graph; 267 GRAPH_TYPEDEFS(Graph); 268 269 Graph G(num); 270 checkGraphNodeList(G, num); 271 checkGraphEdgeList(G, num * (num - 1) / 2); 272 273 for (NodeIt n(G); n != INVALID; ++n) { 274 checkGraphOutArcList(G, n, num - 1); 275 checkGraphInArcList(G, n, num - 1); 276 checkGraphIncEdgeList(G, n, num - 1); 277 } 278 279 checkGraphConArcList(G, num * (num - 1)); 280 checkGraphConEdgeList(G, num * (num - 1) / 2); 281 282 checkArcDirections(G); 283 284 checkNodeIds(G); 285 checkArcIds(G); 286 checkEdgeIds(G); 287 checkGraphNodeMap(G); 288 checkGraphArcMap(G); 289 checkGraphEdgeMap(G); 290 291 292 for (int i = 0; i < G.nodeNum(); ++i) { 293 check(G.index(G(i)) == i, "Wrong index"); 294 } 295 296 for (NodeIt u(G); u != INVALID; ++u) { 297 for (NodeIt v(G); v != INVALID; ++v) { 298 Edge e = G.edge(u, v); 299 Arc a = G.arc(u, v); 300 if (u == v) { 301 check(e == INVALID, "Wrong edge lookup"); 302 check(a == INVALID, "Wrong arc lookup"); 303 } else { 304 check((G.u(e) == u && G.v(e) == v) || 305 (G.u(e) == v && G.v(e) == u), "Wrong edge lookup"); 306 check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup"); 307 } 308 } 309 } 310 } 311 264 312 void checkConcepts() { 265 313 { // Checking graph components … … 291 339 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 292 340 } 293 // { // Checking FullGraph 294 // checkConcept<Graph, FullGraph>(); 295 // checkGraphIterators<FullGraph>(); 296 // } 297 // { // Checking GridGraph 298 // checkConcept<Graph, GridGraph>(); 299 // checkGraphIterators<GridGraph>(); 300 // } 341 { // Checking FullGraph 342 checkConcept<Graph, FullGraph>(); 343 } 344 { // Checking GridGraph 345 checkConcept<Graph, GridGraph>(); 346 } 347 { // Checking HypercubeGraph 348 checkConcept<Graph, HypercubeGraph>(); 349 } 301 350 } 302 351 … … 355 404 } 356 405 357 // void checkGridGraph(const GridGraph& g, int w, int h) { 358 // check(g.width() == w, "Wrong width"); 359 // check(g.height() == h, "Wrong height"); 360 361 // for (int i = 0; i < w; ++i) { 362 // for (int j = 0; j < h; ++j) { 363 // check(g.col(g(i, j)) == i, "Wrong col"); 364 // check(g.row(g(i, j)) == j, "Wrong row"); 365 // } 366 // } 367 368 // for (int i = 0; i < w; ++i) { 369 // for (int j = 0; j < h - 1; ++j) { 370 // check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); 371 // check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); 372 // } 373 // check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); 374 // } 375 376 // for (int i = 0; i < w; ++i) { 377 // for (int j = 1; j < h; ++j) { 378 // check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); 379 // check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); 380 // } 381 // check(g.up(g(i, 0)) == INVALID, "Wrong up"); 382 // } 383 384 // for (int j = 0; j < h; ++j) { 385 // for (int i = 0; i < w - 1; ++i) { 386 // check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); 387 // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); 388 // } 389 // check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); 390 // } 391 392 // for (int j = 0; j < h; ++j) { 393 // for (int i = 1; i < w; ++i) { 394 // check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); 395 // check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); 396 // } 397 // check(g.left(g(0, j)) == INVALID, "Wrong left"); 398 // } 399 // } 406 void checkGridGraph(int width, int height) { 407 typedef GridGraph Graph; 408 GRAPH_TYPEDEFS(Graph); 409 Graph G(width, height); 410 411 check(G.width() == width, "Wrong column number"); 412 check(G.height() == height, "Wrong row number"); 413 414 for (int i = 0; i < width; ++i) { 415 for (int j = 0; j < height; ++j) { 416 check(G.col(G(i, j)) == i, "Wrong column"); 417 check(G.row(G(i, j)) == j, "Wrong row"); 418 check(G.pos(G(i, j)).x == i, "Wrong column"); 419 check(G.pos(G(i, j)).y == j, "Wrong row"); 420 } 421 } 422 423 for (int j = 0; j < height; ++j) { 424 for (int i = 0; i < width - 1; ++i) { 425 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); 426 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); 427 } 428 check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); 429 } 430 431 for (int j = 0; j < height; ++j) { 432 for (int i = 1; i < width; ++i) { 433 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); 434 check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); 435 } 436 check(G.left(G(0, j)) == INVALID, "Wrong left"); 437 } 438 439 for (int i = 0; i < width; ++i) { 440 for (int j = 0; j < height - 1; ++j) { 441 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); 442 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); 443 } 444 check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); 445 } 446 447 for (int i = 0; i < width; ++i) { 448 for (int j = 1; j < height; ++j) { 449 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); 450 check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); 451 } 452 check(G.down(G(i, 0)) == INVALID, "Wrong down"); 453 } 454 455 checkGraphNodeList(G, width * height); 456 checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); 457 checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 458 459 for (NodeIt n(G); n != INVALID; ++n) { 460 int nb = 4; 461 if (G.col(n) == 0) --nb; 462 if (G.col(n) == width - 1) --nb; 463 if (G.row(n) == 0) --nb; 464 if (G.row(n) == height - 1) --nb; 465 466 checkGraphOutArcList(G, n, nb); 467 checkGraphInArcList(G, n, nb); 468 checkGraphIncEdgeList(G, n, nb); 469 } 470 471 checkArcDirections(G); 472 473 checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 474 checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); 475 476 checkNodeIds(G); 477 checkArcIds(G); 478 checkEdgeIds(G); 479 checkGraphNodeMap(G); 480 checkGraphArcMap(G); 481 checkGraphEdgeMap(G); 482 483 } 484 485 void checkHypercubeGraph(int dim) { 486 GRAPH_TYPEDEFS(HypercubeGraph); 487 488 HypercubeGraph G(dim); 489 checkGraphNodeList(G, 1 << dim); 490 checkGraphEdgeList(G, dim * (1 << (dim-1))); 491 checkGraphArcList(G, dim * (1 << dim)); 492 493 Node n = G.nodeFromId(dim); 494 495 for (NodeIt n(G); n != INVALID; ++n) { 496 checkGraphIncEdgeList(G, n, dim); 497 for (IncEdgeIt e(G, n); e != INVALID; ++e) { 498 check( (G.u(e) == n && 499 G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) || 500 (G.v(e) == n && 501 G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))), 502 "Wrong edge or wrong dimension"); 503 } 504 505 checkGraphOutArcList(G, n, dim); 506 for (OutArcIt a(G, n); a != INVALID; ++a) { 507 check(G.source(a) == n && 508 G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))), 509 "Wrong arc or wrong dimension"); 510 } 511 512 checkGraphInArcList(G, n, dim); 513 for (InArcIt a(G, n); a != INVALID; ++a) { 514 check(G.target(a) == n && 515 G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))), 516 "Wrong arc or wrong dimension"); 517 } 518 } 519 520 checkGraphConArcList(G, (1 << dim) * dim); 521 checkGraphConEdgeList(G, dim * (1 << (dim-1))); 522 523 checkArcDirections(G); 524 525 checkNodeIds(G); 526 checkArcIds(G); 527 checkEdgeIds(G); 528 checkGraphNodeMap(G); 529 checkGraphArcMap(G); 530 checkGraphEdgeMap(G); 531 } 400 532 401 533 void checkGraphs() { … … 412 544 checkGraphValidity<SmartGraph>(); 413 545 } 414 // { // Checking FullGraph 415 // FullGraph g(5); 416 // checkGraphNodeList(g, 5); 417 // checkGraphEdgeList(g, 10); 418 // } 419 // { // Checking GridGraph 420 // GridGraph g(5, 6); 421 // checkGraphNodeList(g, 30); 422 // checkGraphEdgeList(g, 49); 423 // checkGridGraph(g, 5, 6); 424 // } 546 { // Checking FullGraph 547 checkFullGraph(7); 548 checkFullGraph(8); 549 } 550 { // Checking GridGraph 551 checkGridGraph(5, 8); 552 checkGridGraph(8, 5); 553 checkGridGraph(5, 5); 554 checkGridGraph(0, 0); 555 checkGridGraph(1, 1); 556 } 557 { // Checking HypercubeGraph 558 checkHypercubeGraph(1); 559 checkHypercubeGraph(2); 560 checkHypercubeGraph(3); 561 checkHypercubeGraph(4); 562 } 425 563 } 426 564
Note: See TracChangeset
for help on using the changeset viewer.