test/digraph_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Sun, 18 Jan 2009 17:49:08 +0100
changeset 471 fb5af0411793
parent 375 2d87dbd7f8c8
child 736 2e20aad15754
child 774 f4b5c2d5449d
child 997 761fe0846f49
permissions -rw-r--r--
Fix lp indexing bug (#205)
     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 
    64   checkGraphNodeList(G, 3);
    65   checkGraphArcList(G, 4);
    66 
    67   checkGraphOutArcList(G, n1, 1);
    68   checkGraphOutArcList(G, n2, 3);
    69   checkGraphOutArcList(G, n3, 0);
    70 
    71   checkGraphInArcList(G, n1, 1);
    72   checkGraphInArcList(G, n2, 1);
    73   checkGraphInArcList(G, n3, 2);
    74 
    75   checkGraphConArcList(G, 4);
    76 
    77   checkNodeIds(G);
    78   checkArcIds(G);
    79   checkGraphNodeMap(G);
    80   checkGraphArcMap(G);
    81 }
    82 
    83 template <class Digraph>
    84 void checkDigraphSplit() {
    85   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    86 
    87   Digraph G;
    88   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    89   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    90       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    91 
    92   Node n4 = G.split(n2);
    93 
    94   check(G.target(OutArcIt(G, n2)) == n4 &&
    95         G.source(InArcIt(G, n4)) == n2,
    96         "Wrong split.");
    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);
   274 
   275   checkNodeIds(G);
   276   checkArcIds(G);
   277   checkGraphNodeMap(G);
   278   checkGraphArcMap(G);
   279 
   280   G.addNode();
   281   snapshot.save(G);
   282 
   283   G.addArc(G.addNode(), G.addNode());
   284 
   285   snapshot.restore();
   286 
   287   checkGraphNodeList(G, 4);
   288   checkGraphArcList(G, 4);
   289 }
   290 
   291 void checkConcepts() {
   292   { // Checking digraph components
   293     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   294 
   295     checkConcept<IDableDigraphComponent<>,
   296       IDableDigraphComponent<> >();
   297 
   298     checkConcept<IterableDigraphComponent<>,
   299       IterableDigraphComponent<> >();
   300 
   301     checkConcept<MappableDigraphComponent<>,
   302       MappableDigraphComponent<> >();
   303   }
   304   { // Checking skeleton digraph
   305     checkConcept<Digraph, Digraph>();
   306   }
   307   { // Checking ListDigraph
   308     checkConcept<Digraph, ListDigraph>();
   309     checkConcept<AlterableDigraphComponent<>, ListDigraph>();
   310     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
   311     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
   312     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
   313   }
   314   { // Checking SmartDigraph
   315     checkConcept<Digraph, SmartDigraph>();
   316     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
   317     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
   318     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   319   }
   320   { // Checking FullDigraph
   321     checkConcept<Digraph, FullDigraph>();
   322   }
   323 }
   324 
   325 template <typename Digraph>
   326 void checkDigraphValidity() {
   327   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   328   Digraph g;
   329 
   330   Node
   331     n1 = g.addNode(),
   332     n2 = g.addNode(),
   333     n3 = g.addNode();
   334 
   335   Arc
   336     e1 = g.addArc(n1, n2),
   337     e2 = g.addArc(n2, n3);
   338 
   339   check(g.valid(n1), "Wrong validity check");
   340   check(g.valid(e1), "Wrong validity check");
   341 
   342   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   343   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   344 }
   345 
   346 template <typename Digraph>
   347 void checkDigraphValidityErase() {
   348   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   349   Digraph g;
   350 
   351   Node
   352     n1 = g.addNode(),
   353     n2 = g.addNode(),
   354     n3 = g.addNode();
   355 
   356   Arc
   357     e1 = g.addArc(n1, n2),
   358     e2 = g.addArc(n2, n3);
   359 
   360   check(g.valid(n1), "Wrong validity check");
   361   check(g.valid(e1), "Wrong validity check");
   362 
   363   g.erase(n1);
   364 
   365   check(!g.valid(n1), "Wrong validity check");
   366   check(g.valid(n2), "Wrong validity check");
   367   check(g.valid(n3), "Wrong validity check");
   368   check(!g.valid(e1), "Wrong validity check");
   369   check(g.valid(e2), "Wrong validity check");
   370 
   371   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   372   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   373 }
   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 
   407 void checkDigraphs() {
   408   { // Checking ListDigraph
   409     checkDigraphBuild<ListDigraph>();
   410     checkDigraphSplit<ListDigraph>();
   411     checkDigraphAlter<ListDigraph>();
   412     checkDigraphErase<ListDigraph>();
   413     checkDigraphSnapshot<ListDigraph>();
   414     checkDigraphValidityErase<ListDigraph>();
   415   }
   416   { // Checking SmartDigraph
   417     checkDigraphBuild<SmartDigraph>();
   418     checkDigraphSplit<SmartDigraph>();
   419     checkDigraphSnapshot<SmartDigraph>();
   420     checkDigraphValidity<SmartDigraph>();
   421   }
   422   { // Checking FullDigraph
   423     checkFullDigraph(8);
   424   }
   425 }
   426 
   427 int main() {
   428   checkDigraphs();
   429   checkConcepts();
   430   return 0;
   431 }