lemon-1.1: test/digraph_test.cc@660db48f324f

     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>

    24 #include "test_tools.h"

    25 #include "graph_test.h"

    27 using namespace lemon;

    28 using namespace lemon::concepts;

    30 template <class Digraph>

    31 void checkDigraphBuild() {

    32   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    33   Digraph G;

    35   checkGraphNodeList(G, 0);

    36   checkGraphArcList(G, 0);

    38   Node

    39     n1 = G.addNode(),

    40     n2 = G.addNode(),

    41     n3 = G.addNode();

    42   checkGraphNodeList(G, 3);

    43   checkGraphArcList(G, 0);

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

    50   checkGraphOutArcList(G, n1, 1);

    51   checkGraphOutArcList(G, n2, 0);

    52   checkGraphOutArcList(G, n3, 0);

    54   checkGraphInArcList(G, n1, 0);

    55   checkGraphInArcList(G, n2, 1);

    56   checkGraphInArcList(G, n3, 0);

    58   checkGraphConArcList(G, 1);

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

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

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

    64   checkGraphNodeList(G, 3);

    65   checkGraphArcList(G, 4);

    67   checkGraphOutArcList(G, n1, 1);

    68   checkGraphOutArcList(G, n2, 3);

    69   checkGraphOutArcList(G, n3, 0);

    71   checkGraphInArcList(G, n1, 1);

    72   checkGraphInArcList(G, n2, 1);

    73   checkGraphInArcList(G, n3, 2);

    75   checkGraphConArcList(G, 4);

    77   checkNodeIds(G);

    78   checkArcIds(G);

    79   checkGraphNodeMap(G);

    80   checkGraphArcMap(G);

    81 }

    83 template <class Digraph>

    84 void checkDigraphSplit() {

    85   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

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

    92   Node n4 = G.split(n2);

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

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

    96         "Wrong split.");

    98   checkGraphNodeList(G, 4);

    99   checkGraphArcList(G, 5);

   101   checkGraphOutArcList(G, n1, 1);

   102   checkGraphOutArcList(G, n2, 1);

   103   checkGraphOutArcList(G, n3, 0);

   104   checkGraphOutArcList(G, n4, 3);

   106   checkGraphInArcList(G, n1, 1);

   107   checkGraphInArcList(G, n2, 1);

   108   checkGraphInArcList(G, n3, 2);

   109   checkGraphInArcList(G, n4, 1);

   111   checkGraphConArcList(G, 5);

   112 }

   114 template <class Digraph>

   115 void checkDigraphAlter() {

   116   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

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

   125   checkGraphNodeList(G, 4);

   126   checkGraphArcList(G, 5);

   128   // Check changeSource() and changeTarget()

   129   G.changeTarget(a4, n1);

   131   checkGraphNodeList(G, 4);

   132   checkGraphArcList(G, 5);

   134   checkGraphOutArcList(G, n1, 1);

   135   checkGraphOutArcList(G, n2, 1);

   136   checkGraphOutArcList(G, n3, 0);

   137   checkGraphOutArcList(G, n4, 3);

   139   checkGraphInArcList(G, n1, 2);

   140   checkGraphInArcList(G, n2, 1);

   141   checkGraphInArcList(G, n3, 1);

   142   checkGraphInArcList(G, n4, 1);

   144   checkGraphConArcList(G, 5);

   146   G.changeSource(a4, n3);

   148   checkGraphNodeList(G, 4);

   149   checkGraphArcList(G, 5);

   151   checkGraphOutArcList(G, n1, 1);

   152   checkGraphOutArcList(G, n2, 1);

   153   checkGraphOutArcList(G, n3, 1);

   154   checkGraphOutArcList(G, n4, 2);

   156   checkGraphInArcList(G, n1, 2);

   157   checkGraphInArcList(G, n2, 1);

   158   checkGraphInArcList(G, n3, 1);

   159   checkGraphInArcList(G, n4, 1);

   161   checkGraphConArcList(G, 5);

   163   // Check contract()

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

   166   checkGraphNodeList(G, 3);

   167   checkGraphArcList(G, 5);

   169   checkGraphOutArcList(G, n1, 1);

   170   checkGraphOutArcList(G, n2, 3);

   171   checkGraphOutArcList(G, n3, 1);

   173   checkGraphInArcList(G, n1, 2);

   174   checkGraphInArcList(G, n2, 2);

   175   checkGraphInArcList(G, n3, 1);

   177   checkGraphConArcList(G, 5);

   179   G.contract(n2, n1);

   181   checkGraphNodeList(G, 2);

   182   checkGraphArcList(G, 3);

   184   checkGraphOutArcList(G, n2, 2);

   185   checkGraphOutArcList(G, n3, 1);

   187   checkGraphInArcList(G, n2, 2);

   188   checkGraphInArcList(G, n3, 1);

   190   checkGraphConArcList(G, 3);

   191 }

   193 template <class Digraph>

   194 void checkDigraphErase() {

   195   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

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

   204   // Check arc deletion

   205   G.erase(a1);

   207   checkGraphNodeList(G, 4);

   208   checkGraphArcList(G, 4);

   210   checkGraphOutArcList(G, n1, 0);

   211   checkGraphOutArcList(G, n2, 1);

   212   checkGraphOutArcList(G, n3, 1);

   213   checkGraphOutArcList(G, n4, 2);

   215   checkGraphInArcList(G, n1, 2);

   216   checkGraphInArcList(G, n2, 0);

   217   checkGraphInArcList(G, n3, 1);

   218   checkGraphInArcList(G, n4, 1);

   220   checkGraphConArcList(G, 4);

   222   // Check node deletion

   223   G.erase(n4);

   225   checkGraphNodeList(G, 3);

   226   checkGraphArcList(G, 1);

   228   checkGraphOutArcList(G, n1, 0);

   229   checkGraphOutArcList(G, n2, 0);

   230   checkGraphOutArcList(G, n3, 1);

   231   checkGraphOutArcList(G, n4, 0);

   233   checkGraphInArcList(G, n1, 1);

   234   checkGraphInArcList(G, n2, 0);

   235   checkGraphInArcList(G, n3, 0);

   236   checkGraphInArcList(G, n4, 0);

   238   checkGraphConArcList(G, 1);

   239 }

   242 template <class Digraph>

   243 void checkDigraphSnapshot() {

   244   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

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

   251   typename Digraph::Snapshot snapshot(G);

   253   Node n = G.addNode();

   254   G.addArc(n3, n);

   255   G.addArc(n, n3);

   257   checkGraphNodeList(G, 4);

   258   checkGraphArcList(G, 6);

   260   snapshot.restore();

   262   checkGraphNodeList(G, 3);

   263   checkGraphArcList(G, 4);

   265   checkGraphOutArcList(G, n1, 1);

   266   checkGraphOutArcList(G, n2, 3);

   267   checkGraphOutArcList(G, n3, 0);

   269   checkGraphInArcList(G, n1, 1);

   270   checkGraphInArcList(G, n2, 1);

   271   checkGraphInArcList(G, n3, 2);

   273   checkGraphConArcList(G, 4);

   275   checkNodeIds(G);

   276   checkArcIds(G);

   277   checkGraphNodeMap(G);

   278   checkGraphArcMap(G);

   280   G.addNode();

   281   snapshot.save(G);

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

   285   snapshot.restore();

   287   checkGraphNodeList(G, 4);

   288   checkGraphArcList(G, 4);

   289 }

   291 void checkConcepts() {

   292   { // Checking digraph components

   293     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();

   295     checkConcept<IDableDigraphComponent<>,

   296       IDableDigraphComponent<> >();

   298     checkConcept<IterableDigraphComponent<>,

   299       IterableDigraphComponent<> >();

   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 }

   325 template <typename Digraph>

   326 void checkDigraphValidity() {

   327   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   328   Digraph g;

   330   Node

   331     n1 = g.addNode(),

   332     n2 = g.addNode(),

   333     n3 = g.addNode();

   335   Arc

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

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

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

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

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

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

   344 }

   346 template <typename Digraph>

   347 void checkDigraphValidityErase() {

   348   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   349   Digraph g;

   351   Node

   352     n1 = g.addNode(),

   353     n2 = g.addNode(),

   354     n3 = g.addNode();

   356   Arc

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

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

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

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

   363   g.erase(n1);

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

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

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

   373 }

   375 void checkFullDigraph(int num) {

   376   typedef FullDigraph Digraph;

   377   DIGRAPH_TYPEDEFS(Digraph);

   378   Digraph G(num);

   380   checkGraphNodeList(G, num);

   381   checkGraphArcList(G, num * num);

   383   for (NodeIt n(G); n != INVALID; ++n) {

   384     checkGraphOutArcList(G, n, num);

   385     checkGraphInArcList(G, n, num);

   386   }

   388   checkGraphConArcList(G, num * num);

   390   checkNodeIds(G);

   391   checkArcIds(G);

   392   checkGraphNodeMap(G);

   393   checkGraphArcMap(G);

   395   for (int i = 0; i < G.nodeNum(); ++i) {

   396     check(G.index(G(i)) == i, "Wrong index");

   397   }

   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 }

   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 }

   427 int main() {

   428   checkDigraphs();

   429   checkConcepts();

   430   return 0;

   431 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 21 Nov 2008 14:11:29 +0000
changeset 389	660db48f324f
parent 365	a12eef1f82b2
parent 374	49d9a36b3b84
child 440	88ed40ad0d4f
permissions	-rw-r--r--