test/graph_test.cc
changeset 365 a12eef1f82b2
parent 356 99f1bdf8f7db
child 372 7b6466ed488a
equal deleted inserted replaced
11:5ec4464ecf18 12:28c40b9e990b
    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 
   119   checkEdgeIds(G);
   120   checkEdgeIds(G);
   120   checkGraphNodeMap(G);
   121   checkGraphNodeMap(G);
   121   checkGraphArcMap(G);
   122   checkGraphArcMap(G);
   122   checkGraphEdgeMap(G);
   123   checkGraphEdgeMap(G);
   123 
   124 
   124   
   125 
   125   for (int i = 0; i < G.nodeNum(); ++i) {
   126   for (int i = 0; i < G.nodeNum(); ++i) {
   126     check(G.index(G(i)) == i, "Wrong index");
   127     check(G.index(G(i)) == i, "Wrong index");
   127   }
   128   }
   128 
   129 
   129   for (NodeIt u(G); u != INVALID; ++u) {
   130   for (NodeIt u(G); u != INVALID; ++u) {
   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();