19 #include <lemon/concepts/graph.h> |
19 #include <lemon/concepts/graph.h> |
20 #include <lemon/list_graph.h> |
20 #include <lemon/list_graph.h> |
21 #include <lemon/smart_graph.h> |
21 #include <lemon/smart_graph.h> |
22 #include <lemon/full_graph.h> |
22 #include <lemon/full_graph.h> |
23 #include <lemon/grid_graph.h> |
23 #include <lemon/grid_graph.h> |
|
24 #include <lemon/hypercube_graph.h> |
24 |
25 |
25 #include "test_tools.h" |
26 #include "test_tools.h" |
26 #include "graph_test.h" |
27 #include "graph_test.h" |
27 |
28 |
28 using namespace lemon; |
29 using namespace lemon; |
102 Graph G(num); |
103 Graph G(num); |
103 checkGraphNodeList(G, num); |
104 checkGraphNodeList(G, num); |
104 checkGraphEdgeList(G, num * (num - 1) / 2); |
105 checkGraphEdgeList(G, num * (num - 1) / 2); |
105 |
106 |
106 for (NodeIt n(G); n != INVALID; ++n) { |
107 for (NodeIt n(G); n != INVALID; ++n) { |
107 checkGraphOutArcList(G, n, num - 1); |
108 checkGraphOutArcList(G, n, num - 1); |
108 checkGraphInArcList(G, n, num - 1); |
109 checkGraphInArcList(G, n, num - 1); |
109 checkGraphIncEdgeList(G, n, num - 1); |
110 checkGraphIncEdgeList(G, n, num - 1); |
110 } |
111 } |
111 |
112 |
112 checkGraphConArcList(G, num * (num - 1)); |
113 checkGraphConArcList(G, num * (num - 1)); |
113 checkGraphConEdgeList(G, num * (num - 1) / 2); |
114 checkGraphConEdgeList(G, num * (num - 1) / 2); |
114 |
115 |
175 checkConcept<Graph, FullGraph>(); |
176 checkConcept<Graph, FullGraph>(); |
176 } |
177 } |
177 { // Checking GridGraph |
178 { // Checking GridGraph |
178 checkConcept<Graph, GridGraph>(); |
179 checkConcept<Graph, GridGraph>(); |
179 } |
180 } |
|
181 { // Checking HypercubeGraph |
|
182 checkConcept<Graph, HypercubeGraph>(); |
|
183 } |
180 } |
184 } |
181 |
185 |
182 template <typename Graph> |
186 template <typename Graph> |
183 void checkGraphValidity() { |
187 void checkGraphValidity() { |
184 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
188 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
310 checkGraphArcMap(G); |
314 checkGraphArcMap(G); |
311 checkGraphEdgeMap(G); |
315 checkGraphEdgeMap(G); |
312 |
316 |
313 } |
317 } |
314 |
318 |
|
319 void checkHypercubeGraph(int dim) { |
|
320 GRAPH_TYPEDEFS(HypercubeGraph); |
|
321 |
|
322 HypercubeGraph G(dim); |
|
323 checkGraphNodeList(G, 1 << dim); |
|
324 checkGraphEdgeList(G, dim * (1 << dim-1)); |
|
325 checkGraphArcList(G, dim * (1 << dim)); |
|
326 |
|
327 Node n = G.nodeFromId(dim); |
|
328 |
|
329 for (NodeIt n(G); n != INVALID; ++n) { |
|
330 checkGraphIncEdgeList(G, n, dim); |
|
331 for (IncEdgeIt e(G, n); e != INVALID; ++e) { |
|
332 check( (G.u(e) == n && |
|
333 G.id(G.v(e)) == G.id(n) ^ (1 << G.dimension(e))) || |
|
334 (G.v(e) == n && |
|
335 G.id(G.u(e)) == G.id(n) ^ (1 << G.dimension(e))), |
|
336 "Wrong edge or wrong dimension"); |
|
337 } |
|
338 |
|
339 checkGraphOutArcList(G, n, dim); |
|
340 for (OutArcIt a(G, n); a != INVALID; ++a) { |
|
341 check(G.source(a) == n && |
|
342 G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)), |
|
343 "Wrong arc or wrong dimension"); |
|
344 } |
|
345 |
|
346 checkGraphInArcList(G, n, dim); |
|
347 for (InArcIt a(G, n); a != INVALID; ++a) { |
|
348 check(G.target(a) == n && |
|
349 G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)), |
|
350 "Wrong arc or wrong dimension"); |
|
351 } |
|
352 } |
|
353 |
|
354 checkGraphConArcList(G, (1 << dim) * dim); |
|
355 checkGraphConEdgeList(G, dim * (1 << dim-1)); |
|
356 |
|
357 checkArcDirections(G); |
|
358 |
|
359 checkNodeIds(G); |
|
360 checkArcIds(G); |
|
361 checkEdgeIds(G); |
|
362 checkGraphNodeMap(G); |
|
363 checkGraphArcMap(G); |
|
364 checkGraphEdgeMap(G); |
|
365 } |
|
366 |
315 void checkGraphs() { |
367 void checkGraphs() { |
316 { // Checking ListGraph |
368 { // Checking ListGraph |
317 checkGraph<ListGraph>(); |
369 checkGraph<ListGraph>(); |
318 checkGraphValidityErase<ListGraph>(); |
370 checkGraphValidityErase<ListGraph>(); |
319 } |
371 } |
320 { // Checking SmartGraph |
372 { // Checking SmartGraph |
321 checkGraph<SmartGraph>(); |
373 checkGraph<SmartGraph>(); |
322 checkGraphValidity<SmartGraph>(); |
374 checkGraphValidity<SmartGraph>(); |
323 } |
375 } |
324 { // Checking FullGraph |
376 { // Checking FullGraph |
325 checkFullGraph(7); |
377 checkFullGraph(7); |
326 checkFullGraph(8); |
378 checkFullGraph(8); |
327 } |
379 } |
328 { // Checking GridGraph |
380 { // Checking GridGraph |
329 checkGridGraph(5, 8); |
381 checkGridGraph(5, 8); |
330 checkGridGraph(8, 5); |
382 checkGridGraph(8, 5); |
331 checkGridGraph(5, 5); |
383 checkGridGraph(5, 5); |
332 checkGridGraph(0, 0); |
384 checkGridGraph(0, 0); |
333 checkGridGraph(1, 1); |
385 checkGridGraph(1, 1); |
334 } |
386 } |
|
387 { // Checking HypercubeGraph |
|
388 checkHypercubeGraph(1); |
|
389 checkHypercubeGraph(2); |
|
390 checkHypercubeGraph(3); |
|
391 checkHypercubeGraph(4); |
|
392 } |
335 } |
393 } |
336 |
394 |
337 int main() { |
395 int main() { |
338 checkConcepts(); |
396 checkConcepts(); |
339 checkGraphs(); |
397 checkGraphs(); |