lemon: test/digraph_test.cc@1c247d3e4bbd

     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  */

    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>

    25 #include "test_tools.h"

    26 #include "graph_test.h"

    28 using namespace lemon;

    29 using namespace lemon::concepts;

    31 template <class Digraph>

    32 void checkDigraphBuild() {

    33   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    34   Digraph G;

    36   checkGraphNodeList(G, 0);

    37   checkGraphArcList(G, 0);

    39   Node

    40     n1 = G.addNode(),

    41     n2 = G.addNode(),

    42     n3 = G.addNode();

    43   checkGraphNodeList(G, 3);

    44   checkGraphArcList(G, 0);

    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);

    51   checkGraphOutArcList(G, n1, 1);

    52   checkGraphOutArcList(G, n2, 0);

    53   checkGraphOutArcList(G, n3, 0);

    55   checkGraphInArcList(G, n1, 0);

    56   checkGraphInArcList(G, n2, 1);

    57   checkGraphInArcList(G, n3, 0);

    59   checkGraphConArcList(G, 1);

    61   Arc a2 = G.addArc(n2, n1),

    62       a3 = G.addArc(n2, n3),

    63       a4 = G.addArc(n2, n3);

    65   checkGraphNodeList(G, 3);

    66   checkGraphArcList(G, 4);

    68   checkGraphOutArcList(G, n1, 1);

    69   checkGraphOutArcList(G, n2, 3);

    70   checkGraphOutArcList(G, n3, 0);

    72   checkGraphInArcList(G, n1, 1);

    73   checkGraphInArcList(G, n2, 1);

    74   checkGraphInArcList(G, n3, 2);

    76   checkGraphConArcList(G, 4);

    78   checkNodeIds(G);

    79   checkArcIds(G);

    80   checkGraphNodeMap(G);

    81   checkGraphArcMap(G);

    82 }

    84 template <class Digraph>

    85 void checkDigraphSplit() {

    86   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    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);

    93   Node n4 = G.split(n2);

    95   check(G.target(OutArcIt(G, n2)) == n4 &&

    96         G.source(InArcIt(G, n4)) == n2,

    97         "Wrong split.");

    99   checkGraphNodeList(G, 4);

   100   checkGraphArcList(G, 5);

   102   checkGraphOutArcList(G, n1, 1);

   103   checkGraphOutArcList(G, n2, 1);

   104   checkGraphOutArcList(G, n3, 0);

   105   checkGraphOutArcList(G, n4, 3);

   107   checkGraphInArcList(G, n1, 1);

   108   checkGraphInArcList(G, n2, 1);

   109   checkGraphInArcList(G, n3, 2);

   110   checkGraphInArcList(G, n4, 1);

   112   checkGraphConArcList(G, 5);

   113 }

   115 template <class Digraph>

   116 void checkDigraphAlter() {

   117   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   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);

   126   checkGraphNodeList(G, 4);

   127   checkGraphArcList(G, 5);

   129   // Check changeSource() and changeTarget()

   130   G.changeTarget(a4, n1);

   132   checkGraphNodeList(G, 4);

   133   checkGraphArcList(G, 5);

   135   checkGraphOutArcList(G, n1, 1);

   136   checkGraphOutArcList(G, n2, 1);

   137   checkGraphOutArcList(G, n3, 0);

   138   checkGraphOutArcList(G, n4, 3);

   140   checkGraphInArcList(G, n1, 2);

   141   checkGraphInArcList(G, n2, 1);

   142   checkGraphInArcList(G, n3, 1);

   143   checkGraphInArcList(G, n4, 1);

   145   checkGraphConArcList(G, 5);

   147   G.changeSource(a4, n3);

   149   checkGraphNodeList(G, 4);

   150   checkGraphArcList(G, 5);

   152   checkGraphOutArcList(G, n1, 1);

   153   checkGraphOutArcList(G, n2, 1);

   154   checkGraphOutArcList(G, n3, 1);

   155   checkGraphOutArcList(G, n4, 2);

   157   checkGraphInArcList(G, n1, 2);

   158   checkGraphInArcList(G, n2, 1);

   159   checkGraphInArcList(G, n3, 1);

   160   checkGraphInArcList(G, n4, 1);

   162   checkGraphConArcList(G, 5);

   164   // Check contract()

   165   G.contract(n2, n4, false);

   167   checkGraphNodeList(G, 3);

   168   checkGraphArcList(G, 5);

   170   checkGraphOutArcList(G, n1, 1);

   171   checkGraphOutArcList(G, n2, 3);

   172   checkGraphOutArcList(G, n3, 1);

   174   checkGraphInArcList(G, n1, 2);

   175   checkGraphInArcList(G, n2, 2);

   176   checkGraphInArcList(G, n3, 1);

   178   checkGraphConArcList(G, 5);

   180   G.contract(n2, n1);

   182   checkGraphNodeList(G, 2);

   183   checkGraphArcList(G, 3);

   185   checkGraphOutArcList(G, n2, 2);

   186   checkGraphOutArcList(G, n3, 1);

   188   checkGraphInArcList(G, n2, 2);

   189   checkGraphInArcList(G, n3, 1);

   191   checkGraphConArcList(G, 3);

   192 }

   194 template <class Digraph>

   195 void checkDigraphErase() {

   196   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   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);

   205   // Check arc deletion

   206   G.erase(a1);

   208   checkGraphNodeList(G, 4);

   209   checkGraphArcList(G, 4);

   211   checkGraphOutArcList(G, n1, 0);

   212   checkGraphOutArcList(G, n2, 1);

   213   checkGraphOutArcList(G, n3, 1);

   214   checkGraphOutArcList(G, n4, 2);

   216   checkGraphInArcList(G, n1, 2);

   217   checkGraphInArcList(G, n2, 0);

   218   checkGraphInArcList(G, n3, 1);

   219   checkGraphInArcList(G, n4, 1);

   221   checkGraphConArcList(G, 4);

   223   // Check node deletion

   224   G.erase(n4);

   226   checkGraphNodeList(G, 3);

   227   checkGraphArcList(G, 1);

   229   checkGraphOutArcList(G, n1, 0);

   230   checkGraphOutArcList(G, n2, 0);

   231   checkGraphOutArcList(G, n3, 1);

   232   checkGraphOutArcList(G, n4, 0);

   234   checkGraphInArcList(G, n1, 1);

   235   checkGraphInArcList(G, n2, 0);

   236   checkGraphInArcList(G, n3, 0);

   237   checkGraphInArcList(G, n4, 0);

   239   checkGraphConArcList(G, 1);

   240 }

   243 template <class Digraph>

   244 void checkDigraphSnapshot() {

   245   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   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);

   252   typename Digraph::Snapshot snapshot(G);

   254   Node n = G.addNode();

   255   G.addArc(n3, n);

   256   G.addArc(n, n3);

   258   checkGraphNodeList(G, 4);

   259   checkGraphArcList(G, 6);

   261   snapshot.restore();

   263   checkGraphNodeList(G, 3);

   264   checkGraphArcList(G, 4);

   266   checkGraphOutArcList(G, n1, 1);

   267   checkGraphOutArcList(G, n2, 3);

   268   checkGraphOutArcList(G, n3, 0);

   270   checkGraphInArcList(G, n1, 1);

   271   checkGraphInArcList(G, n2, 1);

   272   checkGraphInArcList(G, n3, 2);

   274   checkGraphConArcList(G, 4);

   276   checkNodeIds(G);

   277   checkArcIds(G);

   278   checkGraphNodeMap(G);

   279   checkGraphArcMap(G);

   281   G.addNode();

   282   snapshot.save(G);

   284   G.addArc(G.addNode(), G.addNode());

   286   snapshot.restore();

   288   checkGraphNodeList(G, 4);

   289   checkGraphArcList(G, 4);

   290 }

   292 void checkConcepts() {

   293   { // Checking digraph components

   294     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();

   296     checkConcept<IDableDigraphComponent<>,

   297       IDableDigraphComponent<> >();

   299     checkConcept<IterableDigraphComponent<>,

   300       IterableDigraphComponent<> >();

   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 }

   329 template <typename Digraph>

   330 void checkDigraphValidity() {

   331   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   332   Digraph g;

   334   Node

   335     n1 = g.addNode(),

   336     n2 = g.addNode(),

   337     n3 = g.addNode();

   339   Arc

   340     e1 = g.addArc(n1, n2),

   341     e2 = g.addArc(n2, n3);

   343   check(g.valid(n1), "Wrong validity check");

   344   check(g.valid(e1), "Wrong validity check");

   346   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

   347   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

   348 }

   350 template <typename Digraph>

   351 void checkDigraphValidityErase() {

   352   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   353   Digraph g;

   355   Node

   356     n1 = g.addNode(),

   357     n2 = g.addNode(),

   358     n3 = g.addNode();

   360   Arc

   361     e1 = g.addArc(n1, n2),

   362     e2 = g.addArc(n2, n3);

   364   check(g.valid(n1), "Wrong validity check");

   365   check(g.valid(e1), "Wrong validity check");

   367   g.erase(n1);

   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");

   375   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

   376   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

   377 }

   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 }

   396 int main() {

   397   checkDigraphs();

   398   checkConcepts();

   399   return 0;

   400 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Tue, 05 May 2009 07:43:28 +0100
branch	1.0
changeset 546	1c247d3e4bbd
parent 228	b6732e0d38c5
child 388	2d87dbd7f8c8
permissions	-rw-r--r--