lemon: test/bpgraph_test.cc@a12cca3ad15a

     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-2010

     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/bpgraph.h>

    20 #include <lemon/list_graph.h>

    21 #include <lemon/smart_graph.h>

    22 #include <lemon/full_graph.h>

    24 #include "test_tools.h"

    25 #include "graph_test.h"

    27 using namespace lemon;

    28 using namespace lemon::concepts;

    30 template <class BpGraph>

    31 void checkBpGraphBuild() {

    32   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

    34   BpGraph G;

    35   checkGraphNodeList(G, 0);

    36   checkGraphRedNodeList(G, 0);

    37   checkGraphBlueNodeList(G, 0);

    38   checkGraphEdgeList(G, 0);

    39   checkGraphArcList(G, 0);

    41   G.reserveNode(3);

    42   G.reserveEdge(3);

    44   Node

    45     rn1 = G.addRedNode();

    46   checkGraphNodeList(G, 1);

    47   checkGraphRedNodeList(G, 1);

    48   checkGraphBlueNodeList(G, 0);

    49   checkGraphEdgeList(G, 0);

    50   checkGraphArcList(G, 0);

    52   Node

    53     bn1 = G.addBlueNode(),

    54     bn2 = G.addBlueNode();

    55   checkGraphNodeList(G, 3);

    56   checkGraphRedNodeList(G, 1);

    57   checkGraphBlueNodeList(G, 2);

    58   checkGraphEdgeList(G, 0);

    59   checkGraphArcList(G, 0);

    61   Edge e1 = G.addEdge(rn1, bn2);

    62   check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge");

    63   check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge");

    65   checkGraphNodeList(G, 3);

    66   checkGraphRedNodeList(G, 1);

    67   checkGraphBlueNodeList(G, 2);

    68   checkGraphEdgeList(G, 1);

    69   checkGraphArcList(G, 2);

    71   checkGraphIncEdgeArcLists(G, rn1, 1);

    72   checkGraphIncEdgeArcLists(G, bn1, 0);

    73   checkGraphIncEdgeArcLists(G, bn2, 1);

    75   checkGraphConEdgeList(G, 1);

    76   checkGraphConArcList(G, 2);

    78   Edge

    79     e2 = G.addEdge(rn1, bn1),

    80     e3 = G.addEdge(rn1, bn2);

    82   checkGraphNodeList(G, 3);

    83   checkGraphRedNodeList(G, 1);

    84   checkGraphBlueNodeList(G, 2);

    85   checkGraphEdgeList(G, 3);

    86   checkGraphArcList(G, 6);

    88   checkGraphIncEdgeArcLists(G, rn1, 3);

    89   checkGraphIncEdgeArcLists(G, bn1, 1);

    90   checkGraphIncEdgeArcLists(G, bn2, 2);

    92   checkGraphConEdgeList(G, 3);

    93   checkGraphConArcList(G, 6);

    95   checkArcDirections(G);

    97   checkNodeIds(G);

    98   checkRedNodeIds(G);

    99   checkBlueNodeIds(G);

   100   checkArcIds(G);

   101   checkEdgeIds(G);

   103   checkGraphNodeMap(G);

   104   checkGraphRedMap(G);

   105   checkGraphBlueMap(G);

   106   checkGraphArcMap(G);

   107   checkGraphEdgeMap(G);

   108 }

   110 template <class BpGraph>

   111 void checkBpGraphErase() {

   112   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   114   BpGraph G;

   115   Node

   116     n1 = G.addRedNode(), n2 = G.addBlueNode(),

   117     n3 = G.addBlueNode(), n4 = G.addRedNode();

   118   Edge

   119     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),

   120     e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);

   122   // Check edge deletion

   123   G.erase(e2);

   125   checkGraphNodeList(G, 4);

   126   checkGraphRedNodeList(G, 2);

   127   checkGraphBlueNodeList(G, 2);

   128   checkGraphEdgeList(G, 3);

   129   checkGraphArcList(G, 6);

   131   checkGraphIncEdgeArcLists(G, n1, 1);

   132   checkGraphIncEdgeArcLists(G, n2, 2);

   133   checkGraphIncEdgeArcLists(G, n3, 1);

   134   checkGraphIncEdgeArcLists(G, n4, 2);

   136   checkGraphConEdgeList(G, 3);

   137   checkGraphConArcList(G, 6);

   139   // Check node deletion

   140   G.erase(n3);

   142   checkGraphNodeList(G, 3);

   143   checkGraphRedNodeList(G, 2);

   144   checkGraphBlueNodeList(G, 1);

   145   checkGraphEdgeList(G, 2);

   146   checkGraphArcList(G, 4);

   148   checkGraphIncEdgeArcLists(G, n1, 1);

   149   checkGraphIncEdgeArcLists(G, n2, 2);

   150   checkGraphIncEdgeArcLists(G, n4, 1);

   152   checkGraphConEdgeList(G, 2);

   153   checkGraphConArcList(G, 4);

   155 }

   157 template <class BpGraph>

   158 void checkBpGraphAlter() {

   159   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   161   BpGraph G;

   162   Node

   163     n1 = G.addRedNode(), n2 = G.addBlueNode(),

   164     n3 = G.addBlueNode(), n4 = G.addRedNode();

   165   Edge

   166     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),

   167     e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);

   169   G.changeRed(e2, n4);

   170   check(G.redNode(e2) == n4, "Wrong red node");

   171   check(G.blueNode(e2) == n3, "Wrong blue node");

   173   checkGraphNodeList(G, 4);

   174   checkGraphRedNodeList(G, 2);

   175   checkGraphBlueNodeList(G, 2);

   176   checkGraphEdgeList(G, 4);

   177   checkGraphArcList(G, 8);

   179   checkGraphIncEdgeArcLists(G, n1, 1);

   180   checkGraphIncEdgeArcLists(G, n2, 2);

   181   checkGraphIncEdgeArcLists(G, n3, 2);

   182   checkGraphIncEdgeArcLists(G, n4, 3);

   184   checkGraphConEdgeList(G, 4);

   185   checkGraphConArcList(G, 8);

   187   G.changeBlue(e2, n2);

   188   check(G.redNode(e2) == n4, "Wrong red node");

   189   check(G.blueNode(e2) == n2, "Wrong blue node");

   191   checkGraphNodeList(G, 4);

   192   checkGraphRedNodeList(G, 2);

   193   checkGraphBlueNodeList(G, 2);

   194   checkGraphEdgeList(G, 4);

   195   checkGraphArcList(G, 8);

   197   checkGraphIncEdgeArcLists(G, n1, 1);

   198   checkGraphIncEdgeArcLists(G, n2, 3);

   199   checkGraphIncEdgeArcLists(G, n3, 1);

   200   checkGraphIncEdgeArcLists(G, n4, 3);

   202   checkGraphConEdgeList(G, 4);

   203   checkGraphConArcList(G, 8);

   204 }

   207 template <class BpGraph>

   208 void checkBpGraphSnapshot() {

   209   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   211   BpGraph G;

   212   Node

   213     n1 = G.addRedNode(),

   214     n2 = G.addBlueNode(),

   215     n3 = G.addBlueNode();

   216   Edge

   217     e1 = G.addEdge(n1, n2),

   218     e2 = G.addEdge(n1, n3);

   220   checkGraphNodeList(G, 3);

   221   checkGraphRedNodeList(G, 1);

   222   checkGraphBlueNodeList(G, 2);

   223   checkGraphEdgeList(G, 2);

   224   checkGraphArcList(G, 4);

   226   typename BpGraph::Snapshot snapshot(G);

   228   Node n4 = G.addRedNode();

   229   G.addEdge(n4, n2);

   230   G.addEdge(n4, n3);

   232   checkGraphNodeList(G, 4);

   233   checkGraphRedNodeList(G, 2);

   234   checkGraphBlueNodeList(G, 2);

   235   checkGraphEdgeList(G, 4);

   236   checkGraphArcList(G, 8);

   238   snapshot.restore();

   240   checkGraphNodeList(G, 3);

   241   checkGraphRedNodeList(G, 1);

   242   checkGraphBlueNodeList(G, 2);

   243   checkGraphEdgeList(G, 2);

   244   checkGraphArcList(G, 4);

   246   checkGraphIncEdgeArcLists(G, n1, 2);

   247   checkGraphIncEdgeArcLists(G, n2, 1);

   248   checkGraphIncEdgeArcLists(G, n3, 1);

   250   checkGraphConEdgeList(G, 2);

   251   checkGraphConArcList(G, 4);

   253   checkNodeIds(G);

   254   checkRedNodeIds(G);

   255   checkBlueNodeIds(G);

   256   checkArcIds(G);

   257   checkEdgeIds(G);

   259   checkGraphNodeMap(G);

   260   checkGraphRedMap(G);

   261   checkGraphBlueMap(G);

   262   checkGraphArcMap(G);

   263   checkGraphEdgeMap(G);

   265   G.addRedNode();

   266   snapshot.save(G);

   268   G.addEdge(G.addRedNode(), G.addBlueNode());

   270   snapshot.restore();

   271   snapshot.save(G);

   273   checkGraphNodeList(G, 4);

   274   checkGraphRedNodeList(G, 2);

   275   checkGraphBlueNodeList(G, 2);

   276   checkGraphEdgeList(G, 2);

   277   checkGraphArcList(G, 4);

   279   G.addEdge(G.addRedNode(), G.addBlueNode());

   281   snapshot.restore();

   283   checkGraphNodeList(G, 4);

   284   checkGraphRedNodeList(G, 2);

   285   checkGraphBlueNodeList(G, 2);

   286   checkGraphEdgeList(G, 2);

   287   checkGraphArcList(G, 4);

   288 }

   290 template <typename BpGraph>

   291 void checkBpGraphValidity() {

   292   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   293   BpGraph g;

   295   Node

   296     n1 = g.addRedNode(),

   297     n2 = g.addBlueNode(),

   298     n3 = g.addBlueNode();

   300   Edge

   301     e1 = g.addEdge(n1, n2),

   302     e2 = g.addEdge(n1, n3);

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

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

   306   check(g.valid(g.direct(e1, true)), "Wrong validity check");

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

   309   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");

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

   311 }

   313 void checkConcepts() {

   314   { // Checking graph components

   315     checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();

   317     checkConcept<IDableBpGraphComponent<>,

   318       IDableBpGraphComponent<> >();

   320     checkConcept<IterableBpGraphComponent<>,

   321       IterableBpGraphComponent<> >();

   323     checkConcept<AlterableBpGraphComponent<>,

   324       AlterableBpGraphComponent<> >();

   326     checkConcept<MappableBpGraphComponent<>,

   327       MappableBpGraphComponent<> >();

   329     checkConcept<ExtendableBpGraphComponent<>,

   330       ExtendableBpGraphComponent<> >();

   332     checkConcept<ErasableBpGraphComponent<>,

   333       ErasableBpGraphComponent<> >();

   335     checkConcept<ClearableBpGraphComponent<>,

   336       ClearableBpGraphComponent<> >();

   338   }

   339   { // Checking skeleton graph

   340     checkConcept<BpGraph, BpGraph>();

   341   }

   342   { // Checking SmartBpGraph

   343     checkConcept<BpGraph, SmartBpGraph>();

   344     checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();

   345     checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();

   346     checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();

   347   }

   348 }

   350 void checkFullBpGraph(int redNum, int blueNum) {

   351   typedef FullBpGraph BpGraph;

   352   BPGRAPH_TYPEDEFS(BpGraph);

   354   BpGraph G(redNum, blueNum);

   355   checkGraphNodeList(G, redNum + blueNum);

   356   checkGraphRedNodeList(G, redNum);

   357   checkGraphBlueNodeList(G, blueNum);

   358   checkGraphEdgeList(G, redNum * blueNum);

   359   checkGraphArcList(G, 2 * redNum * blueNum);

   361   G.resize(redNum, blueNum);

   362   checkGraphNodeList(G, redNum + blueNum);

   363   checkGraphRedNodeList(G, redNum);

   364   checkGraphBlueNodeList(G, blueNum);

   365   checkGraphEdgeList(G, redNum * blueNum);

   366   checkGraphArcList(G, 2 * redNum * blueNum);

   368   for (RedIt n(G); n != INVALID; ++n) {

   369     checkGraphOutArcList(G, n, blueNum);

   370     checkGraphInArcList(G, n, blueNum);

   371     checkGraphIncEdgeList(G, n, blueNum);

   372   }

   374   for (BlueIt n(G); n != INVALID; ++n) {

   375     checkGraphOutArcList(G, n, redNum);

   376     checkGraphInArcList(G, n, redNum);

   377     checkGraphIncEdgeList(G, n, redNum);

   378   }

   380   checkGraphConArcList(G, 2 * redNum * blueNum);

   381   checkGraphConEdgeList(G, redNum * blueNum);

   383   checkArcDirections(G);

   385   checkNodeIds(G);

   386   checkRedNodeIds(G);

   387   checkBlueNodeIds(G);

   388   checkArcIds(G);

   389   checkEdgeIds(G);

   391   checkGraphNodeMap(G);

   392   checkGraphRedMap(G);

   393   checkGraphBlueMap(G);

   394   checkGraphArcMap(G);

   395   checkGraphEdgeMap(G);

   397   for (int i = 0; i < G.redNum(); ++i) {

   398     check(G.red(G.redNode(i)), "Wrong node");

   399     check(G.redIndex(G.redNode(i)) == i, "Wrong index");

   400   }

   402   for (int i = 0; i < G.blueNum(); ++i) {

   403     check(G.blue(G.blueNode(i)), "Wrong node");

   404     check(G.blueIndex(G.blueNode(i)) == i, "Wrong index");

   405   }

   407   for (NodeIt u(G); u != INVALID; ++u) {

   408     for (NodeIt v(G); v != INVALID; ++v) {

   409       Edge e = G.edge(u, v);

   410       Arc a = G.arc(u, v);

   411       if (G.red(u) == G.red(v)) {

   412         check(e == INVALID, "Wrong edge lookup");

   413         check(a == INVALID, "Wrong arc lookup");

   414       } else {

   415         check((G.u(e) == u && G.v(e) == v) ||

   416               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");

   417         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");

   418       }

   419     }

   420   }

   422 }

   424 void checkGraphs() {

   425   { // Checking ListGraph

   426     checkBpGraphBuild<ListBpGraph>();

   427     checkBpGraphErase<ListBpGraph>();

   428     checkBpGraphAlter<ListBpGraph>();

   429     checkBpGraphSnapshot<ListBpGraph>();

   430     checkBpGraphValidity<ListBpGraph>();

   431   }

   432   { // Checking SmartGraph

   433     checkBpGraphBuild<SmartBpGraph>();

   434     checkBpGraphSnapshot<SmartBpGraph>();

   435     checkBpGraphValidity<SmartBpGraph>();

   436   }

   437   { // Checking FullBpGraph

   438     checkFullBpGraph(6, 8);

   439     checkFullBpGraph(7, 4);

   440   }

   441 }

   443 int main() {

   444   checkConcepts();

   445   checkGraphs();

   446   return 0;

   447 }

author	Balazs Dezso <deba@inf.elte.hu>
	Mon, 15 Nov 2010 09:46:08 +0100
changeset 1189	a12cca3ad15a
parent 1188	5ef0ab7b61cd
child 1193	c8fa41fcc4a7
permissions	-rw-r--r--