test/bpgraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 28 Feb 2013 23:44:35 +0100
changeset 1060 45befc97b1bc
parent 1025 c8fa41fcc4a7
child 1092 dceba191c00d
permissions -rw-r--r--
Merge test files of Preflow and EdmondsKarp (#177)
     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  */
    18 
    19 #include <lemon/concepts/bpgraph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
    23 
    24 #include "test_tools.h"
    25 #include "graph_test.h"
    26 
    27 using namespace lemon;
    28 using namespace lemon::concepts;
    29 
    30 template <class BpGraph>
    31 void checkBpGraphBuild() {
    32   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
    33 
    34   BpGraph G;
    35   checkGraphNodeList(G, 0);
    36   checkGraphRedNodeList(G, 0);
    37   checkGraphBlueNodeList(G, 0);
    38   checkGraphEdgeList(G, 0);
    39   checkGraphArcList(G, 0);
    40 
    41   G.reserveNode(3);
    42   G.reserveEdge(3);
    43 
    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);
    51 
    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);
    60 
    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");
    64 
    65   checkGraphNodeList(G, 3);
    66   checkGraphRedNodeList(G, 1);
    67   checkGraphBlueNodeList(G, 2);
    68   checkGraphEdgeList(G, 1);
    69   checkGraphArcList(G, 2);
    70 
    71   checkGraphIncEdgeArcLists(G, rn1, 1);
    72   checkGraphIncEdgeArcLists(G, bn1, 0);
    73   checkGraphIncEdgeArcLists(G, bn2, 1);
    74 
    75   checkGraphConEdgeList(G, 1);
    76   checkGraphConArcList(G, 2);
    77 
    78   Edge
    79     e2 = G.addEdge(bn1, rn1),
    80     e3 = G.addEdge(rn1, bn2);
    81 
    82   checkGraphNodeList(G, 3);
    83   checkGraphRedNodeList(G, 1);
    84   checkGraphBlueNodeList(G, 2);
    85   checkGraphEdgeList(G, 3);
    86   checkGraphArcList(G, 6);
    87 
    88   checkGraphIncEdgeArcLists(G, rn1, 3);
    89   checkGraphIncEdgeArcLists(G, bn1, 1);
    90   checkGraphIncEdgeArcLists(G, bn2, 2);
    91 
    92   checkGraphConEdgeList(G, 3);
    93   checkGraphConArcList(G, 6);
    94 
    95   checkArcDirections(G);
    96 
    97   checkNodeIds(G);
    98   checkRedNodeIds(G);
    99   checkBlueNodeIds(G);
   100   checkArcIds(G);
   101   checkEdgeIds(G);
   102 
   103   checkGraphNodeMap(G);
   104   checkGraphRedNodeMap(G);
   105   checkGraphBlueNodeMap(G);
   106   checkGraphArcMap(G);
   107   checkGraphEdgeMap(G);
   108 }
   109 
   110 template <class BpGraph>
   111 void checkBpGraphErase() {
   112   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   113 
   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);
   122 
   123   // Check edge deletion
   124   G.erase(e2);
   125 
   126   checkGraphNodeList(G, 4);
   127   checkGraphRedNodeList(G, 2);
   128   checkGraphBlueNodeList(G, 2);
   129   checkGraphEdgeList(G, 3);
   130   checkGraphArcList(G, 6);
   131 
   132   checkGraphIncEdgeArcLists(G, n1, 1);
   133   checkGraphIncEdgeArcLists(G, n2, 2);
   134   checkGraphIncEdgeArcLists(G, n3, 1);
   135   checkGraphIncEdgeArcLists(G, n4, 2);
   136 
   137   checkGraphConEdgeList(G, 3);
   138   checkGraphConArcList(G, 6);
   139 
   140   // Check node deletion
   141   G.erase(n3);
   142 
   143   checkGraphNodeList(G, 3);
   144   checkGraphRedNodeList(G, 2);
   145   checkGraphBlueNodeList(G, 1);
   146   checkGraphEdgeList(G, 2);
   147   checkGraphArcList(G, 4);
   148 
   149   checkGraphIncEdgeArcLists(G, n1, 1);
   150   checkGraphIncEdgeArcLists(G, n2, 2);
   151   checkGraphIncEdgeArcLists(G, n4, 1);
   152 
   153   checkGraphConEdgeList(G, 2);
   154   checkGraphConArcList(G, 4);
   155 
   156 }
   157 
   158 template <class BpGraph>
   159 void checkBpGraphAlter() {
   160   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   161 
   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);
   170 
   171   G.changeRed(e2, n4);
   172   check(G.redNode(e2) == n4, "Wrong red node");
   173   check(G.blueNode(e2) == n3, "Wrong blue node");
   174 
   175   checkGraphNodeList(G, 4);
   176   checkGraphRedNodeList(G, 2);
   177   checkGraphBlueNodeList(G, 2);
   178   checkGraphEdgeList(G, 4);
   179   checkGraphArcList(G, 8);
   180 
   181   checkGraphIncEdgeArcLists(G, n1, 1);
   182   checkGraphIncEdgeArcLists(G, n2, 2);
   183   checkGraphIncEdgeArcLists(G, n3, 2);
   184   checkGraphIncEdgeArcLists(G, n4, 3);
   185 
   186   checkGraphConEdgeList(G, 4);
   187   checkGraphConArcList(G, 8);
   188 
   189   G.changeBlue(e2, n2);
   190   check(G.redNode(e2) == n4, "Wrong red node");
   191   check(G.blueNode(e2) == n2, "Wrong blue node");
   192 
   193   checkGraphNodeList(G, 4);
   194   checkGraphRedNodeList(G, 2);
   195   checkGraphBlueNodeList(G, 2);
   196   checkGraphEdgeList(G, 4);
   197   checkGraphArcList(G, 8);
   198 
   199   checkGraphIncEdgeArcLists(G, n1, 1);
   200   checkGraphIncEdgeArcLists(G, n2, 3);
   201   checkGraphIncEdgeArcLists(G, n3, 1);
   202   checkGraphIncEdgeArcLists(G, n4, 3);
   203 
   204   checkGraphConEdgeList(G, 4);
   205   checkGraphConArcList(G, 8);
   206 }
   207 
   208 
   209 template <class BpGraph>
   210 void checkBpGraphSnapshot() {
   211   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   212 
   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);
   222 
   223   checkGraphNodeList(G, 3);
   224   checkGraphRedNodeList(G, 1);
   225   checkGraphBlueNodeList(G, 2);
   226   checkGraphEdgeList(G, 2);
   227   checkGraphArcList(G, 4);
   228 
   229   typename BpGraph::Snapshot snapshot(G);
   230 
   231   RedNode n4 = G.addRedNode();
   232   G.addEdge(n4, n2);
   233   G.addEdge(n4, n3);
   234 
   235   checkGraphNodeList(G, 4);
   236   checkGraphRedNodeList(G, 2);
   237   checkGraphBlueNodeList(G, 2);
   238   checkGraphEdgeList(G, 4);
   239   checkGraphArcList(G, 8);
   240 
   241   snapshot.restore();
   242 
   243   checkGraphNodeList(G, 3);
   244   checkGraphRedNodeList(G, 1);
   245   checkGraphBlueNodeList(G, 2);
   246   checkGraphEdgeList(G, 2);
   247   checkGraphArcList(G, 4);
   248 
   249   checkGraphIncEdgeArcLists(G, n1, 2);
   250   checkGraphIncEdgeArcLists(G, n2, 1);
   251   checkGraphIncEdgeArcLists(G, n3, 1);
   252 
   253   checkGraphConEdgeList(G, 2);
   254   checkGraphConArcList(G, 4);
   255 
   256   checkNodeIds(G);
   257   checkRedNodeIds(G);
   258   checkBlueNodeIds(G);
   259   checkArcIds(G);
   260   checkEdgeIds(G);
   261 
   262   checkGraphNodeMap(G);
   263   checkGraphRedNodeMap(G);
   264   checkGraphBlueNodeMap(G);
   265   checkGraphArcMap(G);
   266   checkGraphEdgeMap(G);
   267 
   268   G.addRedNode();
   269   snapshot.save(G);
   270 
   271   G.addEdge(G.addRedNode(), G.addBlueNode());
   272 
   273   snapshot.restore();
   274   snapshot.save(G);
   275 
   276   checkGraphNodeList(G, 4);
   277   checkGraphRedNodeList(G, 2);
   278   checkGraphBlueNodeList(G, 2);
   279   checkGraphEdgeList(G, 2);
   280   checkGraphArcList(G, 4);
   281 
   282   G.addEdge(G.addRedNode(), G.addBlueNode());
   283 
   284   snapshot.restore();
   285 
   286   checkGraphNodeList(G, 4);
   287   checkGraphRedNodeList(G, 2);
   288   checkGraphBlueNodeList(G, 2);
   289   checkGraphEdgeList(G, 2);
   290   checkGraphArcList(G, 4);
   291 }
   292 
   293 template <typename BpGraph>
   294 void checkBpGraphValidity() {
   295   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   296   BpGraph g;
   297 
   298   RedNode
   299     n1 = g.addRedNode();
   300   BlueNode
   301     n2 = g.addBlueNode(),
   302     n3 = g.addBlueNode();
   303 
   304   Edge
   305     e1 = g.addEdge(n1, n2),
   306     e2 = g.addEdge(n1, n3);
   307 
   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");
   311 
   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 }
   316 
   317 void checkConcepts() {
   318   { // Checking graph components
   319     checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
   320 
   321     checkConcept<IDableBpGraphComponent<>,
   322       IDableBpGraphComponent<> >();
   323 
   324     checkConcept<IterableBpGraphComponent<>,
   325       IterableBpGraphComponent<> >();
   326 
   327     checkConcept<AlterableBpGraphComponent<>,
   328       AlterableBpGraphComponent<> >();
   329 
   330     checkConcept<MappableBpGraphComponent<>,
   331       MappableBpGraphComponent<> >();
   332 
   333     checkConcept<ExtendableBpGraphComponent<>,
   334       ExtendableBpGraphComponent<> >();
   335 
   336     checkConcept<ErasableBpGraphComponent<>,
   337       ErasableBpGraphComponent<> >();
   338 
   339     checkConcept<ClearableBpGraphComponent<>,
   340       ClearableBpGraphComponent<> >();
   341 
   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 }
   353 
   354 void checkFullBpGraph(int redNum, int blueNum) {
   355   typedef FullBpGraph BpGraph;
   356   BPGRAPH_TYPEDEFS(BpGraph);
   357 
   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);
   364 
   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);
   371 
   372   for (RedNodeIt n(G); n != INVALID; ++n) {
   373     checkGraphOutArcList(G, n, blueNum);
   374     checkGraphInArcList(G, n, blueNum);
   375     checkGraphIncEdgeList(G, n, blueNum);
   376   }
   377 
   378   for (BlueNodeIt n(G); n != INVALID; ++n) {
   379     checkGraphOutArcList(G, n, redNum);
   380     checkGraphInArcList(G, n, redNum);
   381     checkGraphIncEdgeList(G, n, redNum);
   382   }
   383 
   384   checkGraphConArcList(G, 2 * redNum * blueNum);
   385   checkGraphConEdgeList(G, redNum * blueNum);
   386 
   387   checkArcDirections(G);
   388 
   389   checkNodeIds(G);
   390   checkRedNodeIds(G);
   391   checkBlueNodeIds(G);
   392   checkArcIds(G);
   393   checkEdgeIds(G);
   394 
   395   checkGraphNodeMap(G);
   396   checkGraphRedNodeMap(G);
   397   checkGraphBlueNodeMap(G);
   398   checkGraphArcMap(G);
   399   checkGraphEdgeMap(G);
   400 
   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   }
   405 
   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   }
   410 
   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   }
   425 
   426 }
   427 
   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 }
   446 
   447 int main() {
   448   checkConcepts();
   449   checkGraphs();
   450   return 0;
   451 }