Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/digraph_test.cc
changeset 404 660db48f324f
parent 377 a12eef1f82b2
parent 387 49d9a36b3b84
child 463 88ed40ad0d4f
equal deleted inserted replaced
8:50a41b945d1f 10:9b20426ef9d4 
    26 
    26 
    27 using namespace lemon;
 
    27 using namespace lemon;
 
    28 using namespace lemon::concepts;
 
    28 using namespace lemon::concepts;
 
    29 
    29 
    30 template <class Digraph>
 
    30 template <class Digraph>
 
    31 void checkDigraph() {
 
    31 void checkDigraphBuild() {
 
    32   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 
    32   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 
    33   Digraph G;
 
    33   Digraph G;
 
    34 
    34 
    35   checkGraphNodeList(G, 0);
 
    35   checkGraphNodeList(G, 0);
 
    36   checkGraphArcList(G, 0);
 
    36   checkGraphArcList(G, 0);
 
    55   checkGraphInArcList(G, n2, 1);
 
    55   checkGraphInArcList(G, n2, 1);
 
    56   checkGraphInArcList(G, n3, 0);
 
    56   checkGraphInArcList(G, n3, 0);
 
    57 
    57 
    58   checkGraphConArcList(G, 1);
 
    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   checkGraphNodeList(G, 3);
 
    64   checkGraphNodeList(G, 3);
 
    62   checkGraphArcList(G, 4);
 
    65   checkGraphArcList(G, 4);
 
    63 
    66 
    64   checkGraphOutArcList(G, n1, 1);
 
    67   checkGraphOutArcList(G, n1, 1);
 
    65   checkGraphOutArcList(G, n2, 3);
 
    68   checkGraphOutArcList(G, n2, 3);
 
    73 
    76 
    74   checkNodeIds(G);
 
    77   checkNodeIds(G);
 
    75   checkArcIds(G);
 
    78   checkArcIds(G);
 
    76   checkGraphNodeMap(G);
 
    79   checkGraphNodeMap(G);
 
    77   checkGraphArcMap(G);
 
    80   checkGraphArcMap(G);
 
    78 
    81 }
 
    79 }
 
    82 
    80 
    83 template <class Digraph>
 
    81 void checkFullDigraph(int num) {
 
    84 void checkDigraphSplit() {
 
    82   typedef FullDigraph Digraph;
 
    85   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 
    83   DIGRAPH_TYPEDEFS(Digraph);
 
    86 
    84   Digraph G(num);
 
    87   Digraph G;
 
    85 
    88   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
 
    86   checkGraphNodeList(G, num);
 
    89   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
 
    87   checkGraphArcList(G, num * num);
 
    90       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
 
    88 
    91 
    89   for (NodeIt n(G); n != INVALID; ++n) {
 
    92   Node n4 = G.split(n2);
 
    90     checkGraphOutArcList(G, n, num);
 
    93 
    91     checkGraphInArcList(G, n, num);
 
    94   check(G.target(OutArcIt(G, n2)) == n4 &&
 
    92   }
 
    95         G.source(InArcIt(G, n4)) == n2,
 
    93 
    96         "Wrong split.");
 
    94   checkGraphConArcList(G, num * num);
 
    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   checkNodeIds(G);
 
   275   checkNodeIds(G);
 
    97   checkArcIds(G);
 
   276   checkArcIds(G);
 
    98   checkGraphNodeMap(G);
 
   277   checkGraphNodeMap(G);
 
    99   checkGraphArcMap(G);
 
   278   checkGraphArcMap(G);
 
   100 
   279 
   101   for (int i = 0; i < G.nodeNum(); ++i) {
 
   280   G.addNode();
 
   102     check(G.index(G(i)) == i, "Wrong index");
 
   281   snapshot.save(G);
 
   103   }
 
   282 
   104 
   283   G.addArc(G.addNode(), G.addNode());
 
   105   for (NodeIt s(G); s != INVALID; ++s) {
 
   284 
   106     for (NodeIt t(G); t != INVALID; ++t) {
 
   285   snapshot.restore();
 
   107       Arc a = G.arc(s, t);
 
   286 
   108       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
 
   287   checkGraphNodeList(G, 4);
 
   109     }
 
   288   checkGraphArcList(G, 4);
 
   110   }
 
       
   111 
       
   112 }
 
   289 }
 
   113 
   290 
   114 void checkConcepts() {
 
   291 void checkConcepts() {
 
   115   { // Checking digraph components
 
   292   { // Checking digraph components
 
   116     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
 
   293     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
 
   193 
   370 
   194   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
 
   371   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
 
   195   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
 
   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 void checkDigraphs() {
 
   407 void checkDigraphs() {
 
   199   { // Checking ListDigraph
 
   408   { // Checking ListDigraph
 
   200     checkDigraph<ListDigraph>();
 
   409     checkDigraphBuild<ListDigraph>();
 
       
   410     checkDigraphSplit<ListDigraph>();
 
       
   411     checkDigraphAlter<ListDigraph>();
 
       
   412     checkDigraphErase<ListDigraph>();
 
       
   413     checkDigraphSnapshot<ListDigraph>();
 
   201     checkDigraphValidityErase<ListDigraph>();
 
   414     checkDigraphValidityErase<ListDigraph>();
 
   202   }
 
   415   }
 
   203   { // Checking SmartDigraph
 
   416   { // Checking SmartDigraph
 
   204     checkDigraph<SmartDigraph>();
 
   417     checkDigraphBuild<SmartDigraph>();
 
       
   418     checkDigraphSplit<SmartDigraph>();
 
       
   419     checkDigraphSnapshot<SmartDigraph>();
 
   205     checkDigraphValidity<SmartDigraph>();
 
   420     checkDigraphValidity<SmartDigraph>();
 
   206   }
 
   421   }
 
   207   { // Checking FullDigraph
 
   422   { // Checking FullDigraph
 
   208     checkFullDigraph(8);
 
   423     checkFullDigraph(8);
 
   209   }
 
   424   }
lemon