Mercuriallemon / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/graph_copy_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Tue, 16 Nov 2010 00:59:36 +0100
changeset 1190 523e45e37e52
parent 989 24b3f18ed9e2
child 1193 c8fa41fcc4a7
permissions -rw-r--r--
Implementation of BpGraphCopy (#69) 
     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-2009

     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/smart_graph.h>

    20 #include <lemon/list_graph.h>

    21 #include <lemon/static_graph.h>

    22 #include <lemon/lgf_reader.h>

    23 #include <lemon/error.h>

    24 

    25 #include "test_tools.h"

    26 

    27 using namespace std;

    28 using namespace lemon;

    29 

    30 template <typename GR>

    31 void digraph_copy_test() {

    32   const int nn = 10;

    33 

    34   // Build a digraph

    35   SmartDigraph from;

    36   SmartDigraph::NodeMap<int> fnm(from);

    37   SmartDigraph::ArcMap<int> fam(from);

    38   SmartDigraph::Node fn = INVALID;

    39   SmartDigraph::Arc fa = INVALID;

    40 

    41   std::vector<SmartDigraph::Node> fnv;

    42   for (int i = 0; i < nn; ++i) {

    43     SmartDigraph::Node node = from.addNode();

    44     fnv.push_back(node);

    45     fnm[node] = i * i;

    46     if (i == 0) fn = node;

    47   }

    48 

    49   for (int i = 0; i < nn; ++i) {

    50     for (int j = 0; j < nn; ++j) {

    51       SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);

    52       fam[arc] = i + j * j;

    53       if (i == 0 && j == 0) fa = arc;

    54     }

    55   }

    56   

    57   // Test digraph copy

    58   GR to;

    59   typename GR::template NodeMap<int> tnm(to);

    60   typename GR::template ArcMap<int> tam(to);

    61   typename GR::Node tn;

    62   typename GR::Arc ta;

    63 

    64   SmartDigraph::NodeMap<typename GR::Node> nr(from);

    65   SmartDigraph::ArcMap<typename GR::Arc> er(from);

    66 

    67   typename GR::template NodeMap<SmartDigraph::Node> ncr(to);

    68   typename GR::template ArcMap<SmartDigraph::Arc> ecr(to);

    69 

    70   digraphCopy(from, to).

    71     nodeMap(fnm, tnm).arcMap(fam, tam).

    72     nodeRef(nr).arcRef(er).

    73     nodeCrossRef(ncr).arcCrossRef(ecr).

    74     node(fn, tn).arc(fa, ta).run();

    75   

    76   check(countNodes(from) == countNodes(to), "Wrong copy.");

    77   check(countArcs(from) == countArcs(to), "Wrong copy.");

    78 

    79   for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {

    80     check(ncr[nr[it]] == it, "Wrong copy.");

    81     check(fnm[it] == tnm[nr[it]], "Wrong copy.");

    82   }

    83 

    84   for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {

    85     check(ecr[er[it]] == it, "Wrong copy.");

    86     check(fam[it] == tam[er[it]], "Wrong copy.");

    87     check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");

    88     check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");

    89   }

    90 

    91   for (typename GR::NodeIt it(to); it != INVALID; ++it) {

    92     check(nr[ncr[it]] == it, "Wrong copy.");

    93   }

    94 

    95   for (typename GR::ArcIt it(to); it != INVALID; ++it) {

    96     check(er[ecr[it]] == it, "Wrong copy.");

    97   }

    98   check(tn == nr[fn], "Wrong copy.");

    99   check(ta == er[fa], "Wrong copy.");

   100 

   101   // Test repeated copy

   102   digraphCopy(from, to).run();

   103   

   104   check(countNodes(from) == countNodes(to), "Wrong copy.");

   105   check(countArcs(from) == countArcs(to), "Wrong copy.");

   106 }

   107 

   108 template <typename GR>

   109 void graph_copy_test() {

   110   const int nn = 10;

   111 

   112   // Build a graph

   113   SmartGraph from;

   114   SmartGraph::NodeMap<int> fnm(from);

   115   SmartGraph::ArcMap<int> fam(from);

   116   SmartGraph::EdgeMap<int> fem(from);

   117   SmartGraph::Node fn = INVALID;

   118   SmartGraph::Arc fa = INVALID;

   119   SmartGraph::Edge fe = INVALID;

   120 

   121   std::vector<SmartGraph::Node> fnv;

   122   for (int i = 0; i < nn; ++i) {

   123     SmartGraph::Node node = from.addNode();

   124     fnv.push_back(node);

   125     fnm[node] = i * i;

   126     if (i == 0) fn = node;

   127   }

   128 

   129   for (int i = 0; i < nn; ++i) {

   130     for (int j = 0; j < nn; ++j) {

   131       SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);

   132       fem[edge] = i * i + j * j;

   133       fam[from.direct(edge, true)] = i + j * j;

   134       fam[from.direct(edge, false)] = i * i + j;

   135       if (i == 0 && j == 0) fa = from.direct(edge, true);

   136       if (i == 0 && j == 0) fe = edge;

   137     }

   138   }

   139 

   140   // Test graph copy

   141   GR to;

   142   typename GR::template NodeMap<int> tnm(to);

   143   typename GR::template ArcMap<int> tam(to);

   144   typename GR::template EdgeMap<int> tem(to);

   145   typename GR::Node tn;

   146   typename GR::Arc ta;

   147   typename GR::Edge te;

   148 

   149   SmartGraph::NodeMap<typename GR::Node> nr(from);

   150   SmartGraph::ArcMap<typename GR::Arc> ar(from);

   151   SmartGraph::EdgeMap<typename GR::Edge> er(from);

   152 

   153   typename GR::template NodeMap<SmartGraph::Node> ncr(to);

   154   typename GR::template ArcMap<SmartGraph::Arc> acr(to);

   155   typename GR::template EdgeMap<SmartGraph::Edge> ecr(to);

   156 

   157   graphCopy(from, to).

   158     nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).

   159     nodeRef(nr).arcRef(ar).edgeRef(er).

   160     nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).

   161     node(fn, tn).arc(fa, ta).edge(fe, te).run();

   162 

   163   check(countNodes(from) == countNodes(to), "Wrong copy.");

   164   check(countEdges(from) == countEdges(to), "Wrong copy.");

   165   check(countArcs(from) == countArcs(to), "Wrong copy.");

   166 

   167   for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {

   168     check(ncr[nr[it]] == it, "Wrong copy.");

   169     check(fnm[it] == tnm[nr[it]], "Wrong copy.");

   170   }

   171 

   172   for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {

   173     check(acr[ar[it]] == it, "Wrong copy.");

   174     check(fam[it] == tam[ar[it]], "Wrong copy.");

   175     check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");

   176     check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");

   177   }

   178 

   179   for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {

   180     check(ecr[er[it]] == it, "Wrong copy.");

   181     check(fem[it] == tem[er[it]], "Wrong copy.");

   182     check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),

   183           "Wrong copy.");

   184     check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),

   185           "Wrong copy.");

   186     check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),

   187           "Wrong copy.");

   188   }

   189 

   190   for (typename GR::NodeIt it(to); it != INVALID; ++it) {

   191     check(nr[ncr[it]] == it, "Wrong copy.");

   192   }

   193 

   194   for (typename GR::ArcIt it(to); it != INVALID; ++it) {

   195     check(ar[acr[it]] == it, "Wrong copy.");

   196   }

   197   for (typename GR::EdgeIt it(to); it != INVALID; ++it) {

   198     check(er[ecr[it]] == it, "Wrong copy.");

   199   }

   200   check(tn == nr[fn], "Wrong copy.");

   201   check(ta == ar[fa], "Wrong copy.");

   202   check(te == er[fe], "Wrong copy.");

   203 

   204   // Test repeated copy

   205   graphCopy(from, to).run();

   206   

   207   check(countNodes(from) == countNodes(to), "Wrong copy.");

   208   check(countEdges(from) == countEdges(to), "Wrong copy.");

   209   check(countArcs(from) == countArcs(to), "Wrong copy.");

   210 }

   211 

   212 template <typename GR>

   213 void bpgraph_copy_test() {

   214   const int nn = 10;

   215 

   216   // Build a graph

   217   SmartBpGraph from;

   218   SmartBpGraph::NodeMap<int> fnm(from);

   219   SmartBpGraph::RedMap<int> frnm(from);

   220   SmartBpGraph::BlueMap<int> fbnm(from);

   221   SmartBpGraph::ArcMap<int> fam(from);

   222   SmartBpGraph::EdgeMap<int> fem(from);

   223   SmartBpGraph::Node fn = INVALID;

   224   SmartBpGraph::Arc fa = INVALID;

   225   SmartBpGraph::Edge fe = INVALID;

   226 

   227   std::vector<SmartBpGraph::Node> frnv;

   228   for (int i = 0; i < nn; ++i) {

   229     SmartBpGraph::Node node = from.addRedNode();

   230     frnv.push_back(node);

   231     fnm[node] = i * i;

   232     frnm[node] = i + i;

   233     if (i == 0) fn = node;

   234   }

   235 

   236   std::vector<SmartBpGraph::Node> fbnv;

   237   for (int i = 0; i < nn; ++i) {

   238     SmartBpGraph::Node node = from.addBlueNode();

   239     fbnv.push_back(node);

   240     fnm[node] = i * i;

   241     fbnm[node] = i + i;

   242   }

   243 

   244   for (int i = 0; i < nn; ++i) {

   245     for (int j = 0; j < nn; ++j) {

   246       SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]);

   247       fem[edge] = i * i + j * j;

   248       fam[from.direct(edge, true)] = i + j * j;

   249       fam[from.direct(edge, false)] = i * i + j;

   250       if (i == 0 && j == 0) fa = from.direct(edge, true);

   251       if (i == 0 && j == 0) fe = edge;

   252     }

   253   }

   254 

   255   // Test graph copy

   256   GR to;

   257   typename GR::template NodeMap<int> tnm(to);

   258   typename GR::template RedMap<int> trnm(to);

   259   typename GR::template BlueMap<int> tbnm(to);

   260   typename GR::template ArcMap<int> tam(to);

   261   typename GR::template EdgeMap<int> tem(to);

   262   typename GR::Node tn;

   263   typename GR::Arc ta;

   264   typename GR::Edge te;

   265 

   266   SmartBpGraph::NodeMap<typename GR::Node> nr(from);

   267   SmartBpGraph::RedMap<typename GR::Node> rnr(from);

   268   SmartBpGraph::BlueMap<typename GR::Node> bnr(from);

   269   SmartBpGraph::ArcMap<typename GR::Arc> ar(from);

   270   SmartBpGraph::EdgeMap<typename GR::Edge> er(from);

   271 

   272   typename GR::template NodeMap<SmartBpGraph::Node> ncr(to);

   273   typename GR::template RedMap<SmartBpGraph::Node> rncr(to);

   274   typename GR::template BlueMap<SmartBpGraph::Node> bncr(to);

   275   typename GR::template ArcMap<SmartBpGraph::Arc> acr(to);

   276   typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to);

   277 

   278   bpGraphCopy(from, to).

   279     nodeMap(fnm, tnm).redMap(frnm, trnm).blueMap(fbnm, tbnm).

   280     arcMap(fam, tam).edgeMap(fem, tem).

   281     nodeRef(nr).redRef(rnr).blueRef(bnr).

   282     arcRef(ar).edgeRef(er).

   283     nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr).

   284     arcCrossRef(acr).edgeCrossRef(ecr).

   285     node(fn, tn).arc(fa, ta).edge(fe, te).run();

   286 

   287   check(countNodes(from) == countNodes(to), "Wrong copy.");

   288   check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");

   289   check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");

   290   check(countEdges(from) == countEdges(to), "Wrong copy.");

   291   check(countArcs(from) == countArcs(to), "Wrong copy.");

   292 

   293   for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) {

   294     check(ncr[nr[it]] == it, "Wrong copy.");

   295     check(fnm[it] == tnm[nr[it]], "Wrong copy.");

   296     if (from.red(it)) {

   297       check(rnr[it] == nr[it], "Wrong copy.");

   298       check(rncr[rnr[it]] == it, "Wrong copy.");

   299       check(frnm[it] == trnm[rnr[it]], "Wrong copy.");

   300       check(to.red(rnr[it]), "Wrong copy.");

   301     } else {

   302       check(bnr[it] == nr[it], "Wrong copy.");

   303       check(bncr[bnr[it]] == it, "Wrong copy.");

   304       check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");

   305       check(to.blue(bnr[it]), "Wrong copy.");

   306     }

   307   }

   308 

   309   for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) {

   310     check(acr[ar[it]] == it, "Wrong copy.");

   311     check(fam[it] == tam[ar[it]], "Wrong copy.");

   312     check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");

   313     check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");

   314   }

   315 

   316   for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) {

   317     check(ecr[er[it]] == it, "Wrong copy.");

   318     check(fem[it] == tem[er[it]], "Wrong copy.");

   319     check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),

   320           "Wrong copy.");

   321     check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),

   322           "Wrong copy.");

   323     check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),

   324           "Wrong copy.");

   325   }

   326 

   327   for (typename GR::NodeIt it(to); it != INVALID; ++it) {

   328     check(nr[ncr[it]] == it, "Wrong copy.");

   329   }

   330   for (typename GR::RedIt it(to); it != INVALID; ++it) {

   331     check(rncr[it] == ncr[it], "Wrong copy.");

   332     check(rnr[rncr[it]] == it, "Wrong copy.");

   333   }

   334   for (typename GR::BlueIt it(to); it != INVALID; ++it) {

   335     check(bncr[it] == ncr[it], "Wrong copy.");

   336     check(bnr[bncr[it]] == it, "Wrong copy.");

   337   }

   338   for (typename GR::ArcIt it(to); it != INVALID; ++it) {

   339     check(ar[acr[it]] == it, "Wrong copy.");

   340   }

   341   for (typename GR::EdgeIt it(to); it != INVALID; ++it) {

   342     check(er[ecr[it]] == it, "Wrong copy.");

   343   }

   344   check(tn == nr[fn], "Wrong copy.");

   345   check(ta == ar[fa], "Wrong copy.");

   346   check(te == er[fe], "Wrong copy.");

   347 

   348   // Test repeated copy

   349   bpGraphCopy(from, to).run();

   350   

   351   check(countNodes(from) == countNodes(to), "Wrong copy.");

   352   check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");

   353   check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");

   354   check(countEdges(from) == countEdges(to), "Wrong copy.");

   355   check(countArcs(from) == countArcs(to), "Wrong copy.");

   356 }

   357 

   358 

   359 int main() {

   360   digraph_copy_test<SmartDigraph>();

   361   digraph_copy_test<ListDigraph>();

   362   digraph_copy_test<StaticDigraph>();

   363   graph_copy_test<SmartGraph>();

   364   graph_copy_test<ListGraph>();

   365   bpgraph_copy_test<SmartBpGraph>();

   366   bpgraph_copy_test<ListBpGraph>();

   367 

   368   return 0;

   369 }
lemon