test/digraph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 12 Dec 2008 21:52:53 +0000
branch1.0
changeset 350 d5cfcff85dfd
parent 228 b6732e0d38c5
permissions -rw-r--r--
Merge bugfix #195
     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-2008
     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 //#include <lemon/hypercube_graph.h>
    24 
    25 #include "test_tools.h"
    26 #include "graph_test.h"
    27 
    28 using namespace lemon;
    29 using namespace lemon::concepts;
    30 
    31 template <class Digraph>
    32 void checkDigraphBuild() {
    33   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    34   Digraph G;
    35 
    36   checkGraphNodeList(G, 0);
    37   checkGraphArcList(G, 0);
    38 
    39   Node
    40     n1 = G.addNode(),
    41     n2 = G.addNode(),
    42     n3 = G.addNode();
    43   checkGraphNodeList(G, 3);
    44   checkGraphArcList(G, 0);
    45 
    46   Arc a1 = G.addArc(n1, n2);
    47   check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");
    48   checkGraphNodeList(G, 3);
    49   checkGraphArcList(G, 1);
    50 
    51   checkGraphOutArcList(G, n1, 1);
    52   checkGraphOutArcList(G, n2, 0);
    53   checkGraphOutArcList(G, n3, 0);
    54 
    55   checkGraphInArcList(G, n1, 0);
    56   checkGraphInArcList(G, n2, 1);
    57   checkGraphInArcList(G, n3, 0);
    58 
    59   checkGraphConArcList(G, 1);
    60 
    61   Arc a2 = G.addArc(n2, n1),
    62       a3 = G.addArc(n2, n3),
    63       a4 = G.addArc(n2, n3);
    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 
    93   Node n4 = G.split(n2);
    94 
    95   check(G.target(OutArcIt(G, n2)) == n4 &&
    96         G.source(InArcIt(G, n4)) == n2,
    97         "Wrong split.");
    98 
    99   checkGraphNodeList(G, 4);
   100   checkGraphArcList(G, 5);
   101 
   102   checkGraphOutArcList(G, n1, 1);
   103   checkGraphOutArcList(G, n2, 1);
   104   checkGraphOutArcList(G, n3, 0);
   105   checkGraphOutArcList(G, n4, 3);
   106 
   107   checkGraphInArcList(G, n1, 1);
   108   checkGraphInArcList(G, n2, 1);
   109   checkGraphInArcList(G, n3, 2);
   110   checkGraphInArcList(G, n4, 1);
   111 
   112   checkGraphConArcList(G, 5);
   113 }
   114 
   115 template <class Digraph>
   116 void checkDigraphAlter() {
   117   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   118 
   119   Digraph G;
   120   Node n1 = G.addNode(), n2 = G.addNode(),
   121        n3 = G.addNode(), n4 = G.addNode();
   122   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   123       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
   124       a5 = G.addArc(n2, n4);
   125 
   126   checkGraphNodeList(G, 4);
   127   checkGraphArcList(G, 5);
   128 
   129   // Check changeSource() and changeTarget()
   130   G.changeTarget(a4, n1);
   131 
   132   checkGraphNodeList(G, 4);
   133   checkGraphArcList(G, 5);
   134 
   135   checkGraphOutArcList(G, n1, 1);
   136   checkGraphOutArcList(G, n2, 1);
   137   checkGraphOutArcList(G, n3, 0);
   138   checkGraphOutArcList(G, n4, 3);
   139 
   140   checkGraphInArcList(G, n1, 2);
   141   checkGraphInArcList(G, n2, 1);
   142   checkGraphInArcList(G, n3, 1);
   143   checkGraphInArcList(G, n4, 1);
   144 
   145   checkGraphConArcList(G, 5);
   146 
   147   G.changeSource(a4, n3);
   148 
   149   checkGraphNodeList(G, 4);
   150   checkGraphArcList(G, 5);
   151 
   152   checkGraphOutArcList(G, n1, 1);
   153   checkGraphOutArcList(G, n2, 1);
   154   checkGraphOutArcList(G, n3, 1);
   155   checkGraphOutArcList(G, n4, 2);
   156 
   157   checkGraphInArcList(G, n1, 2);
   158   checkGraphInArcList(G, n2, 1);
   159   checkGraphInArcList(G, n3, 1);
   160   checkGraphInArcList(G, n4, 1);
   161 
   162   checkGraphConArcList(G, 5);
   163 
   164   // Check contract()
   165   G.contract(n2, n4, false);
   166 
   167   checkGraphNodeList(G, 3);
   168   checkGraphArcList(G, 5);
   169 
   170   checkGraphOutArcList(G, n1, 1);
   171   checkGraphOutArcList(G, n2, 3);
   172   checkGraphOutArcList(G, n3, 1);
   173 
   174   checkGraphInArcList(G, n1, 2);
   175   checkGraphInArcList(G, n2, 2);
   176   checkGraphInArcList(G, n3, 1);
   177 
   178   checkGraphConArcList(G, 5);
   179 
   180   G.contract(n2, n1);
   181 
   182   checkGraphNodeList(G, 2);
   183   checkGraphArcList(G, 3);
   184 
   185   checkGraphOutArcList(G, n2, 2);
   186   checkGraphOutArcList(G, n3, 1);
   187 
   188   checkGraphInArcList(G, n2, 2);
   189   checkGraphInArcList(G, n3, 1);
   190 
   191   checkGraphConArcList(G, 3);
   192 }
   193 
   194 template <class Digraph>
   195 void checkDigraphErase() {
   196   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   197 
   198   Digraph G;
   199   Node n1 = G.addNode(), n2 = G.addNode(),
   200        n3 = G.addNode(), n4 = G.addNode();
   201   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   202       a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
   203       a5 = G.addArc(n2, n4);
   204 
   205   // Check arc deletion
   206   G.erase(a1);
   207 
   208   checkGraphNodeList(G, 4);
   209   checkGraphArcList(G, 4);
   210 
   211   checkGraphOutArcList(G, n1, 0);
   212   checkGraphOutArcList(G, n2, 1);
   213   checkGraphOutArcList(G, n3, 1);
   214   checkGraphOutArcList(G, n4, 2);
   215 
   216   checkGraphInArcList(G, n1, 2);
   217   checkGraphInArcList(G, n2, 0);
   218   checkGraphInArcList(G, n3, 1);
   219   checkGraphInArcList(G, n4, 1);
   220 
   221   checkGraphConArcList(G, 4);
   222 
   223   // Check node deletion
   224   G.erase(n4);
   225 
   226   checkGraphNodeList(G, 3);
   227   checkGraphArcList(G, 1);
   228 
   229   checkGraphOutArcList(G, n1, 0);
   230   checkGraphOutArcList(G, n2, 0);
   231   checkGraphOutArcList(G, n3, 1);
   232   checkGraphOutArcList(G, n4, 0);
   233 
   234   checkGraphInArcList(G, n1, 1);
   235   checkGraphInArcList(G, n2, 0);
   236   checkGraphInArcList(G, n3, 0);
   237   checkGraphInArcList(G, n4, 0);
   238 
   239   checkGraphConArcList(G, 1);
   240 }
   241 
   242 
   243 template <class Digraph>
   244 void checkDigraphSnapshot() {
   245   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   246 
   247   Digraph G;
   248   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   249   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
   250       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
   251 
   252   typename Digraph::Snapshot snapshot(G);
   253 
   254   Node n = G.addNode();
   255   G.addArc(n3, n);
   256   G.addArc(n, n3);
   257 
   258   checkGraphNodeList(G, 4);
   259   checkGraphArcList(G, 6);
   260 
   261   snapshot.restore();
   262 
   263   checkGraphNodeList(G, 3);
   264   checkGraphArcList(G, 4);
   265 
   266   checkGraphOutArcList(G, n1, 1);
   267   checkGraphOutArcList(G, n2, 3);
   268   checkGraphOutArcList(G, n3, 0);
   269 
   270   checkGraphInArcList(G, n1, 1);
   271   checkGraphInArcList(G, n2, 1);
   272   checkGraphInArcList(G, n3, 2);
   273 
   274   checkGraphConArcList(G, 4);
   275 
   276   checkNodeIds(G);
   277   checkArcIds(G);
   278   checkGraphNodeMap(G);
   279   checkGraphArcMap(G);
   280 
   281   G.addNode();
   282   snapshot.save(G);
   283 
   284   G.addArc(G.addNode(), G.addNode());
   285 
   286   snapshot.restore();
   287 
   288   checkGraphNodeList(G, 4);
   289   checkGraphArcList(G, 4);
   290 }
   291 
   292 void checkConcepts() {
   293   { // Checking digraph components
   294     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   295 
   296     checkConcept<IDableDigraphComponent<>,
   297       IDableDigraphComponent<> >();
   298 
   299     checkConcept<IterableDigraphComponent<>,
   300       IterableDigraphComponent<> >();
   301 
   302     checkConcept<MappableDigraphComponent<>,
   303       MappableDigraphComponent<> >();
   304   }
   305   { // Checking skeleton digraph
   306     checkConcept<Digraph, Digraph>();
   307   }
   308   { // Checking ListDigraph
   309     checkConcept<Digraph, ListDigraph>();
   310     checkConcept<AlterableDigraphComponent<>, ListDigraph>();
   311     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
   312     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
   313     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
   314   }
   315   { // Checking SmartDigraph
   316     checkConcept<Digraph, SmartDigraph>();
   317     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
   318     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
   319     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   320   }
   321 //  { // Checking FullDigraph
   322 //    checkConcept<Digraph, FullDigraph>();
   323 //  }
   324 //  { // Checking HyperCubeDigraph
   325 //    checkConcept<Digraph, HyperCubeDigraph>();
   326 //  }
   327 }
   328 
   329 template <typename Digraph>
   330 void checkDigraphValidity() {
   331   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   332   Digraph g;
   333 
   334   Node
   335     n1 = g.addNode(),
   336     n2 = g.addNode(),
   337     n3 = g.addNode();
   338 
   339   Arc
   340     e1 = g.addArc(n1, n2),
   341     e2 = g.addArc(n2, n3);
   342 
   343   check(g.valid(n1), "Wrong validity check");
   344   check(g.valid(e1), "Wrong validity check");
   345 
   346   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   347   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   348 }
   349 
   350 template <typename Digraph>
   351 void checkDigraphValidityErase() {
   352   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   353   Digraph g;
   354 
   355   Node
   356     n1 = g.addNode(),
   357     n2 = g.addNode(),
   358     n3 = g.addNode();
   359 
   360   Arc
   361     e1 = g.addArc(n1, n2),
   362     e2 = g.addArc(n2, n3);
   363 
   364   check(g.valid(n1), "Wrong validity check");
   365   check(g.valid(e1), "Wrong validity check");
   366 
   367   g.erase(n1);
   368 
   369   check(!g.valid(n1), "Wrong validity check");
   370   check(g.valid(n2), "Wrong validity check");
   371   check(g.valid(n3), "Wrong validity check");
   372   check(!g.valid(e1), "Wrong validity check");
   373   check(g.valid(e2), "Wrong validity check");
   374 
   375   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   376   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   377 }
   378 
   379 void checkDigraphs() {
   380   { // Checking ListDigraph
   381     checkDigraphBuild<ListDigraph>();
   382     checkDigraphSplit<ListDigraph>();
   383     checkDigraphAlter<ListDigraph>();
   384     checkDigraphErase<ListDigraph>();
   385     checkDigraphSnapshot<ListDigraph>();
   386     checkDigraphValidityErase<ListDigraph>();
   387   }
   388   { // Checking SmartDigraph
   389     checkDigraphBuild<SmartDigraph>();
   390     checkDigraphSplit<SmartDigraph>();
   391     checkDigraphSnapshot<SmartDigraph>();
   392     checkDigraphValidity<SmartDigraph>();
   393   }
   394 }
   395 
   396 int main() {
   397   checkDigraphs();
   398   checkConcepts();
   399   return 0;
   400 }