test/digraph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 06 Aug 2013 12:04:13 +0200
changeset 805 115031ac8001
parent 440 88ed40ad0d4f
child 807 3e711ee55d31
permissions -rw-r--r--
Further fixes for gcc version 3.3 and 4.3 (#470)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/concepts/digraph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
    23 
    24 #include "test_tools.h"
    25 #include "graph_test.h"
    26 
    27 using namespace lemon;
    28 using namespace lemon::concepts;
    29 
    30 template <class Digraph>
    31 void checkDigraphBuild() {
    32   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    33   Digraph G;
    34 
    35   checkGraphNodeList(G, 0);
    36   checkGraphArcList(G, 0);
    37 
    38   Node
    39     n1 = G.addNode(),
    40     n2 = G.addNode(),
    41     n3 = G.addNode();
    42   checkGraphNodeList(G, 3);
    43   checkGraphArcList(G, 0);
    44 
    45   Arc a1 = G.addArc(n1, n2);
    46   check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
    47   checkGraphNodeList(G, 3);
    48   checkGraphArcList(G, 1);
    49 
    50   checkGraphOutArcList(G, n1, 1);
    51   checkGraphOutArcList(G, n2, 0);
    52   checkGraphOutArcList(G, n3, 0);
    53 
    54   checkGraphInArcList(G, n1, 0);
    55   checkGraphInArcList(G, n2, 1);
    56   checkGraphInArcList(G, n3, 0);
    57 
    58   checkGraphConArcList(G, 1);
    59 
    60   Arc a2 = G.addArc(n2, n1),
    61       a3 = G.addArc(n2, n3),
    62       a4 = G.addArc(n2, n3);
    63   ignore_unused_variable_warning(a2,a3,a4);
    64 
    65   checkGraphNodeList(G, 3);
    66   checkGraphArcList(G, 4);
    67 
    68   checkGraphOutArcList(G, n1, 1);
    69   checkGraphOutArcList(G, n2, 3);
    70   checkGraphOutArcList(G, n3, 0);
    71 
    72   checkGraphInArcList(G, n1, 1);
    73   checkGraphInArcList(G, n2, 1);
    74   checkGraphInArcList(G, n3, 2);
    75 
    76   checkGraphConArcList(G, 4);
    77 
    78   checkNodeIds(G);
    79   checkArcIds(G);
    80   checkGraphNodeMap(G);
    81   checkGraphArcMap(G);
    82 }
    83 
    84 template <class Digraph>
    85 void checkDigraphSplit() {
    86   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    87 
    88   Digraph G;
    89   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    90   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    91       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    92   ignore_unused_variable_warning(a1,a2,a3,a4);
    93 
    94   Node n4 = G.split(n2);
    95 
    96   check(G.target(OutArcIt(G, n2)) == n4 &&
    97         G.source(InArcIt(G, n4)) == n2,
    98         "Wrong split.");
    99 
   100   checkGraphNodeList(G, 4);
   101   checkGraphArcList(G, 5);
   102 
   103   checkGraphOutArcList(G, n1, 1);
   104   checkGraphOutArcList(G, n2, 1);
   105   checkGraphOutArcList(G, n3, 0);
   106   checkGraphOutArcList(G, n4, 3);
   107 
   108   checkGraphInArcList(G, n1, 1);
   109   checkGraphInArcList(G, n2, 1);
   110   checkGraphInArcList(G, n3, 2);
   111   checkGraphInArcList(G, n4, 1);
   112 
   113   checkGraphConArcList(G, 5);
   114 }
   115 
   116 template <class Digraph>
   117 void checkDigraphAlter() {
   118   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   119 
   120   Digraph G;
   121   Node n1 = G.addNode(), n2 = G.addNode(),
   122        n3 = G.addNode(), n4 = G.addNode();
   123   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   124       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
   125       a5 = G.addArc(n2, n4);
   126   ignore_unused_variable_warning(a1,a2,a3,a5);
   127 
   128   checkGraphNodeList(G, 4);
   129   checkGraphArcList(G, 5);
   130 
   131   // Check changeSource() and changeTarget()
   132   G.changeTarget(a4, n1);
   133 
   134   checkGraphNodeList(G, 4);
   135   checkGraphArcList(G, 5);
   136 
   137   checkGraphOutArcList(G, n1, 1);
   138   checkGraphOutArcList(G, n2, 1);
   139   checkGraphOutArcList(G, n3, 0);
   140   checkGraphOutArcList(G, n4, 3);
   141 
   142   checkGraphInArcList(G, n1, 2);
   143   checkGraphInArcList(G, n2, 1);
   144   checkGraphInArcList(G, n3, 1);
   145   checkGraphInArcList(G, n4, 1);
   146 
   147   checkGraphConArcList(G, 5);
   148 
   149   G.changeSource(a4, n3);
   150 
   151   checkGraphNodeList(G, 4);
   152   checkGraphArcList(G, 5);
   153 
   154   checkGraphOutArcList(G, n1, 1);
   155   checkGraphOutArcList(G, n2, 1);
   156   checkGraphOutArcList(G, n3, 1);
   157   checkGraphOutArcList(G, n4, 2);
   158 
   159   checkGraphInArcList(G, n1, 2);
   160   checkGraphInArcList(G, n2, 1);
   161   checkGraphInArcList(G, n3, 1);
   162   checkGraphInArcList(G, n4, 1);
   163 
   164   checkGraphConArcList(G, 5);
   165 
   166   // Check contract()
   167   G.contract(n2, n4, false);
   168 
   169   checkGraphNodeList(G, 3);
   170   checkGraphArcList(G, 5);
   171 
   172   checkGraphOutArcList(G, n1, 1);
   173   checkGraphOutArcList(G, n2, 3);
   174   checkGraphOutArcList(G, n3, 1);
   175 
   176   checkGraphInArcList(G, n1, 2);
   177   checkGraphInArcList(G, n2, 2);
   178   checkGraphInArcList(G, n3, 1);
   179 
   180   checkGraphConArcList(G, 5);
   181 
   182   G.contract(n2, n1);
   183 
   184   checkGraphNodeList(G, 2);
   185   checkGraphArcList(G, 3);
   186 
   187   checkGraphOutArcList(G, n2, 2);
   188   checkGraphOutArcList(G, n3, 1);
   189 
   190   checkGraphInArcList(G, n2, 2);
   191   checkGraphInArcList(G, n3, 1);
   192 
   193   checkGraphConArcList(G, 3);
   194 }
   195 
   196 template <class Digraph>
   197 void checkDigraphErase() {
   198   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   199 
   200   Digraph G;
   201   Node n1 = G.addNode(), n2 = G.addNode(),
   202        n3 = G.addNode(), n4 = G.addNode();
   203   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   204       a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
   205       a5 = G.addArc(n2, n4);
   206   ignore_unused_variable_warning(a2,a3,a4,a5);
   207 
   208   // Check arc deletion
   209   G.erase(a1);
   210 
   211   checkGraphNodeList(G, 4);
   212   checkGraphArcList(G, 4);
   213 
   214   checkGraphOutArcList(G, n1, 0);
   215   checkGraphOutArcList(G, n2, 1);
   216   checkGraphOutArcList(G, n3, 1);
   217   checkGraphOutArcList(G, n4, 2);
   218 
   219   checkGraphInArcList(G, n1, 2);
   220   checkGraphInArcList(G, n2, 0);
   221   checkGraphInArcList(G, n3, 1);
   222   checkGraphInArcList(G, n4, 1);
   223 
   224   checkGraphConArcList(G, 4);
   225 
   226   // Check node deletion
   227   G.erase(n4);
   228 
   229   checkGraphNodeList(G, 3);
   230   checkGraphArcList(G, 1);
   231 
   232   checkGraphOutArcList(G, n1, 0);
   233   checkGraphOutArcList(G, n2, 0);
   234   checkGraphOutArcList(G, n3, 1);
   235   checkGraphOutArcList(G, n4, 0);
   236 
   237   checkGraphInArcList(G, n1, 1);
   238   checkGraphInArcList(G, n2, 0);
   239   checkGraphInArcList(G, n3, 0);
   240   checkGraphInArcList(G, n4, 0);
   241 
   242   checkGraphConArcList(G, 1);
   243 }
   244 
   245 
   246 template <class Digraph>
   247 void checkDigraphSnapshot() {
   248   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   249 
   250   Digraph G;
   251   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   252   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
   253       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
   254   ignore_unused_variable_warning(a1,a2,a3,a4);
   255 
   256   typename Digraph::Snapshot snapshot(G);
   257 
   258   Node n = G.addNode();
   259   G.addArc(n3, n);
   260   G.addArc(n, n3);
   261 
   262   checkGraphNodeList(G, 4);
   263   checkGraphArcList(G, 6);
   264 
   265   snapshot.restore();
   266 
   267   checkGraphNodeList(G, 3);
   268   checkGraphArcList(G, 4);
   269 
   270   checkGraphOutArcList(G, n1, 1);
   271   checkGraphOutArcList(G, n2, 3);
   272   checkGraphOutArcList(G, n3, 0);
   273 
   274   checkGraphInArcList(G, n1, 1);
   275   checkGraphInArcList(G, n2, 1);
   276   checkGraphInArcList(G, n3, 2);
   277 
   278   checkGraphConArcList(G, 4);
   279 
   280   checkNodeIds(G);
   281   checkArcIds(G);
   282   checkGraphNodeMap(G);
   283   checkGraphArcMap(G);
   284 
   285   G.addNode();
   286   snapshot.save(G);
   287 
   288   G.addArc(G.addNode(), G.addNode());
   289 
   290   snapshot.restore();
   291 
   292   checkGraphNodeList(G, 4);
   293   checkGraphArcList(G, 4);
   294 }
   295 
   296 void checkConcepts() {
   297   { // Checking digraph components
   298     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   299 
   300     checkConcept<IDableDigraphComponent<>,
   301       IDableDigraphComponent<> >();
   302 
   303     checkConcept<IterableDigraphComponent<>,
   304       IterableDigraphComponent<> >();
   305 
   306     checkConcept<MappableDigraphComponent<>,
   307       MappableDigraphComponent<> >();
   308   }
   309   { // Checking skeleton digraph
   310     checkConcept<Digraph, Digraph>();
   311   }
   312   { // Checking ListDigraph
   313     checkConcept<Digraph, ListDigraph>();
   314     checkConcept<AlterableDigraphComponent<>, ListDigraph>();
   315     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
   316     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
   317     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
   318   }
   319   { // Checking SmartDigraph
   320     checkConcept<Digraph, SmartDigraph>();
   321     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
   322     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
   323     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   324   }
   325   { // Checking FullDigraph
   326     checkConcept<Digraph, FullDigraph>();
   327   }
   328 }
   329 
   330 template <typename Digraph>
   331 void checkDigraphValidity() {
   332   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   333   Digraph g;
   334 
   335   Node
   336     n1 = g.addNode(),
   337     n2 = g.addNode(),
   338     n3 = g.addNode();
   339 
   340   Arc
   341     e1 = g.addArc(n1, n2),
   342     e2 = g.addArc(n2, n3);
   343   ignore_unused_variable_warning(e2);
   344 
   345   check(g.valid(n1), "Wrong validity check");
   346   check(g.valid(e1), "Wrong validity check");
   347 
   348   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   349   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   350 }
   351 
   352 template <typename Digraph>
   353 void checkDigraphValidityErase() {
   354   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   355   Digraph g;
   356 
   357   Node
   358     n1 = g.addNode(),
   359     n2 = g.addNode(),
   360     n3 = g.addNode();
   361 
   362   Arc
   363     e1 = g.addArc(n1, n2),
   364     e2 = g.addArc(n2, n3);
   365 
   366   check(g.valid(n1), "Wrong validity check");
   367   check(g.valid(e1), "Wrong validity check");
   368 
   369   g.erase(n1);
   370 
   371   check(!g.valid(n1), "Wrong validity check");
   372   check(g.valid(n2), "Wrong validity check");
   373   check(g.valid(n3), "Wrong validity check");
   374   check(!g.valid(e1), "Wrong validity check");
   375   check(g.valid(e2), "Wrong validity check");
   376 
   377   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   378   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   379 }
   380 
   381 void checkFullDigraph(int num) {
   382   typedef FullDigraph Digraph;
   383   DIGRAPH_TYPEDEFS(Digraph);
   384   Digraph G(num);
   385 
   386   checkGraphNodeList(G, num);
   387   checkGraphArcList(G, num * num);
   388 
   389   for (NodeIt n(G); n != INVALID; ++n) {
   390     checkGraphOutArcList(G, n, num);
   391     checkGraphInArcList(G, n, num);
   392   }
   393 
   394   checkGraphConArcList(G, num * num);
   395 
   396   checkNodeIds(G);
   397   checkArcIds(G);
   398   checkGraphNodeMap(G);
   399   checkGraphArcMap(G);
   400 
   401   for (int i = 0; i < G.nodeNum(); ++i) {
   402     check(G.index(G(i)) == i, "Wrong index");
   403   }
   404 
   405   for (NodeIt s(G); s != INVALID; ++s) {
   406     for (NodeIt t(G); t != INVALID; ++t) {
   407       Arc a = G.arc(s, t);
   408       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
   409     }
   410   }
   411 }
   412 
   413 void checkDigraphs() {
   414   { // Checking ListDigraph
   415     checkDigraphBuild<ListDigraph>();
   416     checkDigraphSplit<ListDigraph>();
   417     checkDigraphAlter<ListDigraph>();
   418     checkDigraphErase<ListDigraph>();
   419     checkDigraphSnapshot<ListDigraph>();
   420     checkDigraphValidityErase<ListDigraph>();
   421   }
   422   { // Checking SmartDigraph
   423     checkDigraphBuild<SmartDigraph>();
   424     checkDigraphSplit<SmartDigraph>();
   425     checkDigraphSnapshot<SmartDigraph>();
   426     checkDigraphValidity<SmartDigraph>();
   427   }
   428   { // Checking FullDigraph
   429     checkFullDigraph(8);
   430   }
   431 }
   432 
   433 int main() {
   434   checkDigraphs();
   435   checkConcepts();
   436   return 0;
   437 }