lemon-main: test/digraph_test.cc@c6aa2cc1af04

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

    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>

    26 #include "test_tools.h"

    27 #include "graph_test.h"

    29 using namespace lemon;

    30 using namespace lemon::concepts;

    32 template <class Digraph>

    33 void checkDigraphBuild() {

    34   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    35   Digraph G;

    37   checkGraphNodeList(G, 0);

    38   checkGraphArcList(G, 0);

    40   G.reserveNode(3);

    41   G.reserveArc(4);

    43   Node

    44     n1 = G.addNode(),

    45     n2 = G.addNode(),

    46     n3 = G.addNode();

    47   checkGraphNodeList(G, 3);

    48   checkGraphArcList(G, 0);

    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);

    55   checkGraphOutArcList(G, n1, 1);

    56   checkGraphOutArcList(G, n2, 0);

    57   checkGraphOutArcList(G, n3, 0);

    59   checkGraphInArcList(G, n1, 0);

    60   checkGraphInArcList(G, n2, 1);

    61   checkGraphInArcList(G, n3, 0);

    63   checkGraphConArcList(G, 1);

    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);

    70   checkGraphNodeList(G, 3);

    71   checkGraphArcList(G, 4);

    73   checkGraphOutArcList(G, n1, 1);

    74   checkGraphOutArcList(G, n2, 3);

    75   checkGraphOutArcList(G, n3, 0);

    77   checkGraphInArcList(G, n1, 1);

    78   checkGraphInArcList(G, n2, 1);

    79   checkGraphInArcList(G, n3, 2);

    81   checkGraphConArcList(G, 4);

    83   checkNodeIds(G);

    84   checkArcIds(G);

    85   checkGraphNodeMap(G);

    86   checkGraphArcMap(G);

    87 }

    89 template <class Digraph>

    90 void checkDigraphSplit() {

    91   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    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);

    99   Node n4 = G.split(n2);

   101   check(G.target(OutArcIt(G, n2)) == n4 &&

   102         G.source(InArcIt(G, n4)) == n2,

   103         "Wrong split.");

   105   checkGraphNodeList(G, 4);

   106   checkGraphArcList(G, 5);

   108   checkGraphOutArcList(G, n1, 1);

   109   checkGraphOutArcList(G, n2, 1);

   110   checkGraphOutArcList(G, n3, 0);

   111   checkGraphOutArcList(G, n4, 3);

   113   checkGraphInArcList(G, n1, 1);

   114   checkGraphInArcList(G, n2, 1);

   115   checkGraphInArcList(G, n3, 2);

   116   checkGraphInArcList(G, n4, 1);

   118   checkGraphConArcList(G, 5);

   119 }

   121 template <class Digraph>

   122 void checkDigraphAlter() {

   123   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   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);

   133   checkGraphNodeList(G, 4);

   134   checkGraphArcList(G, 5);

   136   // Check changeSource() and changeTarget()

   137   G.changeTarget(a4, n1);

   139   checkGraphNodeList(G, 4);

   140   checkGraphArcList(G, 5);

   142   checkGraphOutArcList(G, n1, 1);

   143   checkGraphOutArcList(G, n2, 1);

   144   checkGraphOutArcList(G, n3, 0);

   145   checkGraphOutArcList(G, n4, 3);

   147   checkGraphInArcList(G, n1, 2);

   148   checkGraphInArcList(G, n2, 1);

   149   checkGraphInArcList(G, n3, 1);

   150   checkGraphInArcList(G, n4, 1);

   152   checkGraphConArcList(G, 5);

   154   G.changeSource(a4, n3);

   156   checkGraphNodeList(G, 4);

   157   checkGraphArcList(G, 5);

   159   checkGraphOutArcList(G, n1, 1);

   160   checkGraphOutArcList(G, n2, 1);

   161   checkGraphOutArcList(G, n3, 1);

   162   checkGraphOutArcList(G, n4, 2);

   164   checkGraphInArcList(G, n1, 2);

   165   checkGraphInArcList(G, n2, 1);

   166   checkGraphInArcList(G, n3, 1);

   167   checkGraphInArcList(G, n4, 1);

   169   checkGraphConArcList(G, 5);

   171   // Check contract()

   172   G.contract(n2, n4, false);

   174   checkGraphNodeList(G, 3);

   175   checkGraphArcList(G, 5);

   177   checkGraphOutArcList(G, n1, 1);

   178   checkGraphOutArcList(G, n2, 3);

   179   checkGraphOutArcList(G, n3, 1);

   181   checkGraphInArcList(G, n1, 2);

   182   checkGraphInArcList(G, n2, 2);

   183   checkGraphInArcList(G, n3, 1);

   185   checkGraphConArcList(G, 5);

   187   G.contract(n2, n1);

   189   checkGraphNodeList(G, 2);

   190   checkGraphArcList(G, 3);

   192   checkGraphOutArcList(G, n2, 2);

   193   checkGraphOutArcList(G, n3, 1);

   195   checkGraphInArcList(G, n2, 2);

   196   checkGraphInArcList(G, n3, 1);

   198   checkGraphConArcList(G, 3);

   199 }

   201 template <class Digraph>

   202 void checkDigraphErase() {

   203   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   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);

   213   // Check arc deletion

   214   G.erase(a1);

   216   checkGraphNodeList(G, 4);

   217   checkGraphArcList(G, 4);

   219   checkGraphOutArcList(G, n1, 0);

   220   checkGraphOutArcList(G, n2, 1);

   221   checkGraphOutArcList(G, n3, 1);

   222   checkGraphOutArcList(G, n4, 2);

   224   checkGraphInArcList(G, n1, 2);

   225   checkGraphInArcList(G, n2, 0);

   226   checkGraphInArcList(G, n3, 1);

   227   checkGraphInArcList(G, n4, 1);

   229   checkGraphConArcList(G, 4);

   231   // Check node deletion

   232   G.erase(n4);

   234   checkGraphNodeList(G, 3);

   235   checkGraphArcList(G, 1);

   237   checkGraphOutArcList(G, n1, 0);

   238   checkGraphOutArcList(G, n2, 0);

   239   checkGraphOutArcList(G, n3, 1);

   240   checkGraphOutArcList(G, n4, 0);

   242   checkGraphInArcList(G, n1, 1);

   243   checkGraphInArcList(G, n2, 0);

   244   checkGraphInArcList(G, n3, 0);

   245   checkGraphInArcList(G, n4, 0);

   247   checkGraphConArcList(G, 1);

   248 }

   251 template <class Digraph>

   252 void checkDigraphSnapshot() {

   253   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   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);

   261   typename Digraph::Snapshot snapshot(G);

   263   Node n = G.addNode();

   264   G.addArc(n3, n);

   265   G.addArc(n, n3);

   267   checkGraphNodeList(G, 4);

   268   checkGraphArcList(G, 6);

   270   snapshot.restore();

   272   checkGraphNodeList(G, 3);

   273   checkGraphArcList(G, 4);

   275   checkGraphOutArcList(G, n1, 1);

   276   checkGraphOutArcList(G, n2, 3);

   277   checkGraphOutArcList(G, n3, 0);

   279   checkGraphInArcList(G, n1, 1);

   280   checkGraphInArcList(G, n2, 1);

   281   checkGraphInArcList(G, n3, 2);

   283   checkGraphConArcList(G, 4);

   285   checkNodeIds(G);

   286   checkArcIds(G);

   287   checkGraphNodeMap(G);

   288   checkGraphArcMap(G);

   290   G.addNode();

   291   snapshot.save(G);

   293   G.addArc(G.addNode(), G.addNode());

   295   snapshot.restore();

   296   snapshot.save(G);

   298   checkGraphNodeList(G, 4);

   299   checkGraphArcList(G, 4);

   301   G.addArc(G.addNode(), G.addNode());

   303   snapshot.restore();

   305   checkGraphNodeList(G, 4);

   306   checkGraphArcList(G, 4);

   307 }

   309 void checkConcepts() {

   310   { // Checking digraph components

   311     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();

   313     checkConcept<IDableDigraphComponent<>,

   314       IDableDigraphComponent<> >();

   316     checkConcept<IterableDigraphComponent<>,

   317       IterableDigraphComponent<> >();

   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 }

   351 template <typename Digraph>

   352 void checkDigraphValidity() {

   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);

   364   ::lemon::ignore_unused_variable_warning(e2);

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

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

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

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

   371 }

   373 template <typename Digraph>

   374 void checkDigraphValidityErase() {

   375   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

   376   Digraph g;

   378   Node

   379     n1 = g.addNode(),

   380     n2 = g.addNode(),

   381     n3 = g.addNode();

   383   Arc

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

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

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

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

   390   g.erase(n1);

   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");

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

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

   400 }

   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);

   408   GR G;

   410   checkGraphNodeList(G, 0);

   411   checkGraphArcList(G, 0);

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

   415   checkGraphNodeList(G, 0);

   416   checkGraphArcList(G, 0);

   418   SmartDigraph::Node

   419     n1 = g.addNode(),

   420     n2 = g.addNode(),

   421     n3 = g.addNode();

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

   425   checkGraphNodeList(G, 3);

   426   checkGraphArcList(G, 0);

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

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

   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);

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

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

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

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

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

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

   445   checkGraphConArcList(G, 1);

   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);

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

   455   checkGraphNodeList(G, 3);

   456   checkGraphArcList(G, 4);

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

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

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

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

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

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

   466   checkGraphConArcList(G, 4);

   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));

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

   481   checkGraphNodeList(G, 6);

   482   checkGraphArcList(G, 9);

   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);

   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);

   498   checkGraphConArcList(G, 9);

   500   checkNodeIds(G);

   501   checkArcIds(G);

   502   checkGraphNodeMap(G);

   503   checkGraphArcMap(G);

   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 }

   511 void checkFullDigraph(int num) {

   512   typedef FullDigraph Digraph;

   513   DIGRAPH_TYPEDEFS(Digraph);

   515   Digraph G(num);

   516   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");

   518   G.resize(num);

   519   check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");

   521   checkGraphNodeList(G, num);

   522   checkGraphArcList(G, num * num);

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

   525     checkGraphOutArcList(G, n, num);

   526     checkGraphInArcList(G, n, num);

   527   }

   529   checkGraphConArcList(G, num * num);

   531   checkNodeIds(G);

   532   checkArcIds(G);

   533   checkGraphNodeMap(G);

   534   checkGraphArcMap(G);

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

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

   538   }

   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 }

   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 }

   572 int main() {

   573   checkDigraphs();

   574   checkConcepts();

   575   return 0;

   576 }

author	Balazs Dezso <deba@google.com>
	Fri, 22 Jan 2021 10:55:32 +0100
changeset 1208	c6aa2cc1af04
parent 1092	dceba191c00d
permissions	-rw-r--r--