lemon-0.x: test/graph_copy_test.cc@3d14a3449362

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2008

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

    20 #include <lemon/list_graph.h>

    21 #include <lemon/graph_reader.h>

    22 #include <lemon/graph_utils.h>

    23 #include <lemon/error.h>

    25 #include "test_tools.h"

    27 using namespace std;

    28 using namespace lemon;

    30 void graph_copy_test() {

    31   const int nn = 10;

    33   SmartGraph source;

    34   SmartGraph::NodeMap<int> snm(source);

    35   SmartGraph::EdgeMap<int> sem(source);

    36   SmartGraph::Node sn = INVALID;

    37   SmartGraph::Edge se = INVALID;

    39   std::vector<SmartGraph::Node> snv;

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

    41     SmartGraph::Node node = source.addNode();

    42     snv.push_back(node);

    43     snm[node] = i * i;

    44     if (i == 0) sn = node;

    45   }

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

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

    49       SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]);

    50       sem[edge] = i + j * j;

    51       if (i == 0 && j == 0) se = edge;

    52     }

    53   }

    55   ListGraph target;

    56   ListGraph::NodeMap<int> tnm(target);

    57   ListGraph::EdgeMap<int> tem(target);

    58   ListGraph::Node tn;

    59   ListGraph::Edge te;

    61   SmartGraph::NodeMap<ListGraph::Node> nr(source);

    62   SmartGraph::EdgeMap<ListGraph::Edge> er(source);

    64   ListGraph::NodeMap<SmartGraph::Node> ncr(target);

    65   ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);

    67   GraphCopy<ListGraph, SmartGraph>(target, source).

    68     nodeMap(tnm, snm).edgeMap(tem, sem).

    69     nodeRef(nr).edgeRef(er).

    70     nodeCrossRef(ncr).edgeCrossRef(ecr).

    71     node(tn, sn).edge(te, se).run();

    73   for (SmartGraph::NodeIt it(source); it != INVALID; ++it) {

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

    75     check(snm[it] == tnm[nr[it]], "Wrong copy.");

    76   }

    78   for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) {

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

    80     check(sem[it] == tem[er[it]], "Wrong copy.");

    81     check(nr[source.source(it)] ==

    82                  target.source(er[it]), "Wrong copy.");

    83     check(nr[source.target(it)] ==

    84                  target.target(er[it]), "Wrong copy.");

    85   }

    87   for (ListGraph::NodeIt it(target); it != INVALID; ++it) {

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

    89   }

    91   for (ListGraph::EdgeIt it(target); it != INVALID; ++it) {

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

    93   }

    94   check(tn == nr[sn], "Wrong copy.");

    95   check(te == er[se], "Wrong copy.");

    96 }

    98 void ugraph_copy_test() {

    99   const int nn = 10;

   101   SmartUGraph source;

   102   SmartUGraph::NodeMap<int> snm(source);

   103   SmartUGraph::EdgeMap<int> sem(source);

   104   SmartUGraph::UEdgeMap<int> suem(source);

   105   SmartUGraph::Node sn = INVALID;

   106   SmartUGraph::Edge se = INVALID;

   107   SmartUGraph::UEdge sue = INVALID;

   109   std::vector<SmartUGraph::Node> snv;

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

   111     SmartUGraph::Node node = source.addNode();

   112     snv.push_back(node);

   113     snm[node] = i * i;

   114     if (i == 0) sn = node;

   115   }

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

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

   119       SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]);

   120       suem[edge] = i * i + j * j;

   121       sem[source.direct(edge, true)] = i + j * j;

   122       sem[source.direct(edge, false)] = i * i + j;

   123       if (i == 0 && j == 0) se = source.direct(edge, true);

   124       if (i == 0 && j == 0) sue = edge;

   125     }

   126   }

   128   ListUGraph target;

   129   ListUGraph::NodeMap<int> tnm(target);

   130   ListUGraph::EdgeMap<int> tem(target);

   131   ListUGraph::UEdgeMap<int> tuem(target);

   132   ListUGraph::Node tn;

   133   ListUGraph::Edge te;

   134   ListUGraph::UEdge tue;

   136   SmartUGraph::NodeMap<ListUGraph::Node> nr(source);

   137   SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);

   138   SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);

   140   ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);

   141   ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);

   142   ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);

   144   UGraphCopy<ListUGraph, SmartUGraph>(target, source).

   145     nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem).

   146     nodeRef(nr).edgeRef(er).uEdgeRef(uer).

   147     nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr).

   148     node(tn, sn).edge(te, se).uEdge(tue, sue).run();

   150   for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) {

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

   152     check(snm[it] == tnm[nr[it]], "Wrong copy.");

   153   }

   155   for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) {

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

   157     check(sem[it] == tem[er[it]], "Wrong copy.");

   158     check(nr[source.source(it)] ==

   159                  target.source(er[it]), "Wrong copy.");

   160     check(nr[source.target(it)] ==

   161                  target.target(er[it]), "Wrong copy.");

   162   }

   164   for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) {

   165     check(uecr[uer[it]] == it, "Wrong copy.");

   166     check(suem[it] == tuem[uer[it]], "Wrong copy.");

   167     check(nr[source.source(it)] == target.source(uer[it]) ||

   168                  nr[source.source(it)] == target.target(uer[it]),

   169                  "Wrong copy.");

   170     check(nr[source.target(it)] == target.source(uer[it]) ||

   171                  nr[source.target(it)] == target.target(uer[it]),

   172                  "Wrong copy.");

   173     check((source.source(it) != source.target(it)) ==

   174                  (target.source(uer[it]) != target.target(uer[it])),

   175                  "Wrong copy.");

   176   }

   178   for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {

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

   180   }

   182   for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) {

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

   184   }

   185   for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) {

   186     check(uer[uecr[it]] == it, "Wrong copy.");

   187   }

   188   check(tn == nr[sn], "Wrong copy.");

   189   check(te == er[se], "Wrong copy.");

   190   check(tue == uer[sue], "Wrong copy.");

   191 }

   193 void bpugraph_copy_test() {

   194   const int nn = 10;

   196   SmartBpUGraph source;

   197   SmartBpUGraph::ANodeMap<int> sanm(source);

   198   SmartBpUGraph::BNodeMap<int> sbnm(source);

   199   SmartBpUGraph::NodeMap<int> snm(source);

   200   SmartBpUGraph::EdgeMap<int> sem(source);

   201   SmartBpUGraph::UEdgeMap<int> suem(source);

   202   SmartBpUGraph::Node sn = INVALID;

   203   SmartBpUGraph::Edge se = INVALID;

   204   SmartBpUGraph::UEdge sue = INVALID;

   206   std::vector<SmartBpUGraph::Node> sanv;

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

   208     SmartBpUGraph::Node node = source.addANode();

   209     sanv.push_back(node);

   210     sanm[node] = i * i;

   211     snm[node] = i * i + i;

   212     if (i == 0) sn = node;

   213   }

   215   std::vector<SmartBpUGraph::Node> sbnv;

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

   217     SmartBpUGraph::Node node = source.addBNode();

   218     sbnv.push_back(node);

   219     sbnm[node] = i * i - i;

   220     snm[node] = i * i + i + 1;

   221   }

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

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

   225       SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]);

   226       suem[edge] = i * i + j * j;

   227       sem[source.direct(edge, true)] = i + j * j;

   228       sem[source.direct(edge, false)] = i * i + j;

   229       if (i == 0 && j == 0) se = source.direct(edge, true);

   230       if (i == 0 && j == 0) sue = edge;

   231     }

   232   }

   234   ListBpUGraph target;

   235   ListBpUGraph::ANodeMap<int> tanm(target);

   236   ListBpUGraph::BNodeMap<int> tbnm(target);

   237   ListBpUGraph::NodeMap<int> tnm(target);

   238   ListBpUGraph::EdgeMap<int> tem(target);

   239   ListBpUGraph::UEdgeMap<int> tuem(target);

   240   ListBpUGraph::Node tn;

   241   ListBpUGraph::Edge te;

   242   ListBpUGraph::UEdge tue;

   244   SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);

   245   SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);

   246   SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);

   247   SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);

   248   SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);

   250   ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);

   251   ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);

   252   ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);

   253   ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);

   254   ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);

   256   BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(target, source).

   257     aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm).

   258     edgeMap(tem, sem).uEdgeMap(tuem, suem).

   259     aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer).

   260     aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr).

   261     edgeCrossRef(ecr).uEdgeCrossRef(uecr).

   262     node(tn, sn).edge(te, se).uEdge(tue, sue).run();

   264   for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) {

   265     check(nr[it] == anr[it], "Wrong copy.");

   266     check(ancr[anr[it]] == it, "Wrong copy.");

   267     check(sanm[it] == tanm[anr[it]], "Wrong copy.");

   268   }

   270   for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) {

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

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

   273     check(sbnm[it] == tbnm[bnr[it]], "Wrong copy.");

   274   }

   276   for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) {

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

   278     check(snm[it] == tnm[nr[it]], "Wrong copy.");

   279   }

   281   for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) {

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

   283     check(sem[it] == tem[er[it]], "Wrong copy.");

   284     check(nr[source.source(it)] ==

   285                  target.source(er[it]), "Wrong copy.");

   286     check(nr[source.target(it)] ==

   287                  target.target(er[it]), "Wrong copy.");

   288   }

   290   for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) {

   291     check(uecr[uer[it]] == it, "Wrong copy.");

   292     check(suem[it] == tuem[uer[it]], "Wrong copy.");

   293     check(nr[source.aNode(it)] ==

   294                  target.aNode(uer[it]), "Wrong copy.");

   295     check(nr[source.bNode(it)] ==

   296                  target.bNode(uer[it]), "Wrong copy.");

   297   }

   299   for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) {

   300     check(ancr[it] == ncr[it], "Wrong copy.");

   301     check(anr[ancr[it]] == it, "Wrong copy.");

   302   }

   304   for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) {

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

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

   307   }

   309   for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {

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

   311   }

   313   for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) {

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

   315   }

   316   for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) {

   317     check(uer[uecr[it]] == it, "Wrong copy.");

   318   }

   319   check(tn == nr[sn], "Wrong copy.");

   320   check(te == er[se], "Wrong copy.");

   321   check(tue == uer[sue], "Wrong copy.");

   322 }

   324 int main() {

   325   graph_copy_test();

   326   ugraph_copy_test();

   327   bpugraph_copy_test();

   329   return 0;

   330 }

author	deba
	Fri, 13 Jun 2008 09:51:45 +0000
changeset 2613	3d14a3449362
parent 2391	14a343be7a5a
permissions	-rw-r--r--