lemon-main: test/bpgraph_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/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);

    81   ::lemon::ignore_unused_variable_warning(e2,e3);

    83   checkGraphNodeList(G, 3);

    84   checkGraphRedNodeList(G, 1);

    85   checkGraphBlueNodeList(G, 2);

    86   checkGraphEdgeList(G, 3);

    87   checkGraphArcList(G, 6);

    89   checkGraphIncEdgeArcLists(G, rn1, 3);

    90   checkGraphIncEdgeArcLists(G, bn1, 1);

    91   checkGraphIncEdgeArcLists(G, bn2, 2);

    93   checkGraphConEdgeList(G, 3);

    94   checkGraphConArcList(G, 6);

    96   checkArcDirections(G);

    98   checkNodeIds(G);

    99   checkRedNodeIds(G);

   100   checkBlueNodeIds(G);

   101   checkArcIds(G);

   102   checkEdgeIds(G);

   104   checkGraphNodeMap(G);

   105   checkGraphRedNodeMap(G);

   106   checkGraphBlueNodeMap(G);

   107   checkGraphArcMap(G);

   108   checkGraphEdgeMap(G);

   109 }

   111 template <class BpGraph>

   112 void checkBpGraphErase() {

   113   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

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

   125   // Check edge deletion

   126   G.erase(e2);

   128   checkGraphNodeList(G, 4);

   129   checkGraphRedNodeList(G, 2);

   130   checkGraphBlueNodeList(G, 2);

   131   checkGraphEdgeList(G, 3);

   132   checkGraphArcList(G, 6);

   134   checkGraphIncEdgeArcLists(G, n1, 1);

   135   checkGraphIncEdgeArcLists(G, n2, 2);

   136   checkGraphIncEdgeArcLists(G, n3, 1);

   137   checkGraphIncEdgeArcLists(G, n4, 2);

   139   checkGraphConEdgeList(G, 3);

   140   checkGraphConArcList(G, 6);

   142   // Check node deletion

   143   G.erase(n3);

   145   checkGraphNodeList(G, 3);

   146   checkGraphRedNodeList(G, 2);

   147   checkGraphBlueNodeList(G, 1);

   148   checkGraphEdgeList(G, 2);

   149   checkGraphArcList(G, 4);

   151   checkGraphIncEdgeArcLists(G, n1, 1);

   152   checkGraphIncEdgeArcLists(G, n2, 2);

   153   checkGraphIncEdgeArcLists(G, n4, 1);

   155   checkGraphConEdgeList(G, 2);

   156   checkGraphConArcList(G, 4);

   158 }

   160 template <class BpGraph>

   161 void checkBpGraphAlter() {

   162   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

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

   174   G.changeRed(e2, n4);

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

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

   178   checkGraphNodeList(G, 4);

   179   checkGraphRedNodeList(G, 2);

   180   checkGraphBlueNodeList(G, 2);

   181   checkGraphEdgeList(G, 4);

   182   checkGraphArcList(G, 8);

   184   checkGraphIncEdgeArcLists(G, n1, 1);

   185   checkGraphIncEdgeArcLists(G, n2, 2);

   186   checkGraphIncEdgeArcLists(G, n3, 2);

   187   checkGraphIncEdgeArcLists(G, n4, 3);

   189   checkGraphConEdgeList(G, 4);

   190   checkGraphConArcList(G, 8);

   192   G.changeBlue(e2, n2);

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

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

   196   checkGraphNodeList(G, 4);

   197   checkGraphRedNodeList(G, 2);

   198   checkGraphBlueNodeList(G, 2);

   199   checkGraphEdgeList(G, 4);

   200   checkGraphArcList(G, 8);

   202   checkGraphIncEdgeArcLists(G, n1, 1);

   203   checkGraphIncEdgeArcLists(G, n2, 3);

   204   checkGraphIncEdgeArcLists(G, n3, 1);

   205   checkGraphIncEdgeArcLists(G, n4, 3);

   207   checkGraphConEdgeList(G, 4);

   208   checkGraphConArcList(G, 8);

   209 }

   212 template <class BpGraph>

   213 void checkBpGraphSnapshot() {

   214   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

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

   227   checkGraphNodeList(G, 3);

   228   checkGraphRedNodeList(G, 1);

   229   checkGraphBlueNodeList(G, 2);

   230   checkGraphEdgeList(G, 2);

   231   checkGraphArcList(G, 4);

   233   typename BpGraph::Snapshot snapshot(G);

   235   RedNode n4 = G.addRedNode();

   236   G.addEdge(n4, n2);

   237   G.addEdge(n4, n3);

   239   checkGraphNodeList(G, 4);

   240   checkGraphRedNodeList(G, 2);

   241   checkGraphBlueNodeList(G, 2);

   242   checkGraphEdgeList(G, 4);

   243   checkGraphArcList(G, 8);

   245   snapshot.restore();

   247   checkGraphNodeList(G, 3);

   248   checkGraphRedNodeList(G, 1);

   249   checkGraphBlueNodeList(G, 2);

   250   checkGraphEdgeList(G, 2);

   251   checkGraphArcList(G, 4);

   253   checkGraphIncEdgeArcLists(G, n1, 2);

   254   checkGraphIncEdgeArcLists(G, n2, 1);

   255   checkGraphIncEdgeArcLists(G, n3, 1);

   257   checkGraphConEdgeList(G, 2);

   258   checkGraphConArcList(G, 4);

   260   checkNodeIds(G);

   261   checkRedNodeIds(G);

   262   checkBlueNodeIds(G);

   263   checkArcIds(G);

   264   checkEdgeIds(G);

   266   checkGraphNodeMap(G);

   267   checkGraphRedNodeMap(G);

   268   checkGraphBlueNodeMap(G);

   269   checkGraphArcMap(G);

   270   checkGraphEdgeMap(G);

   272   G.addRedNode();

   273   snapshot.save(G);

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

   277   snapshot.restore();

   278   snapshot.save(G);

   280   checkGraphNodeList(G, 4);

   281   checkGraphRedNodeList(G, 2);

   282   checkGraphBlueNodeList(G, 2);

   283   checkGraphEdgeList(G, 2);

   284   checkGraphArcList(G, 4);

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

   288   snapshot.restore();

   290   checkGraphNodeList(G, 4);

   291   checkGraphRedNodeList(G, 2);

   292   checkGraphBlueNodeList(G, 2);

   293   checkGraphEdgeList(G, 2);

   294   checkGraphArcList(G, 4);

   295 }

   297 template <typename BpGraph>

   298 void checkBpGraphValidity() {

   299   TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);

   300   BpGraph g;

   302   RedNode

   303     n1 = g.addRedNode();

   304   BlueNode

   305     n2 = g.addBlueNode(),

   306     n3 = g.addBlueNode();

   308   Edge

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

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

   311   ::lemon::ignore_unused_variable_warning(e2);

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

   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 }

   322 void checkConcepts() {

   323   { // Checking graph components

   324     checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();

   326     checkConcept<IDableBpGraphComponent<>,

   327       IDableBpGraphComponent<> >();

   329     checkConcept<IterableBpGraphComponent<>,

   330       IterableBpGraphComponent<> >();

   332     checkConcept<AlterableBpGraphComponent<>,

   333       AlterableBpGraphComponent<> >();

   335     checkConcept<MappableBpGraphComponent<>,

   336       MappableBpGraphComponent<> >();

   338     checkConcept<ExtendableBpGraphComponent<>,

   339       ExtendableBpGraphComponent<> >();

   341     checkConcept<ErasableBpGraphComponent<>,

   342       ErasableBpGraphComponent<> >();

   344     checkConcept<ClearableBpGraphComponent<>,

   345       ClearableBpGraphComponent<> >();

   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 }

   359 void checkFullBpGraph(int redNum, int blueNum) {

   360   typedef FullBpGraph BpGraph;

   361   BPGRAPH_TYPEDEFS(BpGraph);

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

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

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

   378     checkGraphOutArcList(G, n, blueNum);

   379     checkGraphInArcList(G, n, blueNum);

   380     checkGraphIncEdgeList(G, n, blueNum);

   381   }

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

   384     checkGraphOutArcList(G, n, redNum);

   385     checkGraphInArcList(G, n, redNum);

   386     checkGraphIncEdgeList(G, n, redNum);

   387   }

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

   390   checkGraphConEdgeList(G, redNum * blueNum);

   392   checkArcDirections(G);

   394   checkNodeIds(G);

   395   checkRedNodeIds(G);

   396   checkBlueNodeIds(G);

   397   checkArcIds(G);

   398   checkEdgeIds(G);

   400   checkGraphNodeMap(G);

   401   checkGraphRedNodeMap(G);

   402   checkGraphBlueNodeMap(G);

   403   checkGraphArcMap(G);

   404   checkGraphEdgeMap(G);

   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   }

   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   }

   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   }

   431 }

   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 }

   452 int main() {

   453   checkConcepts();

   454   checkGraphs();

   455   return 0;

   456 }

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