lemon: test/digraph_test.cc@c160bf9f18ef

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

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

   322     checkConcept<Digraph, StaticDigraph>();

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

   324   }

   325   { // Checking FullDigraph

   326     checkConcept<Digraph, FullDigraph>();

   327   }

   328 }

   330 template <typename Digraph>

   331 void checkDigraphValidity() {

   332   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   333   Digraph g;

   335   Node

   336     n1 = g.addNode(),

   337     n2 = g.addNode(),

   338     n3 = g.addNode();

   340   Arc

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

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

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

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

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

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

   349 }

   351 template <typename Digraph>

   352 void checkDigraphValidityErase() {

   353   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   354   Digraph g;

   356   Node

   357     n1 = g.addNode(),

   358     n2 = g.addNode(),

   359     n3 = g.addNode();

   361   Arc

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

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

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

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

   368   g.erase(n1);

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

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

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

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

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

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

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

   378 }

   380 void checkStaticDigraph() {

   381   SmartDigraph g;

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

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

   385   StaticDigraph G;

   387   checkGraphNodeList(G, 0);

   388   checkGraphArcList(G, 0);

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

   392   checkGraphNodeList(G, 0);

   393   checkGraphArcList(G, 0);

   395   SmartDigraph::Node

   396     n1 = g.addNode(),

   397     n2 = g.addNode(),

   398     n3 = g.addNode();

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

   402   checkGraphNodeList(G, 3);

   403   checkGraphArcList(G, 0);

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

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

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

   410         "Wrong arc or wrong references");

   411   checkGraphNodeList(G, 3);

   412   checkGraphArcList(G, 1);

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

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

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

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

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

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

   422   checkGraphConArcList(G, 1);

   424   SmartDigraph::Arc

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

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

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

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

   431   checkGraphNodeList(G, 3);

   432   checkGraphArcList(G, 4);

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

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

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

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

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

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

   442   checkGraphConArcList(G, 4);

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

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

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

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

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

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

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

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

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

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

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

   457   checkGraphNodeList(G, 6);

   458   checkGraphArcList(G, 9);

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

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

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

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

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

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

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

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

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

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

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

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

   474   checkGraphConArcList(G, 9);

   476   checkNodeIds(G);

   477   checkArcIds(G);

   478   checkGraphNodeMap(G);

   479   checkGraphArcMap(G);

   481   int n = G.nodeNum();

   482   int m = G.arcNum();

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

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

   485 }

   487 void checkFullDigraph(int num) {

   488   typedef FullDigraph Digraph;

   489   DIGRAPH_TYPEDEFS(Digraph);

   490   Digraph G(num);

   492   checkGraphNodeList(G, num);

   493   checkGraphArcList(G, num * num);

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

   496     checkGraphOutArcList(G, n, num);

   497     checkGraphInArcList(G, n, num);

   498   }

   500   checkGraphConArcList(G, num * num);

   502   checkNodeIds(G);

   503   checkArcIds(G);

   504   checkGraphNodeMap(G);

   505   checkGraphArcMap(G);

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

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

   509   }

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

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

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

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

   515     }

   516   }

   517 }

   519 void checkDigraphs() {

   520   { // Checking ListDigraph

   521     checkDigraphBuild<ListDigraph>();

   522     checkDigraphSplit<ListDigraph>();

   523     checkDigraphAlter<ListDigraph>();

   524     checkDigraphErase<ListDigraph>();

   525     checkDigraphSnapshot<ListDigraph>();

   526     checkDigraphValidityErase<ListDigraph>();

   527   }

   528   { // Checking SmartDigraph

   529     checkDigraphBuild<SmartDigraph>();

   530     checkDigraphSplit<SmartDigraph>();

   531     checkDigraphSnapshot<SmartDigraph>();

   532     checkDigraphValidity<SmartDigraph>();

   533   }

   534   { // Checking StaticDigraph

   535     checkStaticDigraph();

   536   }

   537   { // Checking FullDigraph

   538     checkFullDigraph(8);

   539   }

   540 }

   542 int main() {

   543   checkDigraphs();

   544   checkConcepts();

   545   return 0;

   546 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Thu, 05 Nov 2009 10:01:02 +0100
changeset 826	c160bf9f18ef
parent 823	eff1caf6d32e
child 827	580af8cf2f6a
permissions	-rw-r--r--