test/bpgraph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 04 Jul 2014 13:41:22 +0200
changeset 1115 9153e490f09c
parent 1092 dceba191c00d
permissions -rw-r--r--
Giving libemon.so a real soname (#482)
     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/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   ::lemon::ignore_unused_variable_warning(e2,e3);
    82 
    83   checkGraphNodeList(G, 3);
    84   checkGraphRedNodeList(G, 1);
    85   checkGraphBlueNodeList(G, 2);
    86   checkGraphEdgeList(G, 3);
    87   checkGraphArcList(G, 6);
    88 
    89   checkGraphIncEdgeArcLists(G, rn1, 3);
    90   checkGraphIncEdgeArcLists(G, bn1, 1);
    91   checkGraphIncEdgeArcLists(G, bn2, 2);
    92 
    93   checkGraphConEdgeList(G, 3);
    94   checkGraphConArcList(G, 6);
    95 
    96   checkArcDirections(G);
    97 
    98   checkNodeIds(G);
    99   checkRedNodeIds(G);
   100   checkBlueNodeIds(G);
   101   checkArcIds(G);
   102   checkEdgeIds(G);
   103 
   104   checkGraphNodeMap(G);
   105   checkGraphRedNodeMap(G);
   106   checkGraphBlueNodeMap(G);
   107   checkGraphArcMap(G);
   108   checkGraphEdgeMap(G);
   109 }
   110 
   111 template <class BpGraph>
   112 void checkBpGraphErase() {
   113   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   114 
   115   BpGraph G;
   116   RedNode
   117     n1 = G.addRedNode(), n4 = G.addRedNode();
   118   BlueNode
   119     n2 = G.addBlueNode(), n3 = G.addBlueNode();
   120   Edge
   121     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
   122     e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
   123   ::lemon::ignore_unused_variable_warning(e1,e3,e4);
   124 
   125   // Check edge deletion
   126   G.erase(e2);
   127 
   128   checkGraphNodeList(G, 4);
   129   checkGraphRedNodeList(G, 2);
   130   checkGraphBlueNodeList(G, 2);
   131   checkGraphEdgeList(G, 3);
   132   checkGraphArcList(G, 6);
   133 
   134   checkGraphIncEdgeArcLists(G, n1, 1);
   135   checkGraphIncEdgeArcLists(G, n2, 2);
   136   checkGraphIncEdgeArcLists(G, n3, 1);
   137   checkGraphIncEdgeArcLists(G, n4, 2);
   138 
   139   checkGraphConEdgeList(G, 3);
   140   checkGraphConArcList(G, 6);
   141 
   142   // Check node deletion
   143   G.erase(n3);
   144 
   145   checkGraphNodeList(G, 3);
   146   checkGraphRedNodeList(G, 2);
   147   checkGraphBlueNodeList(G, 1);
   148   checkGraphEdgeList(G, 2);
   149   checkGraphArcList(G, 4);
   150 
   151   checkGraphIncEdgeArcLists(G, n1, 1);
   152   checkGraphIncEdgeArcLists(G, n2, 2);
   153   checkGraphIncEdgeArcLists(G, n4, 1);
   154 
   155   checkGraphConEdgeList(G, 2);
   156   checkGraphConArcList(G, 4);
   157 
   158 }
   159 
   160 template <class BpGraph>
   161 void checkBpGraphAlter() {
   162   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   163 
   164   BpGraph G;
   165   RedNode
   166     n1 = G.addRedNode(), n4 = G.addRedNode();
   167   BlueNode
   168     n2 = G.addBlueNode(), n3 = G.addBlueNode();
   169   Edge
   170     e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
   171     e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
   172   ::lemon::ignore_unused_variable_warning(e1,e3,e4);
   173 
   174   G.changeRed(e2, n4);
   175   check(G.redNode(e2) == n4, "Wrong red node");
   176   check(G.blueNode(e2) == n3, "Wrong blue node");
   177 
   178   checkGraphNodeList(G, 4);
   179   checkGraphRedNodeList(G, 2);
   180   checkGraphBlueNodeList(G, 2);
   181   checkGraphEdgeList(G, 4);
   182   checkGraphArcList(G, 8);
   183 
   184   checkGraphIncEdgeArcLists(G, n1, 1);
   185   checkGraphIncEdgeArcLists(G, n2, 2);
   186   checkGraphIncEdgeArcLists(G, n3, 2);
   187   checkGraphIncEdgeArcLists(G, n4, 3);
   188 
   189   checkGraphConEdgeList(G, 4);
   190   checkGraphConArcList(G, 8);
   191 
   192   G.changeBlue(e2, n2);
   193   check(G.redNode(e2) == n4, "Wrong red node");
   194   check(G.blueNode(e2) == n2, "Wrong blue node");
   195 
   196   checkGraphNodeList(G, 4);
   197   checkGraphRedNodeList(G, 2);
   198   checkGraphBlueNodeList(G, 2);
   199   checkGraphEdgeList(G, 4);
   200   checkGraphArcList(G, 8);
   201 
   202   checkGraphIncEdgeArcLists(G, n1, 1);
   203   checkGraphIncEdgeArcLists(G, n2, 3);
   204   checkGraphIncEdgeArcLists(G, n3, 1);
   205   checkGraphIncEdgeArcLists(G, n4, 3);
   206 
   207   checkGraphConEdgeList(G, 4);
   208   checkGraphConArcList(G, 8);
   209 }
   210 
   211 
   212 template <class BpGraph>
   213 void checkBpGraphSnapshot() {
   214   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   215 
   216   BpGraph G;
   217   RedNode
   218     n1 = G.addRedNode();
   219   BlueNode
   220     n2 = G.addBlueNode(),
   221     n3 = G.addBlueNode();
   222   Edge
   223     e1 = G.addEdge(n1, n2),
   224     e2 = G.addEdge(n1, n3);
   225   ::lemon::ignore_unused_variable_warning(e1,e2);
   226 
   227   checkGraphNodeList(G, 3);
   228   checkGraphRedNodeList(G, 1);
   229   checkGraphBlueNodeList(G, 2);
   230   checkGraphEdgeList(G, 2);
   231   checkGraphArcList(G, 4);
   232 
   233   typename BpGraph::Snapshot snapshot(G);
   234 
   235   RedNode n4 = G.addRedNode();
   236   G.addEdge(n4, n2);
   237   G.addEdge(n4, n3);
   238 
   239   checkGraphNodeList(G, 4);
   240   checkGraphRedNodeList(G, 2);
   241   checkGraphBlueNodeList(G, 2);
   242   checkGraphEdgeList(G, 4);
   243   checkGraphArcList(G, 8);
   244 
   245   snapshot.restore();
   246 
   247   checkGraphNodeList(G, 3);
   248   checkGraphRedNodeList(G, 1);
   249   checkGraphBlueNodeList(G, 2);
   250   checkGraphEdgeList(G, 2);
   251   checkGraphArcList(G, 4);
   252 
   253   checkGraphIncEdgeArcLists(G, n1, 2);
   254   checkGraphIncEdgeArcLists(G, n2, 1);
   255   checkGraphIncEdgeArcLists(G, n3, 1);
   256 
   257   checkGraphConEdgeList(G, 2);
   258   checkGraphConArcList(G, 4);
   259 
   260   checkNodeIds(G);
   261   checkRedNodeIds(G);
   262   checkBlueNodeIds(G);
   263   checkArcIds(G);
   264   checkEdgeIds(G);
   265 
   266   checkGraphNodeMap(G);
   267   checkGraphRedNodeMap(G);
   268   checkGraphBlueNodeMap(G);
   269   checkGraphArcMap(G);
   270   checkGraphEdgeMap(G);
   271 
   272   G.addRedNode();
   273   snapshot.save(G);
   274 
   275   G.addEdge(G.addRedNode(), G.addBlueNode());
   276 
   277   snapshot.restore();
   278   snapshot.save(G);
   279 
   280   checkGraphNodeList(G, 4);
   281   checkGraphRedNodeList(G, 2);
   282   checkGraphBlueNodeList(G, 2);
   283   checkGraphEdgeList(G, 2);
   284   checkGraphArcList(G, 4);
   285 
   286   G.addEdge(G.addRedNode(), G.addBlueNode());
   287 
   288   snapshot.restore();
   289 
   290   checkGraphNodeList(G, 4);
   291   checkGraphRedNodeList(G, 2);
   292   checkGraphBlueNodeList(G, 2);
   293   checkGraphEdgeList(G, 2);
   294   checkGraphArcList(G, 4);
   295 }
   296 
   297 template <typename BpGraph>
   298 void checkBpGraphValidity() {
   299   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
   300   BpGraph g;
   301 
   302   RedNode
   303     n1 = g.addRedNode();
   304   BlueNode
   305     n2 = g.addBlueNode(),
   306     n3 = g.addBlueNode();
   307 
   308   Edge
   309     e1 = g.addEdge(n1, n2),
   310     e2 = g.addEdge(n1, n3);
   311   ::lemon::ignore_unused_variable_warning(e2);
   312 
   313   check(g.valid(n1), "Wrong validity check");
   314   check(g.valid(e1), "Wrong validity check");
   315   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   316 
   317   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   318   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   319   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   320 }
   321 
   322 void checkConcepts() {
   323   { // Checking graph components
   324     checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
   325 
   326     checkConcept<IDableBpGraphComponent<>,
   327       IDableBpGraphComponent<> >();
   328 
   329     checkConcept<IterableBpGraphComponent<>,
   330       IterableBpGraphComponent<> >();
   331 
   332     checkConcept<AlterableBpGraphComponent<>,
   333       AlterableBpGraphComponent<> >();
   334 
   335     checkConcept<MappableBpGraphComponent<>,
   336       MappableBpGraphComponent<> >();
   337 
   338     checkConcept<ExtendableBpGraphComponent<>,
   339       ExtendableBpGraphComponent<> >();
   340 
   341     checkConcept<ErasableBpGraphComponent<>,
   342       ErasableBpGraphComponent<> >();
   343 
   344     checkConcept<ClearableBpGraphComponent<>,
   345       ClearableBpGraphComponent<> >();
   346 
   347   }
   348   { // Checking skeleton graph
   349     checkConcept<BpGraph, BpGraph>();
   350   }
   351   { // Checking SmartBpGraph
   352     checkConcept<BpGraph, SmartBpGraph>();
   353     checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
   354     checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
   355     checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
   356   }
   357 }
   358 
   359 void checkFullBpGraph(int redNum, int blueNum) {
   360   typedef FullBpGraph BpGraph;
   361   BPGRAPH_TYPEDEFS(BpGraph);
   362 
   363   BpGraph G(redNum, blueNum);
   364   checkGraphNodeList(G, redNum + blueNum);
   365   checkGraphRedNodeList(G, redNum);
   366   checkGraphBlueNodeList(G, blueNum);
   367   checkGraphEdgeList(G, redNum * blueNum);
   368   checkGraphArcList(G, 2 * redNum * blueNum);
   369 
   370   G.resize(redNum, blueNum);
   371   checkGraphNodeList(G, redNum + blueNum);
   372   checkGraphRedNodeList(G, redNum);
   373   checkGraphBlueNodeList(G, blueNum);
   374   checkGraphEdgeList(G, redNum * blueNum);
   375   checkGraphArcList(G, 2 * redNum * blueNum);
   376 
   377   for (RedNodeIt n(G); n != INVALID; ++n) {
   378     checkGraphOutArcList(G, n, blueNum);
   379     checkGraphInArcList(G, n, blueNum);
   380     checkGraphIncEdgeList(G, n, blueNum);
   381   }
   382 
   383   for (BlueNodeIt n(G); n != INVALID; ++n) {
   384     checkGraphOutArcList(G, n, redNum);
   385     checkGraphInArcList(G, n, redNum);
   386     checkGraphIncEdgeList(G, n, redNum);
   387   }
   388 
   389   checkGraphConArcList(G, 2 * redNum * blueNum);
   390   checkGraphConEdgeList(G, redNum * blueNum);
   391 
   392   checkArcDirections(G);
   393 
   394   checkNodeIds(G);
   395   checkRedNodeIds(G);
   396   checkBlueNodeIds(G);
   397   checkArcIds(G);
   398   checkEdgeIds(G);
   399 
   400   checkGraphNodeMap(G);
   401   checkGraphRedNodeMap(G);
   402   checkGraphBlueNodeMap(G);
   403   checkGraphArcMap(G);
   404   checkGraphEdgeMap(G);
   405 
   406   for (int i = 0; i < G.redNum(); ++i) {
   407     check(G.red(G.redNode(i)), "Wrong node");
   408     check(G.index(G.redNode(i)) == i, "Wrong index");
   409   }
   410 
   411   for (int i = 0; i < G.blueNum(); ++i) {
   412     check(G.blue(G.blueNode(i)), "Wrong node");
   413     check(G.index(G.blueNode(i)) == i, "Wrong index");
   414   }
   415 
   416   for (NodeIt u(G); u != INVALID; ++u) {
   417     for (NodeIt v(G); v != INVALID; ++v) {
   418       Edge e = G.edge(u, v);
   419       Arc a = G.arc(u, v);
   420       if (G.red(u) == G.red(v)) {
   421         check(e == INVALID, "Wrong edge lookup");
   422         check(a == INVALID, "Wrong arc lookup");
   423       } else {
   424         check((G.u(e) == u && G.v(e) == v) ||
   425               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
   426         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
   427       }
   428     }
   429   }
   430 
   431 }
   432 
   433 void checkGraphs() {
   434   { // Checking ListGraph
   435     checkBpGraphBuild<ListBpGraph>();
   436     checkBpGraphErase<ListBpGraph>();
   437     checkBpGraphAlter<ListBpGraph>();
   438     checkBpGraphSnapshot<ListBpGraph>();
   439     checkBpGraphValidity<ListBpGraph>();
   440   }
   441   { // Checking SmartGraph
   442     checkBpGraphBuild<SmartBpGraph>();
   443     checkBpGraphSnapshot<SmartBpGraph>();
   444     checkBpGraphValidity<SmartBpGraph>();
   445   }
   446   { // Checking FullBpGraph
   447     checkFullBpGraph(6, 8);
   448     checkFullBpGraph(7, 4);
   449   }
   450 }
   451 
   452 int main() {
   453   checkConcepts();
   454   checkGraphs();
   455   return 0;
   456 }