test/digraph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 05 Nov 2009 06:26:18 +0100
changeset 757 9fbbd802020f
parent 737 9d6c3e8b2421
child 780 580af8cf2f6a
permissions -rw-r--r--
Merge #184
     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   G.reserveNode(3);
    39   G.reserveArc(4);
    40 
    41   Node
    42     n1 = G.addNode(),
    43     n2 = G.addNode(),
    44     n3 = G.addNode();
    45   checkGraphNodeList(G, 3);
    46   checkGraphArcList(G, 0);
    47 
    48   Arc a1 = G.addArc(n1, n2);
    49   check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
    50   checkGraphNodeList(G, 3);
    51   checkGraphArcList(G, 1);
    52 
    53   checkGraphOutArcList(G, n1, 1);
    54   checkGraphOutArcList(G, n2, 0);
    55   checkGraphOutArcList(G, n3, 0);
    56 
    57   checkGraphInArcList(G, n1, 0);
    58   checkGraphInArcList(G, n2, 1);
    59   checkGraphInArcList(G, n3, 0);
    60 
    61   checkGraphConArcList(G, 1);
    62 
    63   Arc a2 = G.addArc(n2, n1),
    64       a3 = G.addArc(n2, n3),
    65       a4 = G.addArc(n2, n3);
    66 
    67   checkGraphNodeList(G, 3);
    68   checkGraphArcList(G, 4);
    69 
    70   checkGraphOutArcList(G, n1, 1);
    71   checkGraphOutArcList(G, n2, 3);
    72   checkGraphOutArcList(G, n3, 0);
    73 
    74   checkGraphInArcList(G, n1, 1);
    75   checkGraphInArcList(G, n2, 1);
    76   checkGraphInArcList(G, n3, 2);
    77 
    78   checkGraphConArcList(G, 4);
    79 
    80   checkNodeIds(G);
    81   checkArcIds(G);
    82   checkGraphNodeMap(G);
    83   checkGraphArcMap(G);
    84 }
    85 
    86 template <class Digraph>
    87 void checkDigraphSplit() {
    88   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    89 
    90   Digraph G;
    91   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    92   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    93       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    94 
    95   Node n4 = G.split(n2);
    96 
    97   check(G.target(OutArcIt(G, n2)) == n4 &&
    98         G.source(InArcIt(G, n4)) == n2,
    99         "Wrong split.");
   100 
   101   checkGraphNodeList(G, 4);
   102   checkGraphArcList(G, 5);
   103 
   104   checkGraphOutArcList(G, n1, 1);
   105   checkGraphOutArcList(G, n2, 1);
   106   checkGraphOutArcList(G, n3, 0);
   107   checkGraphOutArcList(G, n4, 3);
   108 
   109   checkGraphInArcList(G, n1, 1);
   110   checkGraphInArcList(G, n2, 1);
   111   checkGraphInArcList(G, n3, 2);
   112   checkGraphInArcList(G, n4, 1);
   113 
   114   checkGraphConArcList(G, 5);
   115 }
   116 
   117 template <class Digraph>
   118 void checkDigraphAlter() {
   119   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   120 
   121   Digraph G;
   122   Node n1 = G.addNode(), n2 = G.addNode(),
   123        n3 = G.addNode(), n4 = G.addNode();
   124   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   125       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
   126       a5 = G.addArc(n2, n4);
   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 
   207   // Check arc deletion
   208   G.erase(a1);
   209 
   210   checkGraphNodeList(G, 4);
   211   checkGraphArcList(G, 4);
   212 
   213   checkGraphOutArcList(G, n1, 0);
   214   checkGraphOutArcList(G, n2, 1);
   215   checkGraphOutArcList(G, n3, 1);
   216   checkGraphOutArcList(G, n4, 2);
   217 
   218   checkGraphInArcList(G, n1, 2);
   219   checkGraphInArcList(G, n2, 0);
   220   checkGraphInArcList(G, n3, 1);
   221   checkGraphInArcList(G, n4, 1);
   222 
   223   checkGraphConArcList(G, 4);
   224 
   225   // Check node deletion
   226   G.erase(n4);
   227 
   228   checkGraphNodeList(G, 3);
   229   checkGraphArcList(G, 1);
   230 
   231   checkGraphOutArcList(G, n1, 0);
   232   checkGraphOutArcList(G, n2, 0);
   233   checkGraphOutArcList(G, n3, 1);
   234   checkGraphOutArcList(G, n4, 0);
   235 
   236   checkGraphInArcList(G, n1, 1);
   237   checkGraphInArcList(G, n2, 0);
   238   checkGraphInArcList(G, n3, 0);
   239   checkGraphInArcList(G, n4, 0);
   240 
   241   checkGraphConArcList(G, 1);
   242 }
   243 
   244 
   245 template <class Digraph>
   246 void checkDigraphSnapshot() {
   247   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   248 
   249   Digraph G;
   250   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   251   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
   252       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
   253 
   254   typename Digraph::Snapshot snapshot(G);
   255 
   256   Node n = G.addNode();
   257   G.addArc(n3, n);
   258   G.addArc(n, n3);
   259 
   260   checkGraphNodeList(G, 4);
   261   checkGraphArcList(G, 6);
   262 
   263   snapshot.restore();
   264 
   265   checkGraphNodeList(G, 3);
   266   checkGraphArcList(G, 4);
   267 
   268   checkGraphOutArcList(G, n1, 1);
   269   checkGraphOutArcList(G, n2, 3);
   270   checkGraphOutArcList(G, n3, 0);
   271 
   272   checkGraphInArcList(G, n1, 1);
   273   checkGraphInArcList(G, n2, 1);
   274   checkGraphInArcList(G, n3, 2);
   275 
   276   checkGraphConArcList(G, 4);
   277 
   278   checkNodeIds(G);
   279   checkArcIds(G);
   280   checkGraphNodeMap(G);
   281   checkGraphArcMap(G);
   282 
   283   G.addNode();
   284   snapshot.save(G);
   285 
   286   G.addArc(G.addNode(), G.addNode());
   287 
   288   snapshot.restore();
   289   snapshot.save(G);
   290 
   291   checkGraphNodeList(G, 4);
   292   checkGraphArcList(G, 4);
   293 
   294   G.addArc(G.addNode(), G.addNode());
   295 
   296   snapshot.restore();
   297 
   298   checkGraphNodeList(G, 4);
   299   checkGraphArcList(G, 4);
   300 }
   301 
   302 void checkConcepts() {
   303   { // Checking digraph components
   304     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   305 
   306     checkConcept<IDableDigraphComponent<>,
   307       IDableDigraphComponent<> >();
   308 
   309     checkConcept<IterableDigraphComponent<>,
   310       IterableDigraphComponent<> >();
   311 
   312     checkConcept<MappableDigraphComponent<>,
   313       MappableDigraphComponent<> >();
   314   }
   315   { // Checking skeleton digraph
   316     checkConcept<Digraph, Digraph>();
   317   }
   318   { // Checking ListDigraph
   319     checkConcept<Digraph, ListDigraph>();
   320     checkConcept<AlterableDigraphComponent<>, ListDigraph>();
   321     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
   322     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
   323     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
   324   }
   325   { // Checking SmartDigraph
   326     checkConcept<Digraph, SmartDigraph>();
   327     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
   328     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
   329     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   330   }
   331   { // Checking FullDigraph
   332     checkConcept<Digraph, FullDigraph>();
   333   }
   334 }
   335 
   336 template <typename Digraph>
   337 void checkDigraphValidity() {
   338   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   339   Digraph g;
   340 
   341   Node
   342     n1 = g.addNode(),
   343     n2 = g.addNode(),
   344     n3 = g.addNode();
   345 
   346   Arc
   347     e1 = g.addArc(n1, n2),
   348     e2 = g.addArc(n2, n3);
   349 
   350   check(g.valid(n1), "Wrong validity check");
   351   check(g.valid(e1), "Wrong validity check");
   352 
   353   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   354   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   355 }
   356 
   357 template <typename Digraph>
   358 void checkDigraphValidityErase() {
   359   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   360   Digraph g;
   361 
   362   Node
   363     n1 = g.addNode(),
   364     n2 = g.addNode(),
   365     n3 = g.addNode();
   366 
   367   Arc
   368     e1 = g.addArc(n1, n2),
   369     e2 = g.addArc(n2, n3);
   370 
   371   check(g.valid(n1), "Wrong validity check");
   372   check(g.valid(e1), "Wrong validity check");
   373 
   374   g.erase(n1);
   375 
   376   check(!g.valid(n1), "Wrong validity check");
   377   check(g.valid(n2), "Wrong validity check");
   378   check(g.valid(n3), "Wrong validity check");
   379   check(!g.valid(e1), "Wrong validity check");
   380   check(g.valid(e2), "Wrong validity check");
   381 
   382   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   383   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   384 }
   385 
   386 void checkFullDigraph(int num) {
   387   typedef FullDigraph Digraph;
   388   DIGRAPH_TYPEDEFS(Digraph);
   389 
   390   Digraph G(num);
   391   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
   392 
   393   G.resize(num);
   394   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
   395 
   396   checkGraphNodeList(G, num);
   397   checkGraphArcList(G, num * num);
   398 
   399   for (NodeIt n(G); n != INVALID; ++n) {
   400     checkGraphOutArcList(G, n, num);
   401     checkGraphInArcList(G, n, num);
   402   }
   403 
   404   checkGraphConArcList(G, num * num);
   405 
   406   checkNodeIds(G);
   407   checkArcIds(G);
   408   checkGraphNodeMap(G);
   409   checkGraphArcMap(G);
   410 
   411   for (int i = 0; i < G.nodeNum(); ++i) {
   412     check(G.index(G(i)) == i, "Wrong index");
   413   }
   414 
   415   for (NodeIt s(G); s != INVALID; ++s) {
   416     for (NodeIt t(G); t != INVALID; ++t) {
   417       Arc a = G.arc(s, t);
   418       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
   419     }
   420   }
   421 }
   422 
   423 void checkDigraphs() {
   424   { // Checking ListDigraph
   425     checkDigraphBuild<ListDigraph>();
   426     checkDigraphSplit<ListDigraph>();
   427     checkDigraphAlter<ListDigraph>();
   428     checkDigraphErase<ListDigraph>();
   429     checkDigraphSnapshot<ListDigraph>();
   430     checkDigraphValidityErase<ListDigraph>();
   431   }
   432   { // Checking SmartDigraph
   433     checkDigraphBuild<SmartDigraph>();
   434     checkDigraphSplit<SmartDigraph>();
   435     checkDigraphSnapshot<SmartDigraph>();
   436     checkDigraphValidity<SmartDigraph>();
   437   }
   438   { // Checking FullDigraph
   439     checkFullDigraph(8);
   440   }
   441 }
   442 
   443 int main() {
   444   checkDigraphs();
   445   checkConcepts();
   446   return 0;
   447 }