lemon: test/bpgraph_test.cc@5ef0ab7b61cd

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

   111 void checkBpGraphSnapshot() {

   112   TEMPLATE_BPGRAPH_TYPEDEFS(Graph);

   114   Graph G;

   115   Node

   116     n1 = G.addRedNode(),

   117     n2 = G.addBlueNode(),

   118     n3 = G.addBlueNode();

   119   Edge

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

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

   123   checkGraphNodeList(G, 3);

   124   checkGraphRedNodeList(G, 1);

   125   checkGraphBlueNodeList(G, 2);

   126   checkGraphEdgeList(G, 2);

   127   checkGraphArcList(G, 4);

   129   typename Graph::Snapshot snapshot(G);

   131   Node n4 = G.addRedNode();

   132   G.addEdge(n4, n2);

   133   G.addEdge(n4, n3);

   135   checkGraphNodeList(G, 4);

   136   checkGraphRedNodeList(G, 2);

   137   checkGraphBlueNodeList(G, 2);

   138   checkGraphEdgeList(G, 4);

   139   checkGraphArcList(G, 8);

   141   snapshot.restore();

   143   checkGraphNodeList(G, 3);

   144   checkGraphRedNodeList(G, 1);

   145   checkGraphBlueNodeList(G, 2);

   146   checkGraphEdgeList(G, 2);

   147   checkGraphArcList(G, 4);

   149   checkGraphIncEdgeArcLists(G, n1, 2);

   150   checkGraphIncEdgeArcLists(G, n2, 1);

   151   checkGraphIncEdgeArcLists(G, n3, 1);

   153   checkGraphConEdgeList(G, 2);

   154   checkGraphConArcList(G, 4);

   156   checkNodeIds(G);

   157   checkRedNodeIds(G);

   158   checkBlueNodeIds(G);

   159   checkArcIds(G);

   160   checkEdgeIds(G);

   162   checkGraphNodeMap(G);

   163   checkGraphRedMap(G);

   164   checkGraphBlueMap(G);

   165   checkGraphArcMap(G);

   166   checkGraphEdgeMap(G);

   168   G.addRedNode();

   169   snapshot.save(G);

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

   173   snapshot.restore();

   174   snapshot.save(G);

   176   checkGraphNodeList(G, 4);

   177   checkGraphRedNodeList(G, 2);

   178   checkGraphBlueNodeList(G, 2);

   179   checkGraphEdgeList(G, 2);

   180   checkGraphArcList(G, 4);

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

   184   snapshot.restore();

   186   checkGraphNodeList(G, 4);

   187   checkGraphRedNodeList(G, 2);

   188   checkGraphBlueNodeList(G, 2);

   189   checkGraphEdgeList(G, 2);

   190   checkGraphArcList(G, 4);

   191 }

   193 template <typename Graph>

   194 void checkBpGraphValidity() {

   195   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   196   Graph g;

   198   Node

   199     n1 = g.addRedNode(),

   200     n2 = g.addBlueNode(),

   201     n3 = g.addBlueNode();

   203   Edge

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

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

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

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

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

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

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

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

   214 }

   216 void checkConcepts() {

   217   { // Checking graph components

   218     checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();

   220     checkConcept<IDableBpGraphComponent<>,

   221       IDableBpGraphComponent<> >();

   223     checkConcept<IterableBpGraphComponent<>,

   224       IterableBpGraphComponent<> >();

   226     checkConcept<AlterableBpGraphComponent<>,

   227       AlterableBpGraphComponent<> >();

   229     checkConcept<MappableBpGraphComponent<>,

   230       MappableBpGraphComponent<> >();

   232     checkConcept<ExtendableBpGraphComponent<>,

   233       ExtendableBpGraphComponent<> >();

   235     checkConcept<ErasableBpGraphComponent<>,

   236       ErasableBpGraphComponent<> >();

   238     checkConcept<ClearableBpGraphComponent<>,

   239       ClearableBpGraphComponent<> >();

   241   }

   242   { // Checking skeleton graph

   243     checkConcept<BpGraph, BpGraph>();

   244   }

   245   { // Checking SmartBpGraph

   246     checkConcept<BpGraph, SmartBpGraph>();

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

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

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

   250   }

   251 }

   253 void checkFullBpGraph(int redNum, int blueNum) {

   254   typedef FullBpGraph BpGraph;

   255   BPGRAPH_TYPEDEFS(BpGraph);

   257   BpGraph G(redNum, blueNum);

   258   checkGraphNodeList(G, redNum + blueNum);

   259   checkGraphRedNodeList(G, redNum);

   260   checkGraphBlueNodeList(G, blueNum);

   261   checkGraphEdgeList(G, redNum * blueNum);

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

   264   G.resize(redNum, blueNum);

   265   checkGraphNodeList(G, redNum + blueNum);

   266   checkGraphRedNodeList(G, redNum);

   267   checkGraphBlueNodeList(G, blueNum);

   268   checkGraphEdgeList(G, redNum * blueNum);

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

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

   272     checkGraphOutArcList(G, n, blueNum);

   273     checkGraphInArcList(G, n, blueNum);

   274     checkGraphIncEdgeList(G, n, blueNum);

   275   }

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

   278     checkGraphOutArcList(G, n, redNum);

   279     checkGraphInArcList(G, n, redNum);

   280     checkGraphIncEdgeList(G, n, redNum);

   281   }

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

   284   checkGraphConEdgeList(G, redNum * blueNum);

   286   checkArcDirections(G);

   288   checkNodeIds(G);

   289   checkRedNodeIds(G);

   290   checkBlueNodeIds(G);

   291   checkArcIds(G);

   292   checkEdgeIds(G);

   294   checkGraphNodeMap(G);

   295   checkGraphRedMap(G);

   296   checkGraphBlueMap(G);

   297   checkGraphArcMap(G);

   298   checkGraphEdgeMap(G);

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

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

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

   303   }

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

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

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

   308   }

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

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

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

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

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

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

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

   317       } else {

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

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

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

   321       }

   322     }

   323   }

   325 }

   327 void checkGraphs() {

   328   { // Checking SmartGraph

   329     checkBpGraphBuild<SmartBpGraph>();

   330     checkBpGraphSnapshot<SmartBpGraph>();

   331     checkBpGraphValidity<SmartBpGraph>();

   332   }

   333   { // Checking FullBpGraph

   334     checkFullBpGraph(6, 8);

   335     checkFullBpGraph(7, 4);

   336   }

   337 }

   339 int main() {

   340   checkConcepts();

   341   checkGraphs();

   342   return 0;

   343 }

author	Balazs Dezso <deba@inf.elte.hu>
	Sun, 14 Nov 2010 22:48:32 +0100
changeset 1188	5ef0ab7b61cd
parent 1187	4c89e925cfe2
child 1189	a12cca3ad15a
permissions	-rw-r--r--