test/digraph_test.cc
author Balazs Dezso <deba@google.com>
Wed, 17 Oct 2018 17:52:11 +0200
changeset 1182 6b79d93e812f
parent 1085 a337a0dd3f75
child 1200 73bd8d5200df
permissions -rw-r--r--
Planar drawing algorithm now works for less than 3 nodes (#611)
     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/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   ::lemon::ignore_unused_variable_warning(a2,a3,a4);
    68 
    69   checkGraphNodeList(G, 3);
    70   checkGraphArcList(G, 4);
    71 
    72   checkGraphOutArcList(G, n1, 1);
    73   checkGraphOutArcList(G, n2, 3);
    74   checkGraphOutArcList(G, n3, 0);
    75 
    76   checkGraphInArcList(G, n1, 1);
    77   checkGraphInArcList(G, n2, 1);
    78   checkGraphInArcList(G, n3, 2);
    79 
    80   checkGraphConArcList(G, 4);
    81 
    82   checkNodeIds(G);
    83   checkArcIds(G);
    84   checkGraphNodeMap(G);
    85   checkGraphArcMap(G);
    86 }
    87 
    88 template <class Digraph>
    89 void checkDigraphSplit() {
    90   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    91 
    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   ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4);
    97 
    98   Node n4 = G.split(n2);
    99 
   100   check(G.target(OutArcIt(G, n2)) == n4 &&
   101         G.source(InArcIt(G, n4)) == n2,
   102         "Wrong split.");
   103 
   104   checkGraphNodeList(G, 4);
   105   checkGraphArcList(G, 5);
   106 
   107   checkGraphOutArcList(G, n1, 1);
   108   checkGraphOutArcList(G, n2, 1);
   109   checkGraphOutArcList(G, n3, 0);
   110   checkGraphOutArcList(G, n4, 3);
   111 
   112   checkGraphInArcList(G, n1, 1);
   113   checkGraphInArcList(G, n2, 1);
   114   checkGraphInArcList(G, n3, 2);
   115   checkGraphInArcList(G, n4, 1);
   116 
   117   checkGraphConArcList(G, 5);
   118 }
   119 
   120 template <class Digraph>
   121 void checkDigraphAlter() {
   122   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   123 
   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   ::lemon::ignore_unused_variable_warning(a1,a2,a3,a5);
   131 
   132   checkGraphNodeList(G, 4);
   133   checkGraphArcList(G, 5);
   134 
   135   // Check changeSource() and changeTarget()
   136   G.changeTarget(a4, n1);
   137 
   138   checkGraphNodeList(G, 4);
   139   checkGraphArcList(G, 5);
   140 
   141   checkGraphOutArcList(G, n1, 1);
   142   checkGraphOutArcList(G, n2, 1);
   143   checkGraphOutArcList(G, n3, 0);
   144   checkGraphOutArcList(G, n4, 3);
   145 
   146   checkGraphInArcList(G, n1, 2);
   147   checkGraphInArcList(G, n2, 1);
   148   checkGraphInArcList(G, n3, 1);
   149   checkGraphInArcList(G, n4, 1);
   150 
   151   checkGraphConArcList(G, 5);
   152 
   153   G.changeSource(a4, n3);
   154 
   155   checkGraphNodeList(G, 4);
   156   checkGraphArcList(G, 5);
   157 
   158   checkGraphOutArcList(G, n1, 1);
   159   checkGraphOutArcList(G, n2, 1);
   160   checkGraphOutArcList(G, n3, 1);
   161   checkGraphOutArcList(G, n4, 2);
   162 
   163   checkGraphInArcList(G, n1, 2);
   164   checkGraphInArcList(G, n2, 1);
   165   checkGraphInArcList(G, n3, 1);
   166   checkGraphInArcList(G, n4, 1);
   167 
   168   checkGraphConArcList(G, 5);
   169 
   170   // Check contract()
   171   G.contract(n2, n4, false);
   172 
   173   checkGraphNodeList(G, 3);
   174   checkGraphArcList(G, 5);
   175 
   176   checkGraphOutArcList(G, n1, 1);
   177   checkGraphOutArcList(G, n2, 3);
   178   checkGraphOutArcList(G, n3, 1);
   179 
   180   checkGraphInArcList(G, n1, 2);
   181   checkGraphInArcList(G, n2, 2);
   182   checkGraphInArcList(G, n3, 1);
   183 
   184   checkGraphConArcList(G, 5);
   185 
   186   G.contract(n2, n1);
   187 
   188   checkGraphNodeList(G, 2);
   189   checkGraphArcList(G, 3);
   190 
   191   checkGraphOutArcList(G, n2, 2);
   192   checkGraphOutArcList(G, n3, 1);
   193 
   194   checkGraphInArcList(G, n2, 2);
   195   checkGraphInArcList(G, n3, 1);
   196 
   197   checkGraphConArcList(G, 3);
   198 }
   199 
   200 template <class Digraph>
   201 void checkDigraphErase() {
   202   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   203 
   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   ::lemon::ignore_unused_variable_warning(a2,a3,a4,a5);
   211 
   212   // Check arc deletion
   213   G.erase(a1);
   214 
   215   checkGraphNodeList(G, 4);
   216   checkGraphArcList(G, 4);
   217 
   218   checkGraphOutArcList(G, n1, 0);
   219   checkGraphOutArcList(G, n2, 1);
   220   checkGraphOutArcList(G, n3, 1);
   221   checkGraphOutArcList(G, n4, 2);
   222 
   223   checkGraphInArcList(G, n1, 2);
   224   checkGraphInArcList(G, n2, 0);
   225   checkGraphInArcList(G, n3, 1);
   226   checkGraphInArcList(G, n4, 1);
   227 
   228   checkGraphConArcList(G, 4);
   229 
   230   // Check node deletion
   231   G.erase(n4);
   232 
   233   checkGraphNodeList(G, 3);
   234   checkGraphArcList(G, 1);
   235 
   236   checkGraphOutArcList(G, n1, 0);
   237   checkGraphOutArcList(G, n2, 0);
   238   checkGraphOutArcList(G, n3, 1);
   239   checkGraphOutArcList(G, n4, 0);
   240 
   241   checkGraphInArcList(G, n1, 1);
   242   checkGraphInArcList(G, n2, 0);
   243   checkGraphInArcList(G, n3, 0);
   244   checkGraphInArcList(G, n4, 0);
   245 
   246   checkGraphConArcList(G, 1);
   247 }
   248 
   249 
   250 template <class Digraph>
   251 void checkDigraphSnapshot() {
   252   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   253 
   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   ::lemon::ignore_unused_variable_warning(a1,a2,a3,a4);
   259 
   260   typename Digraph::Snapshot snapshot(G);
   261 
   262   Node n = G.addNode();
   263   G.addArc(n3, n);
   264   G.addArc(n, n3);
   265 
   266   checkGraphNodeList(G, 4);
   267   checkGraphArcList(G, 6);
   268 
   269   snapshot.restore();
   270 
   271   checkGraphNodeList(G, 3);
   272   checkGraphArcList(G, 4);
   273 
   274   checkGraphOutArcList(G, n1, 1);
   275   checkGraphOutArcList(G, n2, 3);
   276   checkGraphOutArcList(G, n3, 0);
   277 
   278   checkGraphInArcList(G, n1, 1);
   279   checkGraphInArcList(G, n2, 1);
   280   checkGraphInArcList(G, n3, 2);
   281 
   282   checkGraphConArcList(G, 4);
   283 
   284   checkNodeIds(G);
   285   checkArcIds(G);
   286   checkGraphNodeMap(G);
   287   checkGraphArcMap(G);
   288 
   289   G.addNode();
   290   snapshot.save(G);
   291 
   292   G.addArc(G.addNode(), G.addNode());
   293 
   294   snapshot.restore();
   295   snapshot.save(G);
   296 
   297   checkGraphNodeList(G, 4);
   298   checkGraphArcList(G, 4);
   299 
   300   G.addArc(G.addNode(), G.addNode());
   301 
   302   snapshot.restore();
   303 
   304   checkGraphNodeList(G, 4);
   305   checkGraphArcList(G, 4);
   306 }
   307 
   308 void checkConcepts() {
   309   { // Checking digraph components
   310     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
   311 
   312     checkConcept<IDableDigraphComponent<>,
   313       IDableDigraphComponent<> >();
   314 
   315     checkConcept<IterableDigraphComponent<>,
   316       IterableDigraphComponent<> >();
   317 
   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 }
   345 
   346 template <typename Digraph>
   347 void checkDigraphValidity() {
   348   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   349   Digraph g;
   350 
   351   Node
   352     n1 = g.addNode(),
   353     n2 = g.addNode(),
   354     n3 = g.addNode();
   355 
   356   Arc
   357     e1 = g.addArc(n1, n2),
   358     e2 = g.addArc(n2, n3);
   359   ::lemon::ignore_unused_variable_warning(e2);
   360 
   361   check(g.valid(n1), "Wrong validity check");
   362   check(g.valid(e1), "Wrong validity check");
   363 
   364   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   365   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   366 }
   367 
   368 template <typename Digraph>
   369 void checkDigraphValidityErase() {
   370   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   371   Digraph g;
   372 
   373   Node
   374     n1 = g.addNode(),
   375     n2 = g.addNode(),
   376     n3 = g.addNode();
   377 
   378   Arc
   379     e1 = g.addArc(n1, n2),
   380     e2 = g.addArc(n2, n3);
   381 
   382   check(g.valid(n1), "Wrong validity check");
   383   check(g.valid(e1), "Wrong validity check");
   384 
   385   g.erase(n1);
   386 
   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");
   392 
   393   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   394   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   395 }
   396 
   397 void checkStaticDigraph() {
   398   SmartDigraph g;
   399   SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
   400   SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
   401 
   402   StaticDigraph G;
   403 
   404   checkGraphNodeList(G, 0);
   405   checkGraphArcList(G, 0);
   406 
   407   G.build(g, nref, aref);
   408 
   409   checkGraphNodeList(G, 0);
   410   checkGraphArcList(G, 0);
   411 
   412   SmartDigraph::Node
   413     n1 = g.addNode(),
   414     n2 = g.addNode(),
   415     n3 = g.addNode();
   416 
   417   G.build(g, nref, aref);
   418 
   419   checkGraphNodeList(G, 3);
   420   checkGraphArcList(G, 0);
   421 
   422   SmartDigraph::Arc a1 = g.addArc(n1, n2);
   423 
   424   G.build(g, nref, aref);
   425 
   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);
   430 
   431   checkGraphOutArcList(G, nref[n1], 1);
   432   checkGraphOutArcList(G, nref[n2], 0);
   433   checkGraphOutArcList(G, nref[n3], 0);
   434 
   435   checkGraphInArcList(G, nref[n1], 0);
   436   checkGraphInArcList(G, nref[n2], 1);
   437   checkGraphInArcList(G, nref[n3], 0);
   438 
   439   checkGraphConArcList(G, 1);
   440 
   441   SmartDigraph::Arc
   442     a2 = g.addArc(n2, n1),
   443     a3 = g.addArc(n2, n3),
   444     a4 = g.addArc(n2, n3);
   445   ::lemon::ignore_unused_variable_warning(a2,a3,a4);
   446 
   447   digraphCopy(g, G).nodeRef(nref).run();
   448 
   449   checkGraphNodeList(G, 3);
   450   checkGraphArcList(G, 4);
   451 
   452   checkGraphOutArcList(G, nref[n1], 1);
   453   checkGraphOutArcList(G, nref[n2], 3);
   454   checkGraphOutArcList(G, nref[n3], 0);
   455 
   456   checkGraphInArcList(G, nref[n1], 1);
   457   checkGraphInArcList(G, nref[n2], 1);
   458   checkGraphInArcList(G, nref[n3], 2);
   459 
   460   checkGraphConArcList(G, 4);
   461 
   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));
   472 
   473   G.build(6, arcs.begin(), arcs.end());
   474 
   475   checkGraphNodeList(G, 6);
   476   checkGraphArcList(G, 9);
   477 
   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);
   484 
   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);
   491 
   492   checkGraphConArcList(G, 9);
   493 
   494   checkNodeIds(G);
   495   checkArcIds(G);
   496   checkGraphNodeMap(G);
   497   checkGraphArcMap(G);
   498 
   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 }
   504 
   505 void checkFullDigraph(int num) {
   506   typedef FullDigraph Digraph;
   507   DIGRAPH_TYPEDEFS(Digraph);
   508 
   509   Digraph G(num);
   510   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
   511 
   512   G.resize(num);
   513   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
   514 
   515   checkGraphNodeList(G, num);
   516   checkGraphArcList(G, num * num);
   517 
   518   for (NodeIt n(G); n != INVALID; ++n) {
   519     checkGraphOutArcList(G, n, num);
   520     checkGraphInArcList(G, n, num);
   521   }
   522 
   523   checkGraphConArcList(G, num * num);
   524 
   525   checkNodeIds(G);
   526   checkArcIds(G);
   527   checkGraphNodeMap(G);
   528   checkGraphArcMap(G);
   529 
   530   for (int i = 0; i < G.nodeNum(); ++i) {
   531     check(G.index(G(i)) == i, "Wrong index");
   532   }
   533 
   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 }
   541 
   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 }
   564 
   565 int main() {
   566   checkDigraphs();
   567   checkConcepts();
   568   return 0;
   569 }