test/digraph_test.cc
author Gabriel Gouvine <gabriel.gouvine.GIT@gmx.com>
Sun, 19 Mar 2017 14:38:08 +0100
changeset 1200 73bd8d5200df
parent 1092 dceba191c00d
permissions -rw-r--r--
CompactDigraph implementation (#377)

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