lemon-main: test/digraph_test.cc@1bafdbd2fc46

     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-2010

     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/static_graph.h>

    23 #include <lemon/full_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   G.reserveNode(3);

    40   G.reserveArc(4);

    42   Node

    43     n1 = G.addNode(),

    44     n2 = G.addNode(),

    45     n3 = G.addNode();

    46   checkGraphNodeList(G, 3);

    47   checkGraphArcList(G, 0);

    49   Arc a1 = G.addArc(n1, n2);

    50   check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");

    51   checkGraphNodeList(G, 3);

    52   checkGraphArcList(G, 1);

    54   checkGraphOutArcList(G, n1, 1);

    55   checkGraphOutArcList(G, n2, 0);

    56   checkGraphOutArcList(G, n3, 0);

    58   checkGraphInArcList(G, n1, 0);

    59   checkGraphInArcList(G, n2, 1);

    60   checkGraphInArcList(G, n3, 0);

    62   checkGraphConArcList(G, 1);

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

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

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

    67   ignore_unused_variable_warning(a2,a3,a4);

    69   checkGraphNodeList(G, 3);

    70   checkGraphArcList(G, 4);

    72   checkGraphOutArcList(G, n1, 1);

    73   checkGraphOutArcList(G, n2, 3);

    74   checkGraphOutArcList(G, n3, 0);

    76   checkGraphInArcList(G, n1, 1);

    77   checkGraphInArcList(G, n2, 1);

    78   checkGraphInArcList(G, n3, 2);

    80   checkGraphConArcList(G, 4);

    82   checkNodeIds(G);

    83   checkArcIds(G);

    84   checkGraphNodeMap(G);

    85   checkGraphArcMap(G);

    86 }

    88 template <class Digraph>

    89 void checkDigraphSplit() {

    90   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    92   Digraph G;

    93   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();

    94   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),

    95       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);

    96   ignore_unused_variable_warning(a1,a2,a3,a4);

    98   Node n4 = G.split(n2);

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

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

   102         "Wrong split.");

   104   checkGraphNodeList(G, 4);

   105   checkGraphArcList(G, 5);

   107   checkGraphOutArcList(G, n1, 1);

   108   checkGraphOutArcList(G, n2, 1);

   109   checkGraphOutArcList(G, n3, 0);

   110   checkGraphOutArcList(G, n4, 3);

   112   checkGraphInArcList(G, n1, 1);

   113   checkGraphInArcList(G, n2, 1);

   114   checkGraphInArcList(G, n3, 2);

   115   checkGraphInArcList(G, n4, 1);

   117   checkGraphConArcList(G, 5);

   118 }

   120 template <class Digraph>

   121 void checkDigraphAlter() {

   122   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   124   Digraph G;

   125   Node n1 = G.addNode(), n2 = G.addNode(),

   126        n3 = G.addNode(), n4 = G.addNode();

   127   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),

   128       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),

   129       a5 = G.addArc(n2, n4);

   130   ignore_unused_variable_warning(a1,a2,a3,a5);

   132   checkGraphNodeList(G, 4);

   133   checkGraphArcList(G, 5);

   135   // Check changeSource() and changeTarget()

   136   G.changeTarget(a4, n1);

   138   checkGraphNodeList(G, 4);

   139   checkGraphArcList(G, 5);

   141   checkGraphOutArcList(G, n1, 1);

   142   checkGraphOutArcList(G, n2, 1);

   143   checkGraphOutArcList(G, n3, 0);

   144   checkGraphOutArcList(G, n4, 3);

   146   checkGraphInArcList(G, n1, 2);

   147   checkGraphInArcList(G, n2, 1);

   148   checkGraphInArcList(G, n3, 1);

   149   checkGraphInArcList(G, n4, 1);

   151   checkGraphConArcList(G, 5);

   153   G.changeSource(a4, n3);

   155   checkGraphNodeList(G, 4);

   156   checkGraphArcList(G, 5);

   158   checkGraphOutArcList(G, n1, 1);

   159   checkGraphOutArcList(G, n2, 1);

   160   checkGraphOutArcList(G, n3, 1);

   161   checkGraphOutArcList(G, n4, 2);

   163   checkGraphInArcList(G, n1, 2);

   164   checkGraphInArcList(G, n2, 1);

   165   checkGraphInArcList(G, n3, 1);

   166   checkGraphInArcList(G, n4, 1);

   168   checkGraphConArcList(G, 5);

   170   // Check contract()

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

   173   checkGraphNodeList(G, 3);

   174   checkGraphArcList(G, 5);

   176   checkGraphOutArcList(G, n1, 1);

   177   checkGraphOutArcList(G, n2, 3);

   178   checkGraphOutArcList(G, n3, 1);

   180   checkGraphInArcList(G, n1, 2);

   181   checkGraphInArcList(G, n2, 2);

   182   checkGraphInArcList(G, n3, 1);

   184   checkGraphConArcList(G, 5);

   186   G.contract(n2, n1);

   188   checkGraphNodeList(G, 2);

   189   checkGraphArcList(G, 3);

   191   checkGraphOutArcList(G, n2, 2);

   192   checkGraphOutArcList(G, n3, 1);

   194   checkGraphInArcList(G, n2, 2);

   195   checkGraphInArcList(G, n3, 1);

   197   checkGraphConArcList(G, 3);

   198 }

   200 template <class Digraph>

   201 void checkDigraphErase() {

   202   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   204   Digraph G;

   205   Node n1 = G.addNode(), n2 = G.addNode(),

   206        n3 = G.addNode(), n4 = G.addNode();

   207   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),

   208       a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),

   209       a5 = G.addArc(n2, n4);

   210   ignore_unused_variable_warning(a2,a3,a4,a5);

   212   // Check arc deletion

   213   G.erase(a1);

   215   checkGraphNodeList(G, 4);

   216   checkGraphArcList(G, 4);

   218   checkGraphOutArcList(G, n1, 0);

   219   checkGraphOutArcList(G, n2, 1);

   220   checkGraphOutArcList(G, n3, 1);

   221   checkGraphOutArcList(G, n4, 2);

   223   checkGraphInArcList(G, n1, 2);

   224   checkGraphInArcList(G, n2, 0);

   225   checkGraphInArcList(G, n3, 1);

   226   checkGraphInArcList(G, n4, 1);

   228   checkGraphConArcList(G, 4);

   230   // Check node deletion

   231   G.erase(n4);

   233   checkGraphNodeList(G, 3);

   234   checkGraphArcList(G, 1);

   236   checkGraphOutArcList(G, n1, 0);

   237   checkGraphOutArcList(G, n2, 0);

   238   checkGraphOutArcList(G, n3, 1);

   239   checkGraphOutArcList(G, n4, 0);

   241   checkGraphInArcList(G, n1, 1);

   242   checkGraphInArcList(G, n2, 0);

   243   checkGraphInArcList(G, n3, 0);

   244   checkGraphInArcList(G, n4, 0);

   246   checkGraphConArcList(G, 1);

   247 }

   250 template <class Digraph>

   251 void checkDigraphSnapshot() {

   252   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   254   Digraph G;

   255   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();

   256   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),

   257       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);

   258   ignore_unused_variable_warning(a1,a2,a3,a4);

   260   typename Digraph::Snapshot snapshot(G);

   262   Node n = G.addNode();

   263   G.addArc(n3, n);

   264   G.addArc(n, n3);

   266   checkGraphNodeList(G, 4);

   267   checkGraphArcList(G, 6);

   269   snapshot.restore();

   271   checkGraphNodeList(G, 3);

   272   checkGraphArcList(G, 4);

   274   checkGraphOutArcList(G, n1, 1);

   275   checkGraphOutArcList(G, n2, 3);

   276   checkGraphOutArcList(G, n3, 0);

   278   checkGraphInArcList(G, n1, 1);

   279   checkGraphInArcList(G, n2, 1);

   280   checkGraphInArcList(G, n3, 2);

   282   checkGraphConArcList(G, 4);

   284   checkNodeIds(G);

   285   checkArcIds(G);

   286   checkGraphNodeMap(G);

   287   checkGraphArcMap(G);

   289   G.addNode();

   290   snapshot.save(G);

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

   294   snapshot.restore();

   295   snapshot.save(G);

   297   checkGraphNodeList(G, 4);

   298   checkGraphArcList(G, 4);

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

   302   snapshot.restore();

   304   checkGraphNodeList(G, 4);

   305   checkGraphArcList(G, 4);

   306 }

   308 void checkConcepts() {

   309   { // Checking digraph components

   310     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();

   312     checkConcept<IDableDigraphComponent<>,

   313       IDableDigraphComponent<> >();

   315     checkConcept<IterableDigraphComponent<>,

   316       IterableDigraphComponent<> >();

   318     checkConcept<MappableDigraphComponent<>,

   319       MappableDigraphComponent<> >();

   320   }

   321   { // Checking skeleton digraph

   322     checkConcept<Digraph, Digraph>();

   323   }

   324   { // Checking ListDigraph

   325     checkConcept<Digraph, ListDigraph>();

   326     checkConcept<AlterableDigraphComponent<>, ListDigraph>();

   327     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();

   328     checkConcept<ClearableDigraphComponent<>, ListDigraph>();

   329     checkConcept<ErasableDigraphComponent<>, ListDigraph>();

   330   }

   331   { // Checking SmartDigraph

   332     checkConcept<Digraph, SmartDigraph>();

   333     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();

   334     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();

   335     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();

   336   }

   337   { // Checking StaticDigraph

   338     checkConcept<Digraph, StaticDigraph>();

   339     checkConcept<ClearableDigraphComponent<>, StaticDigraph>();

   340   }

   341   { // Checking FullDigraph

   342     checkConcept<Digraph, FullDigraph>();

   343   }

   344 }

   346 template <typename Digraph>

   347 void checkDigraphValidity() {

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

   359   ignore_unused_variable_warning(e2);

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

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

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

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

   366 }

   368 template <typename Digraph>

   369 void checkDigraphValidityErase() {

   370   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   371   Digraph g;

   373   Node

   374     n1 = g.addNode(),

   375     n2 = g.addNode(),

   376     n3 = g.addNode();

   378   Arc

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

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

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

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

   385   g.erase(n1);

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

   388   check(g.valid(n2), "Wrong validity check");

   389   check(g.valid(n3), "Wrong validity check");

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

   391   check(g.valid(e2), "Wrong validity check");

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

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

   395 }

   397 void checkStaticDigraph() {

   398   SmartDigraph g;

   399   SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);

   400   SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);

   402   StaticDigraph G;

   404   checkGraphNodeList(G, 0);

   405   checkGraphArcList(G, 0);

   407   G.build(g, nref, aref);

   409   checkGraphNodeList(G, 0);

   410   checkGraphArcList(G, 0);

   412   SmartDigraph::Node

   413     n1 = g.addNode(),

   414     n2 = g.addNode(),

   415     n3 = g.addNode();

   417   G.build(g, nref, aref);

   419   checkGraphNodeList(G, 3);

   420   checkGraphArcList(G, 0);

   422   SmartDigraph::Arc a1 = g.addArc(n1, n2);

   424   G.build(g, nref, aref);

   426   check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],

   427         "Wrong arc or wrong references");

   428   checkGraphNodeList(G, 3);

   429   checkGraphArcList(G, 1);

   431   checkGraphOutArcList(G, nref[n1], 1);

   432   checkGraphOutArcList(G, nref[n2], 0);

   433   checkGraphOutArcList(G, nref[n3], 0);

   435   checkGraphInArcList(G, nref[n1], 0);

   436   checkGraphInArcList(G, nref[n2], 1);

   437   checkGraphInArcList(G, nref[n3], 0);

   439   checkGraphConArcList(G, 1);

   441   SmartDigraph::Arc

   442     a2 = g.addArc(n2, n1),

   443     a3 = g.addArc(n2, n3),

   444     a4 = g.addArc(n2, n3);

   445   ignore_unused_variable_warning(a2,a3,a4);

   447   digraphCopy(g, G).nodeRef(nref).run();

   449   checkGraphNodeList(G, 3);

   450   checkGraphArcList(G, 4);

   452   checkGraphOutArcList(G, nref[n1], 1);

   453   checkGraphOutArcList(G, nref[n2], 3);

   454   checkGraphOutArcList(G, nref[n3], 0);

   456   checkGraphInArcList(G, nref[n1], 1);

   457   checkGraphInArcList(G, nref[n2], 1);

   458   checkGraphInArcList(G, nref[n3], 2);

   460   checkGraphConArcList(G, 4);

   462   std::vector<std::pair<int,int> > arcs;

   463   arcs.push_back(std::make_pair(0,1));

   464   arcs.push_back(std::make_pair(0,2));

   465   arcs.push_back(std::make_pair(1,3));

   466   arcs.push_back(std::make_pair(1,2));

   467   arcs.push_back(std::make_pair(3,0));

   468   arcs.push_back(std::make_pair(3,3));

   469   arcs.push_back(std::make_pair(4,2));

   470   arcs.push_back(std::make_pair(4,3));

   471   arcs.push_back(std::make_pair(4,1));

   473   G.build(6, arcs.begin(), arcs.end());

   475   checkGraphNodeList(G, 6);

   476   checkGraphArcList(G, 9);

   478   checkGraphOutArcList(G, G.node(0), 2);

   479   checkGraphOutArcList(G, G.node(1), 2);

   480   checkGraphOutArcList(G, G.node(2), 0);

   481   checkGraphOutArcList(G, G.node(3), 2);

   482   checkGraphOutArcList(G, G.node(4), 3);

   483   checkGraphOutArcList(G, G.node(5), 0);

   485   checkGraphInArcList(G, G.node(0), 1);

   486   checkGraphInArcList(G, G.node(1), 2);

   487   checkGraphInArcList(G, G.node(2), 3);

   488   checkGraphInArcList(G, G.node(3), 3);

   489   checkGraphInArcList(G, G.node(4), 0);

   490   checkGraphInArcList(G, G.node(5), 0);

   492   checkGraphConArcList(G, 9);

   494   checkNodeIds(G);

   495   checkArcIds(G);

   496   checkGraphNodeMap(G);

   497   checkGraphArcMap(G);

   499   int n = G.nodeNum();

   500   int m = G.arcNum();

   501   check(G.index(G.node(n-1)) == n-1, "Wrong index.");

   502   check(G.index(G.arc(m-1)) == m-1, "Wrong index.");

   503 }

   505 void checkFullDigraph(int num) {

   506   typedef FullDigraph Digraph;

   507   DIGRAPH_TYPEDEFS(Digraph);

   509   Digraph G(num);

   510   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");

   512   G.resize(num);

   513   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");

   515   checkGraphNodeList(G, num);

   516   checkGraphArcList(G, num * num);

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

   519     checkGraphOutArcList(G, n, num);

   520     checkGraphInArcList(G, n, num);

   521   }

   523   checkGraphConArcList(G, num * num);

   525   checkNodeIds(G);

   526   checkArcIds(G);

   527   checkGraphNodeMap(G);

   528   checkGraphArcMap(G);

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

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

   532   }

   534   for (NodeIt s(G); s != INVALID; ++s) {

   535     for (NodeIt t(G); t != INVALID; ++t) {

   536       Arc a = G.arc(s, t);

   537       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");

   538     }

   539   }

   540 }

   542 void checkDigraphs() {

   543   { // Checking ListDigraph

   544     checkDigraphBuild<ListDigraph>();

   545     checkDigraphSplit<ListDigraph>();

   546     checkDigraphAlter<ListDigraph>();

   547     checkDigraphErase<ListDigraph>();

   548     checkDigraphSnapshot<ListDigraph>();

   549     checkDigraphValidityErase<ListDigraph>();

   550   }

   551   { // Checking SmartDigraph

   552     checkDigraphBuild<SmartDigraph>();

   553     checkDigraphSplit<SmartDigraph>();

   554     checkDigraphSnapshot<SmartDigraph>();

   555     checkDigraphValidity<SmartDigraph>();

   556   }

   557   { // Checking StaticDigraph

   558     checkStaticDigraph();

   559   }

   560   { // Checking FullDigraph

   561     checkFullDigraph(8);

   562   }

   563 }

   565 int main() {

   566   checkDigraphs();

   567   checkConcepts();

   568   return 0;

   569 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Sat, 20 Mar 2010 11:03:12 +0100
changeset 1043	1bafdbd2fc46
parent 998	7fdaa05a69a1
child 1084	8b2d4e5d96e4
permissions	-rw-r--r--