lemon: test/bpgraph_test.cc@97f1760dcd13

     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   RedNode

    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   BlueNode

    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(bn1, rn1),

    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   checkGraphRedNodeMap(G);

   105   checkGraphBlueNodeMap(G);

   106   checkGraphArcMap(G);

   107   checkGraphEdgeMap(G);

   108 }

   110 template <class BpGraph>

   111 void checkBpGraphErase() {

   112   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   114   BpGraph G;

   115   RedNode

   116     n1 = G.addRedNode(), n4 = G.addRedNode();

   117   BlueNode

   118     n2 = G.addBlueNode(), n3 = G.addBlueNode();

   119   Edge

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

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

   123   // Check edge deletion

   124   G.erase(e2);

   126   checkGraphNodeList(G, 4);

   127   checkGraphRedNodeList(G, 2);

   128   checkGraphBlueNodeList(G, 2);

   129   checkGraphEdgeList(G, 3);

   130   checkGraphArcList(G, 6);

   132   checkGraphIncEdgeArcLists(G, n1, 1);

   133   checkGraphIncEdgeArcLists(G, n2, 2);

   134   checkGraphIncEdgeArcLists(G, n3, 1);

   135   checkGraphIncEdgeArcLists(G, n4, 2);

   137   checkGraphConEdgeList(G, 3);

   138   checkGraphConArcList(G, 6);

   140   // Check node deletion

   141   G.erase(n3);

   143   checkGraphNodeList(G, 3);

   144   checkGraphRedNodeList(G, 2);

   145   checkGraphBlueNodeList(G, 1);

   146   checkGraphEdgeList(G, 2);

   147   checkGraphArcList(G, 4);

   149   checkGraphIncEdgeArcLists(G, n1, 1);

   150   checkGraphIncEdgeArcLists(G, n2, 2);

   151   checkGraphIncEdgeArcLists(G, n4, 1);

   153   checkGraphConEdgeList(G, 2);

   154   checkGraphConArcList(G, 4);

   156 }

   158 template <class BpGraph>

   159 void checkBpGraphAlter() {

   160   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   162   BpGraph G;

   163   RedNode

   164     n1 = G.addRedNode(), n4 = G.addRedNode();

   165   BlueNode

   166     n2 = G.addBlueNode(), n3 = G.addBlueNode();

   167   Edge

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

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

   171   G.changeRed(e2, n4);

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

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

   175   checkGraphNodeList(G, 4);

   176   checkGraphRedNodeList(G, 2);

   177   checkGraphBlueNodeList(G, 2);

   178   checkGraphEdgeList(G, 4);

   179   checkGraphArcList(G, 8);

   181   checkGraphIncEdgeArcLists(G, n1, 1);

   182   checkGraphIncEdgeArcLists(G, n2, 2);

   183   checkGraphIncEdgeArcLists(G, n3, 2);

   184   checkGraphIncEdgeArcLists(G, n4, 3);

   186   checkGraphConEdgeList(G, 4);

   187   checkGraphConArcList(G, 8);

   189   G.changeBlue(e2, n2);

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

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

   193   checkGraphNodeList(G, 4);

   194   checkGraphRedNodeList(G, 2);

   195   checkGraphBlueNodeList(G, 2);

   196   checkGraphEdgeList(G, 4);

   197   checkGraphArcList(G, 8);

   199   checkGraphIncEdgeArcLists(G, n1, 1);

   200   checkGraphIncEdgeArcLists(G, n2, 3);

   201   checkGraphIncEdgeArcLists(G, n3, 1);

   202   checkGraphIncEdgeArcLists(G, n4, 3);

   204   checkGraphConEdgeList(G, 4);

   205   checkGraphConArcList(G, 8);

   206 }

   209 template <class BpGraph>

   210 void checkBpGraphSnapshot() {

   211   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   213   BpGraph G;

   214   RedNode

   215     n1 = G.addRedNode();

   216   BlueNode

   217     n2 = G.addBlueNode(),

   218     n3 = G.addBlueNode();

   219   Edge

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

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

   223   checkGraphNodeList(G, 3);

   224   checkGraphRedNodeList(G, 1);

   225   checkGraphBlueNodeList(G, 2);

   226   checkGraphEdgeList(G, 2);

   227   checkGraphArcList(G, 4);

   229   typename BpGraph::Snapshot snapshot(G);

   231   RedNode n4 = G.addRedNode();

   232   G.addEdge(n4, n2);

   233   G.addEdge(n4, n3);

   235   checkGraphNodeList(G, 4);

   236   checkGraphRedNodeList(G, 2);

   237   checkGraphBlueNodeList(G, 2);

   238   checkGraphEdgeList(G, 4);

   239   checkGraphArcList(G, 8);

   241   snapshot.restore();

   243   checkGraphNodeList(G, 3);

   244   checkGraphRedNodeList(G, 1);

   245   checkGraphBlueNodeList(G, 2);

   246   checkGraphEdgeList(G, 2);

   247   checkGraphArcList(G, 4);

   249   checkGraphIncEdgeArcLists(G, n1, 2);

   250   checkGraphIncEdgeArcLists(G, n2, 1);

   251   checkGraphIncEdgeArcLists(G, n3, 1);

   253   checkGraphConEdgeList(G, 2);

   254   checkGraphConArcList(G, 4);

   256   checkNodeIds(G);

   257   checkRedNodeIds(G);

   258   checkBlueNodeIds(G);

   259   checkArcIds(G);

   260   checkEdgeIds(G);

   262   checkGraphNodeMap(G);

   263   checkGraphRedNodeMap(G);

   264   checkGraphBlueNodeMap(G);

   265   checkGraphArcMap(G);

   266   checkGraphEdgeMap(G);

   268   G.addRedNode();

   269   snapshot.save(G);

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

   273   snapshot.restore();

   274   snapshot.save(G);

   276   checkGraphNodeList(G, 4);

   277   checkGraphRedNodeList(G, 2);

   278   checkGraphBlueNodeList(G, 2);

   279   checkGraphEdgeList(G, 2);

   280   checkGraphArcList(G, 4);

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

   284   snapshot.restore();

   286   checkGraphNodeList(G, 4);

   287   checkGraphRedNodeList(G, 2);

   288   checkGraphBlueNodeList(G, 2);

   289   checkGraphEdgeList(G, 2);

   290   checkGraphArcList(G, 4);

   291 }

   293 template <typename BpGraph>

   294 void checkBpGraphValidity() {

   295   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   296   BpGraph g;

   298   RedNode

   299     n1 = g.addRedNode();

   300   BlueNode

   301     n2 = g.addBlueNode(),

   302     n3 = g.addBlueNode();

   304   Edge

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

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

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

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

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

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

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

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

   315 }

   317 void checkConcepts() {

   318   { // Checking graph components

   319     checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();

   321     checkConcept<IDableBpGraphComponent<>,

   322       IDableBpGraphComponent<> >();

   324     checkConcept<IterableBpGraphComponent<>,

   325       IterableBpGraphComponent<> >();

   327     checkConcept<AlterableBpGraphComponent<>,

   328       AlterableBpGraphComponent<> >();

   330     checkConcept<MappableBpGraphComponent<>,

   331       MappableBpGraphComponent<> >();

   333     checkConcept<ExtendableBpGraphComponent<>,

   334       ExtendableBpGraphComponent<> >();

   336     checkConcept<ErasableBpGraphComponent<>,

   337       ErasableBpGraphComponent<> >();

   339     checkConcept<ClearableBpGraphComponent<>,

   340       ClearableBpGraphComponent<> >();

   342   }

   343   { // Checking skeleton graph

   344     checkConcept<BpGraph, BpGraph>();

   345   }

   346   { // Checking SmartBpGraph

   347     checkConcept<BpGraph, SmartBpGraph>();

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

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

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

   351   }

   352 }

   354 void checkFullBpGraph(int redNum, int blueNum) {

   355   typedef FullBpGraph BpGraph;

   356   BPGRAPH_TYPEDEFS(BpGraph);

   358   BpGraph G(redNum, blueNum);

   359   checkGraphNodeList(G, redNum + blueNum);

   360   checkGraphRedNodeList(G, redNum);

   361   checkGraphBlueNodeList(G, blueNum);

   362   checkGraphEdgeList(G, redNum * blueNum);

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

   365   G.resize(redNum, blueNum);

   366   checkGraphNodeList(G, redNum + blueNum);

   367   checkGraphRedNodeList(G, redNum);

   368   checkGraphBlueNodeList(G, blueNum);

   369   checkGraphEdgeList(G, redNum * blueNum);

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

   372   for (RedNodeIt n(G); n != INVALID; ++n) {

   373     checkGraphOutArcList(G, n, blueNum);

   374     checkGraphInArcList(G, n, blueNum);

   375     checkGraphIncEdgeList(G, n, blueNum);

   376   }

   378   for (BlueNodeIt n(G); n != INVALID; ++n) {

   379     checkGraphOutArcList(G, n, redNum);

   380     checkGraphInArcList(G, n, redNum);

   381     checkGraphIncEdgeList(G, n, redNum);

   382   }

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

   385   checkGraphConEdgeList(G, redNum * blueNum);

   387   checkArcDirections(G);

   389   checkNodeIds(G);

   390   checkRedNodeIds(G);

   391   checkBlueNodeIds(G);

   392   checkArcIds(G);

   393   checkEdgeIds(G);

   395   checkGraphNodeMap(G);

   396   checkGraphRedNodeMap(G);

   397   checkGraphBlueNodeMap(G);

   398   checkGraphArcMap(G);

   399   checkGraphEdgeMap(G);

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

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

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

   404   }

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

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

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

   409   }

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

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

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

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

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

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

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

   418       } else {

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

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

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

   422       }

   423     }

   424   }

   426 }

   428 void checkGraphs() {

   429   { // Checking ListGraph

   430     checkBpGraphBuild<ListBpGraph>();

   431     checkBpGraphErase<ListBpGraph>();

   432     checkBpGraphAlter<ListBpGraph>();

   433     checkBpGraphSnapshot<ListBpGraph>();

   434     checkBpGraphValidity<ListBpGraph>();

   435   }

   436   { // Checking SmartGraph

   437     checkBpGraphBuild<SmartBpGraph>();

   438     checkBpGraphSnapshot<SmartBpGraph>();

   439     checkBpGraphValidity<SmartBpGraph>();

   440   }

   441   { // Checking FullBpGraph

   442     checkFullBpGraph(6, 8);

   443     checkFullBpGraph(7, 4);

   444   }

   445 }

   447 int main() {

   448   checkConcepts();

   449   checkGraphs();

   450   return 0;

   451 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Wed, 07 Aug 2013 07:04:58 +0200
changeset 1261	97f1760dcd13
parent 1193	c8fa41fcc4a7
child 1270	dceba191c00d
permissions	-rw-r--r--