test/digraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 13 Mar 2010 22:01:38 +0100
changeset 864 d3ea191c3412
parent 777 5764dd9b6e18
parent 740 819ca5b50de0
child 877 141f9c0db4a3
permissions -rw-r--r--
Rename min mean cycle classes and their members (#179)
with respect to the possible introduction of min ratio
cycle algorithms in the future.

The renamed classes:
- Karp --> KarpMmc
- HartmannOrlin --> HartmannOrlinMmc
- Howard --> HowardMmc

The renamed members:
- cycleLength() --> cycleCost()
- cycleArcNum() --> cycleSize()
- findMinMean() --> findCycleMean()
- Value --> Cost
- LargeValue --> LargeCost
- SetLargeValue --> SetLargeCost
     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  */
    18 
    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>
    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   G.reserveNode(3);
    40   G.reserveArc(4);
    41 
    42   Node
    43     n1 = G.addNode(),
    44     n2 = G.addNode(),
    45     n3 = G.addNode();
    46   checkGraphNodeList(G, 3);
    47   checkGraphArcList(G, 0);
    48 
    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);
    53 
    54   checkGraphOutArcList(G, n1, 1);
    55   checkGraphOutArcList(G, n2, 0);
    56   checkGraphOutArcList(G, n3, 0);
    57 
    58   checkGraphInArcList(G, n1, 0);
    59   checkGraphInArcList(G, n2, 1);
    60   checkGraphInArcList(G, n3, 0);
    61 
    62   checkGraphConArcList(G, 1);
    63 
    64   Arc a2 = G.addArc(n2, n1),
    65       a3 = G.addArc(n2, n3),
    66       a4 = G.addArc(n2, n3);
    67 
    68   checkGraphNodeList(G, 3);
    69   checkGraphArcList(G, 4);
    70 
    71   checkGraphOutArcList(G, n1, 1);
    72   checkGraphOutArcList(G, n2, 3);
    73   checkGraphOutArcList(G, n3, 0);
    74 
    75   checkGraphInArcList(G, n1, 1);
    76   checkGraphInArcList(G, n2, 1);
    77   checkGraphInArcList(G, n3, 2);
    78 
    79   checkGraphConArcList(G, 4);
    80 
    81   checkNodeIds(G);
    82   checkArcIds(G);
    83   checkGraphNodeMap(G);
    84   checkGraphArcMap(G);
    85 }
    86 
    87 template <class Digraph>
    88 void checkDigraphSplit() {
    89   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    90 
    91   Digraph G;
    92   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    93   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    94       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    95 
    96   Node n4 = G.split(n2);
    97 
    98   check(G.target(OutArcIt(G, n2)) == n4 &&
    99         G.source(InArcIt(G, n4)) == n2,
   100         "Wrong split.");
   101 
   102   checkGraphNodeList(G, 4);
   103   checkGraphArcList(G, 5);
   104 
   105   checkGraphOutArcList(G, n1, 1);
   106   checkGraphOutArcList(G, n2, 1);
   107   checkGraphOutArcList(G, n3, 0);
   108   checkGraphOutArcList(G, n4, 3);
   109 
   110   checkGraphInArcList(G, n1, 1);
   111   checkGraphInArcList(G, n2, 1);
   112   checkGraphInArcList(G, n3, 2);
   113   checkGraphInArcList(G, n4, 1);
   114 
   115   checkGraphConArcList(G, 5);
   116 }
   117 
   118 template <class Digraph>
   119 void checkDigraphAlter() {
   120   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   121 
   122   Digraph G;
   123   Node n1 = G.addNode(), n2 = G.addNode(),
   124        n3 = G.addNode(), n4 = G.addNode();
   125   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   126       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
   127       a5 = G.addArc(n2, n4);
   128 
   129   checkGraphNodeList(G, 4);
   130   checkGraphArcList(G, 5);
   131 
   132   // Check changeSource() and changeTarget()
   133   G.changeTarget(a4, n1);
   134 
   135   checkGraphNodeList(G, 4);
   136   checkGraphArcList(G, 5);
   137 
   138   checkGraphOutArcList(G, n1, 1);
   139   checkGraphOutArcList(G, n2, 1);
   140   checkGraphOutArcList(G, n3, 0);
   141   checkGraphOutArcList(G, n4, 3);
   142 
   143   checkGraphInArcList(G, n1, 2);
   144   checkGraphInArcList(G, n2, 1);
   145   checkGraphInArcList(G, n3, 1);
   146   checkGraphInArcList(G, n4, 1);
   147 
   148   checkGraphConArcList(G, 5);
   149 
   150   G.changeSource(a4, n3);
   151 
   152   checkGraphNodeList(G, 4);
   153   checkGraphArcList(G, 5);
   154 
   155   checkGraphOutArcList(G, n1, 1);
   156   checkGraphOutArcList(G, n2, 1);
   157   checkGraphOutArcList(G, n3, 1);
   158   checkGraphOutArcList(G, n4, 2);
   159 
   160   checkGraphInArcList(G, n1, 2);
   161   checkGraphInArcList(G, n2, 1);
   162   checkGraphInArcList(G, n3, 1);
   163   checkGraphInArcList(G, n4, 1);
   164 
   165   checkGraphConArcList(G, 5);
   166 
   167   // Check contract()
   168   G.contract(n2, n4, false);
   169 
   170   checkGraphNodeList(G, 3);
   171   checkGraphArcList(G, 5);
   172 
   173   checkGraphOutArcList(G, n1, 1);
   174   checkGraphOutArcList(G, n2, 3);
   175   checkGraphOutArcList(G, n3, 1);
   176 
   177   checkGraphInArcList(G, n1, 2);
   178   checkGraphInArcList(G, n2, 2);
   179   checkGraphInArcList(G, n3, 1);
   180 
   181   checkGraphConArcList(G, 5);
   182 
   183   G.contract(n2, n1);
   184 
   185   checkGraphNodeList(G, 2);
   186   checkGraphArcList(G, 3);
   187 
   188   checkGraphOutArcList(G, n2, 2);
   189   checkGraphOutArcList(G, n3, 1);
   190 
   191   checkGraphInArcList(G, n2, 2);
   192   checkGraphInArcList(G, n3, 1);
   193 
   194   checkGraphConArcList(G, 3);
   195 }
   196 
   197 template <class Digraph>
   198 void checkDigraphErase() {
   199   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   200 
   201   Digraph G;
   202   Node n1 = G.addNode(), n2 = G.addNode(),
   203        n3 = G.addNode(), n4 = G.addNode();
   204   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
   205       a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
   206       a5 = G.addArc(n2, n4);
   207 
   208   // Check arc deletion
   209   G.erase(a1);
   210 
   211   checkGraphNodeList(G, 4);
   212   checkGraphArcList(G, 4);
   213 
   214   checkGraphOutArcList(G, n1, 0);
   215   checkGraphOutArcList(G, n2, 1);
   216   checkGraphOutArcList(G, n3, 1);
   217   checkGraphOutArcList(G, n4, 2);
   218 
   219   checkGraphInArcList(G, n1, 2);
   220   checkGraphInArcList(G, n2, 0);
   221   checkGraphInArcList(G, n3, 1);
   222   checkGraphInArcList(G, n4, 1);
   223 
   224   checkGraphConArcList(G, 4);
   225 
   226   // Check node deletion
   227   G.erase(n4);
   228 
   229   checkGraphNodeList(G, 3);
   230   checkGraphArcList(G, 1);
   231 
   232   checkGraphOutArcList(G, n1, 0);
   233   checkGraphOutArcList(G, n2, 0);
   234   checkGraphOutArcList(G, n3, 1);
   235   checkGraphOutArcList(G, n4, 0);
   236 
   237   checkGraphInArcList(G, n1, 1);
   238   checkGraphInArcList(G, n2, 0);
   239   checkGraphInArcList(G, n3, 0);
   240   checkGraphInArcList(G, n4, 0);
   241 
   242   checkGraphConArcList(G, 1);
   243 }
   244 
   245 
   246 template <class Digraph>
   247 void checkDigraphSnapshot() {
   248   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   249 
   250   Digraph G;
   251   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   252   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
   253       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
   254 
   255   typename Digraph::Snapshot snapshot(G);
   256 
   257   Node n = G.addNode();
   258   G.addArc(n3, n);
   259   G.addArc(n, n3);
   260 
   261   checkGraphNodeList(G, 4);
   262   checkGraphArcList(G, 6);
   263 
   264   snapshot.restore();
   265 
   266   checkGraphNodeList(G, 3);
   267   checkGraphArcList(G, 4);
   268 
   269   checkGraphOutArcList(G, n1, 1);
   270   checkGraphOutArcList(G, n2, 3);
   271   checkGraphOutArcList(G, n3, 0);
   272 
   273   checkGraphInArcList(G, n1, 1);
   274   checkGraphInArcList(G, n2, 1);
   275   checkGraphInArcList(G, n3, 2);
   276 
   277   checkGraphConArcList(G, 4);
   278 
   279   checkNodeIds(G);
   280   checkArcIds(G);
   281   checkGraphNodeMap(G);
   282   checkGraphArcMap(G);
   283 
   284   G.addNode();
   285   snapshot.save(G);
   286 
   287   G.addArc(G.addNode(), G.addNode());
   288 
   289   snapshot.restore();
   290   snapshot.save(G);
   291 
   292   checkGraphNodeList(G, 4);
   293   checkGraphArcList(G, 4);
   294 
   295   G.addArc(G.addNode(), G.addNode());
   296 
   297   snapshot.restore();
   298 
   299   checkGraphNodeList(G, 4);
   300   checkGraphArcList(G, 4);
   301 }
   302 
   303 void checkConcepts() {
   304   { // Checking digraph components
   305     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   306 
   307     checkConcept<IDableDigraphComponent<>,
   308       IDableDigraphComponent<> >();
   309 
   310     checkConcept<IterableDigraphComponent<>,
   311       IterableDigraphComponent<> >();
   312 
   313     checkConcept<MappableDigraphComponent<>,
   314       MappableDigraphComponent<> >();
   315   }
   316   { // Checking skeleton digraph
   317     checkConcept<Digraph, Digraph>();
   318   }
   319   { // Checking ListDigraph
   320     checkConcept<Digraph, ListDigraph>();
   321     checkConcept<AlterableDigraphComponent<>, ListDigraph>();
   322     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
   323     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
   324     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
   325   }
   326   { // Checking SmartDigraph
   327     checkConcept<Digraph, SmartDigraph>();
   328     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
   329     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
   330     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
   331   }
   332   { // Checking StaticDigraph
   333     checkConcept<Digraph, StaticDigraph>();
   334     checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
   335   }
   336   { // Checking FullDigraph
   337     checkConcept<Digraph, FullDigraph>();
   338   }
   339 }
   340 
   341 template <typename Digraph>
   342 void checkDigraphValidity() {
   343   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   344   Digraph g;
   345 
   346   Node
   347     n1 = g.addNode(),
   348     n2 = g.addNode(),
   349     n3 = g.addNode();
   350 
   351   Arc
   352     e1 = g.addArc(n1, n2),
   353     e2 = g.addArc(n2, n3);
   354 
   355   check(g.valid(n1), "Wrong validity check");
   356   check(g.valid(e1), "Wrong validity check");
   357 
   358   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   359   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   360 }
   361 
   362 template <typename Digraph>
   363 void checkDigraphValidityErase() {
   364   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   365   Digraph g;
   366 
   367   Node
   368     n1 = g.addNode(),
   369     n2 = g.addNode(),
   370     n3 = g.addNode();
   371 
   372   Arc
   373     e1 = g.addArc(n1, n2),
   374     e2 = g.addArc(n2, n3);
   375 
   376   check(g.valid(n1), "Wrong validity check");
   377   check(g.valid(e1), "Wrong validity check");
   378 
   379   g.erase(n1);
   380 
   381   check(!g.valid(n1), "Wrong validity check");
   382   check(g.valid(n2), "Wrong validity check");
   383   check(g.valid(n3), "Wrong validity check");
   384   check(!g.valid(e1), "Wrong validity check");
   385   check(g.valid(e2), "Wrong validity check");
   386 
   387   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   388   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   389 }
   390 
   391 void checkStaticDigraph() {
   392   SmartDigraph g;
   393   SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
   394   SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
   395   
   396   StaticDigraph G;
   397   
   398   checkGraphNodeList(G, 0);
   399   checkGraphArcList(G, 0);
   400 
   401   G.build(g, nref, aref);
   402 
   403   checkGraphNodeList(G, 0);
   404   checkGraphArcList(G, 0);
   405 
   406   SmartDigraph::Node
   407     n1 = g.addNode(),
   408     n2 = g.addNode(),
   409     n3 = g.addNode();
   410 
   411   G.build(g, nref, aref);
   412 
   413   checkGraphNodeList(G, 3);
   414   checkGraphArcList(G, 0);
   415 
   416   SmartDigraph::Arc a1 = g.addArc(n1, n2);
   417 
   418   G.build(g, nref, aref);
   419 
   420   check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
   421         "Wrong arc or wrong references");
   422   checkGraphNodeList(G, 3);
   423   checkGraphArcList(G, 1);
   424 
   425   checkGraphOutArcList(G, nref[n1], 1);
   426   checkGraphOutArcList(G, nref[n2], 0);
   427   checkGraphOutArcList(G, nref[n3], 0);
   428 
   429   checkGraphInArcList(G, nref[n1], 0);
   430   checkGraphInArcList(G, nref[n2], 1);
   431   checkGraphInArcList(G, nref[n3], 0);
   432 
   433   checkGraphConArcList(G, 1);
   434 
   435   SmartDigraph::Arc
   436     a2 = g.addArc(n2, n1),
   437     a3 = g.addArc(n2, n3),
   438     a4 = g.addArc(n2, n3);
   439 
   440   digraphCopy(g, G).nodeRef(nref).run();
   441 
   442   checkGraphNodeList(G, 3);
   443   checkGraphArcList(G, 4);
   444 
   445   checkGraphOutArcList(G, nref[n1], 1);
   446   checkGraphOutArcList(G, nref[n2], 3);
   447   checkGraphOutArcList(G, nref[n3], 0);
   448 
   449   checkGraphInArcList(G, nref[n1], 1);
   450   checkGraphInArcList(G, nref[n2], 1);
   451   checkGraphInArcList(G, nref[n3], 2);
   452 
   453   checkGraphConArcList(G, 4);
   454 
   455   std::vector<std::pair<int,int> > arcs;
   456   arcs.push_back(std::make_pair(0,1));
   457   arcs.push_back(std::make_pair(0,2));
   458   arcs.push_back(std::make_pair(1,3));
   459   arcs.push_back(std::make_pair(1,2));
   460   arcs.push_back(std::make_pair(3,0));
   461   arcs.push_back(std::make_pair(3,3));
   462   arcs.push_back(std::make_pair(4,2));
   463   arcs.push_back(std::make_pair(4,3));
   464   arcs.push_back(std::make_pair(4,1));
   465 
   466   G.build(6, arcs.begin(), arcs.end());
   467   
   468   checkGraphNodeList(G, 6);
   469   checkGraphArcList(G, 9);
   470 
   471   checkGraphOutArcList(G, G.node(0), 2);
   472   checkGraphOutArcList(G, G.node(1), 2);
   473   checkGraphOutArcList(G, G.node(2), 0);
   474   checkGraphOutArcList(G, G.node(3), 2);
   475   checkGraphOutArcList(G, G.node(4), 3);
   476   checkGraphOutArcList(G, G.node(5), 0);
   477 
   478   checkGraphInArcList(G, G.node(0), 1);
   479   checkGraphInArcList(G, G.node(1), 2);
   480   checkGraphInArcList(G, G.node(2), 3);
   481   checkGraphInArcList(G, G.node(3), 3);
   482   checkGraphInArcList(G, G.node(4), 0);
   483   checkGraphInArcList(G, G.node(5), 0);
   484 
   485   checkGraphConArcList(G, 9);
   486 
   487   checkNodeIds(G);
   488   checkArcIds(G);
   489   checkGraphNodeMap(G);
   490   checkGraphArcMap(G);
   491   
   492   int n = G.nodeNum();
   493   int m = G.arcNum();
   494   check(G.index(G.node(n-1)) == n-1, "Wrong index.");
   495   check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
   496 }
   497 
   498 void checkFullDigraph(int num) {
   499   typedef FullDigraph Digraph;
   500   DIGRAPH_TYPEDEFS(Digraph);
   501 
   502   Digraph G(num);
   503   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
   504 
   505   G.resize(num);
   506   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
   507 
   508   checkGraphNodeList(G, num);
   509   checkGraphArcList(G, num * num);
   510 
   511   for (NodeIt n(G); n != INVALID; ++n) {
   512     checkGraphOutArcList(G, n, num);
   513     checkGraphInArcList(G, n, num);
   514   }
   515 
   516   checkGraphConArcList(G, num * num);
   517 
   518   checkNodeIds(G);
   519   checkArcIds(G);
   520   checkGraphNodeMap(G);
   521   checkGraphArcMap(G);
   522 
   523   for (int i = 0; i < G.nodeNum(); ++i) {
   524     check(G.index(G(i)) == i, "Wrong index");
   525   }
   526 
   527   for (NodeIt s(G); s != INVALID; ++s) {
   528     for (NodeIt t(G); t != INVALID; ++t) {
   529       Arc a = G.arc(s, t);
   530       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
   531     }
   532   }
   533 }
   534 
   535 void checkDigraphs() {
   536   { // Checking ListDigraph
   537     checkDigraphBuild<ListDigraph>();
   538     checkDigraphSplit<ListDigraph>();
   539     checkDigraphAlter<ListDigraph>();
   540     checkDigraphErase<ListDigraph>();
   541     checkDigraphSnapshot<ListDigraph>();
   542     checkDigraphValidityErase<ListDigraph>();
   543   }
   544   { // Checking SmartDigraph
   545     checkDigraphBuild<SmartDigraph>();
   546     checkDigraphSplit<SmartDigraph>();
   547     checkDigraphSnapshot<SmartDigraph>();
   548     checkDigraphValidity<SmartDigraph>();
   549   }
   550   { // Checking StaticDigraph
   551     checkStaticDigraph();
   552   }
   553   { // Checking FullDigraph
   554     checkFullDigraph(8);
   555   }
   556 }
   557 
   558 int main() {
   559   checkDigraphs();
   560   checkConcepts();
   561   return 0;
   562 }