test/digraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 29 Sep 2009 12:03:02 +0200
changeset 777 5764dd9b6e18
parent 776 eff1caf6d32e
child 780 580af8cf2f6a
permissions -rw-r--r--
Add a new build() function to StaticDigraph (#68)

This function builds the digraph from an arc list that
contains pairs of integer indices from the range [0..n-1].
It is useful in the cases when you would like to build a
StaticDigraph from scratch, i.e. you do not want to build
another digraph that can be copied using the other build()
function.
     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   Node
    40     n1 = G.addNode(),
    41     n2 = G.addNode(),
    42     n3 = G.addNode();
    43   checkGraphNodeList(G, 3);
    44   checkGraphArcList(G, 0);
    45 
    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);
    50 
    51   checkGraphOutArcList(G, n1, 1);
    52   checkGraphOutArcList(G, n2, 0);
    53   checkGraphOutArcList(G, n3, 0);
    54 
    55   checkGraphInArcList(G, n1, 0);
    56   checkGraphInArcList(G, n2, 1);
    57   checkGraphInArcList(G, n3, 0);
    58 
    59   checkGraphConArcList(G, 1);
    60 
    61   Arc a2 = G.addArc(n2, n1),
    62       a3 = G.addArc(n2, n3),
    63       a4 = G.addArc(n2, n3);
    64 
    65   checkGraphNodeList(G, 3);
    66   checkGraphArcList(G, 4);
    67 
    68   checkGraphOutArcList(G, n1, 1);
    69   checkGraphOutArcList(G, n2, 3);
    70   checkGraphOutArcList(G, n3, 0);
    71 
    72   checkGraphInArcList(G, n1, 1);
    73   checkGraphInArcList(G, n2, 1);
    74   checkGraphInArcList(G, n3, 2);
    75 
    76   checkGraphConArcList(G, 4);
    77 
    78   checkNodeIds(G);
    79   checkArcIds(G);
    80   checkGraphNodeMap(G);
    81   checkGraphArcMap(G);
    82 }
    83 
    84 template <class Digraph>
    85 void checkDigraphSplit() {
    86   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    87 
    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);
    92 
    93   Node n4 = G.split(n2);
    94 
    95   check(G.target(OutArcIt(G, n2)) == n4 &&
    96         G.source(InArcIt(G, n4)) == n2,
    97         "Wrong split.");
    98 
    99   checkGraphNodeList(G, 4);
   100   checkGraphArcList(G, 5);
   101 
   102   checkGraphOutArcList(G, n1, 1);
   103   checkGraphOutArcList(G, n2, 1);
   104   checkGraphOutArcList(G, n3, 0);
   105   checkGraphOutArcList(G, n4, 3);
   106 
   107   checkGraphInArcList(G, n1, 1);
   108   checkGraphInArcList(G, n2, 1);
   109   checkGraphInArcList(G, n3, 2);
   110   checkGraphInArcList(G, n4, 1);
   111 
   112   checkGraphConArcList(G, 5);
   113 }
   114 
   115 template <class Digraph>
   116 void checkDigraphAlter() {
   117   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   118 
   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);
   125 
   126   checkGraphNodeList(G, 4);
   127   checkGraphArcList(G, 5);
   128 
   129   // Check changeSource() and changeTarget()
   130   G.changeTarget(a4, n1);
   131 
   132   checkGraphNodeList(G, 4);
   133   checkGraphArcList(G, 5);
   134 
   135   checkGraphOutArcList(G, n1, 1);
   136   checkGraphOutArcList(G, n2, 1);
   137   checkGraphOutArcList(G, n3, 0);
   138   checkGraphOutArcList(G, n4, 3);
   139 
   140   checkGraphInArcList(G, n1, 2);
   141   checkGraphInArcList(G, n2, 1);
   142   checkGraphInArcList(G, n3, 1);
   143   checkGraphInArcList(G, n4, 1);
   144 
   145   checkGraphConArcList(G, 5);
   146 
   147   G.changeSource(a4, n3);
   148 
   149   checkGraphNodeList(G, 4);
   150   checkGraphArcList(G, 5);
   151 
   152   checkGraphOutArcList(G, n1, 1);
   153   checkGraphOutArcList(G, n2, 1);
   154   checkGraphOutArcList(G, n3, 1);
   155   checkGraphOutArcList(G, n4, 2);
   156 
   157   checkGraphInArcList(G, n1, 2);
   158   checkGraphInArcList(G, n2, 1);
   159   checkGraphInArcList(G, n3, 1);
   160   checkGraphInArcList(G, n4, 1);
   161 
   162   checkGraphConArcList(G, 5);
   163 
   164   // Check contract()
   165   G.contract(n2, n4, false);
   166 
   167   checkGraphNodeList(G, 3);
   168   checkGraphArcList(G, 5);
   169 
   170   checkGraphOutArcList(G, n1, 1);
   171   checkGraphOutArcList(G, n2, 3);
   172   checkGraphOutArcList(G, n3, 1);
   173 
   174   checkGraphInArcList(G, n1, 2);
   175   checkGraphInArcList(G, n2, 2);
   176   checkGraphInArcList(G, n3, 1);
   177 
   178   checkGraphConArcList(G, 5);
   179 
   180   G.contract(n2, n1);
   181 
   182   checkGraphNodeList(G, 2);
   183   checkGraphArcList(G, 3);
   184 
   185   checkGraphOutArcList(G, n2, 2);
   186   checkGraphOutArcList(G, n3, 1);
   187 
   188   checkGraphInArcList(G, n2, 2);
   189   checkGraphInArcList(G, n3, 1);
   190 
   191   checkGraphConArcList(G, 3);
   192 }
   193 
   194 template <class Digraph>
   195 void checkDigraphErase() {
   196   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   197 
   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);
   204 
   205   // Check arc deletion
   206   G.erase(a1);
   207 
   208   checkGraphNodeList(G, 4);
   209   checkGraphArcList(G, 4);
   210 
   211   checkGraphOutArcList(G, n1, 0);
   212   checkGraphOutArcList(G, n2, 1);
   213   checkGraphOutArcList(G, n3, 1);
   214   checkGraphOutArcList(G, n4, 2);
   215 
   216   checkGraphInArcList(G, n1, 2);
   217   checkGraphInArcList(G, n2, 0);
   218   checkGraphInArcList(G, n3, 1);
   219   checkGraphInArcList(G, n4, 1);
   220 
   221   checkGraphConArcList(G, 4);
   222 
   223   // Check node deletion
   224   G.erase(n4);
   225 
   226   checkGraphNodeList(G, 3);
   227   checkGraphArcList(G, 1);
   228 
   229   checkGraphOutArcList(G, n1, 0);
   230   checkGraphOutArcList(G, n2, 0);
   231   checkGraphOutArcList(G, n3, 1);
   232   checkGraphOutArcList(G, n4, 0);
   233 
   234   checkGraphInArcList(G, n1, 1);
   235   checkGraphInArcList(G, n2, 0);
   236   checkGraphInArcList(G, n3, 0);
   237   checkGraphInArcList(G, n4, 0);
   238 
   239   checkGraphConArcList(G, 1);
   240 }
   241 
   242 
   243 template <class Digraph>
   244 void checkDigraphSnapshot() {
   245   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   246 
   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);
   251 
   252   typename Digraph::Snapshot snapshot(G);
   253 
   254   Node n = G.addNode();
   255   G.addArc(n3, n);
   256   G.addArc(n, n3);
   257 
   258   checkGraphNodeList(G, 4);
   259   checkGraphArcList(G, 6);
   260 
   261   snapshot.restore();
   262 
   263   checkGraphNodeList(G, 3);
   264   checkGraphArcList(G, 4);
   265 
   266   checkGraphOutArcList(G, n1, 1);
   267   checkGraphOutArcList(G, n2, 3);
   268   checkGraphOutArcList(G, n3, 0);
   269 
   270   checkGraphInArcList(G, n1, 1);
   271   checkGraphInArcList(G, n2, 1);
   272   checkGraphInArcList(G, n3, 2);
   273 
   274   checkGraphConArcList(G, 4);
   275 
   276   checkNodeIds(G);
   277   checkArcIds(G);
   278   checkGraphNodeMap(G);
   279   checkGraphArcMap(G);
   280 
   281   G.addNode();
   282   snapshot.save(G);
   283 
   284   G.addArc(G.addNode(), G.addNode());
   285 
   286   snapshot.restore();
   287 
   288   checkGraphNodeList(G, 4);
   289   checkGraphArcList(G, 4);
   290 }
   291 
   292 void checkConcepts() {
   293   { // Checking digraph components
   294     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   295 
   296     checkConcept<IDableDigraphComponent<>,
   297       IDableDigraphComponent<> >();
   298 
   299     checkConcept<IterableDigraphComponent<>,
   300       IterableDigraphComponent<> >();
   301 
   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 }
   329 
   330 template <typename Digraph>
   331 void checkDigraphValidity() {
   332   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   333   Digraph g;
   334 
   335   Node
   336     n1 = g.addNode(),
   337     n2 = g.addNode(),
   338     n3 = g.addNode();
   339 
   340   Arc
   341     e1 = g.addArc(n1, n2),
   342     e2 = g.addArc(n2, n3);
   343 
   344   check(g.valid(n1), "Wrong validity check");
   345   check(g.valid(e1), "Wrong validity check");
   346 
   347   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   348   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   349 }
   350 
   351 template <typename Digraph>
   352 void checkDigraphValidityErase() {
   353   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   354   Digraph g;
   355 
   356   Node
   357     n1 = g.addNode(),
   358     n2 = g.addNode(),
   359     n3 = g.addNode();
   360 
   361   Arc
   362     e1 = g.addArc(n1, n2),
   363     e2 = g.addArc(n2, n3);
   364 
   365   check(g.valid(n1), "Wrong validity check");
   366   check(g.valid(e1), "Wrong validity check");
   367 
   368   g.erase(n1);
   369 
   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");
   375 
   376   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   377   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   378 }
   379 
   380 void checkStaticDigraph() {
   381   SmartDigraph g;
   382   SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
   383   SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
   384   
   385   StaticDigraph G;
   386   
   387   checkGraphNodeList(G, 0);
   388   checkGraphArcList(G, 0);
   389 
   390   G.build(g, nref, aref);
   391 
   392   checkGraphNodeList(G, 0);
   393   checkGraphArcList(G, 0);
   394 
   395   SmartDigraph::Node
   396     n1 = g.addNode(),
   397     n2 = g.addNode(),
   398     n3 = g.addNode();
   399 
   400   G.build(g, nref, aref);
   401 
   402   checkGraphNodeList(G, 3);
   403   checkGraphArcList(G, 0);
   404 
   405   SmartDigraph::Arc a1 = g.addArc(n1, n2);
   406 
   407   G.build(g, nref, aref);
   408 
   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);
   413 
   414   checkGraphOutArcList(G, nref[n1], 1);
   415   checkGraphOutArcList(G, nref[n2], 0);
   416   checkGraphOutArcList(G, nref[n3], 0);
   417 
   418   checkGraphInArcList(G, nref[n1], 0);
   419   checkGraphInArcList(G, nref[n2], 1);
   420   checkGraphInArcList(G, nref[n3], 0);
   421 
   422   checkGraphConArcList(G, 1);
   423 
   424   SmartDigraph::Arc
   425     a2 = g.addArc(n2, n1),
   426     a3 = g.addArc(n2, n3),
   427     a4 = g.addArc(n2, n3);
   428 
   429   digraphCopy(g, G).nodeRef(nref).run();
   430 
   431   checkGraphNodeList(G, 3);
   432   checkGraphArcList(G, 4);
   433 
   434   checkGraphOutArcList(G, nref[n1], 1);
   435   checkGraphOutArcList(G, nref[n2], 3);
   436   checkGraphOutArcList(G, nref[n3], 0);
   437 
   438   checkGraphInArcList(G, nref[n1], 1);
   439   checkGraphInArcList(G, nref[n2], 1);
   440   checkGraphInArcList(G, nref[n3], 2);
   441 
   442   checkGraphConArcList(G, 4);
   443 
   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));
   454 
   455   G.build(6, arcs.begin(), arcs.end());
   456   
   457   checkGraphNodeList(G, 6);
   458   checkGraphArcList(G, 9);
   459 
   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);
   466 
   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);
   473 
   474   checkGraphConArcList(G, 9);
   475 
   476   checkNodeIds(G);
   477   checkArcIds(G);
   478   checkGraphNodeMap(G);
   479   checkGraphArcMap(G);
   480   
   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 }
   486 
   487 void checkFullDigraph(int num) {
   488   typedef FullDigraph Digraph;
   489   DIGRAPH_TYPEDEFS(Digraph);
   490   Digraph G(num);
   491 
   492   checkGraphNodeList(G, num);
   493   checkGraphArcList(G, num * num);
   494 
   495   for (NodeIt n(G); n != INVALID; ++n) {
   496     checkGraphOutArcList(G, n, num);
   497     checkGraphInArcList(G, n, num);
   498   }
   499 
   500   checkGraphConArcList(G, num * num);
   501 
   502   checkNodeIds(G);
   503   checkArcIds(G);
   504   checkGraphNodeMap(G);
   505   checkGraphArcMap(G);
   506 
   507   for (int i = 0; i < G.nodeNum(); ++i) {
   508     check(G.index(G(i)) == i, "Wrong index");
   509   }
   510 
   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 }
   518 
   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 }
   541 
   542 int main() {
   543   checkDigraphs();
   544   checkConcepts();
   545   return 0;
   546 }