test/graph_copy_test.cc
author deba
Mon, 17 Dec 2007 09:54:26 +0000
changeset 2542 faaa54ec4520
parent 2344 48ecc4feb42b
child 2553 bfced05fa852
permissions -rw-r--r--
Bug fix
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2391
     5
 * Copyright (C) 2003-2007
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
deba@2290
    19
#include <lemon/smart_graph.h>
deba@2290
    20
#include <lemon/list_graph.h>
deba@2290
    21
#include <lemon/graph_reader.h>
deba@2290
    22
#include <lemon/graph_utils.h>
deba@2290
    23
#include <lemon/error.h>
deba@2290
    24
deba@2290
    25
#include "test_tools.h"
deba@2290
    26
deba@2290
    27
using namespace std;
deba@2290
    28
using namespace lemon;
deba@2290
    29
deba@2290
    30
void graph_copy_test() {
deba@2290
    31
  const int nn = 10;
deba@2290
    32
deba@2290
    33
  SmartGraph source;
deba@2290
    34
  SmartGraph::NodeMap<int> snm(source);
deba@2290
    35
  SmartGraph::EdgeMap<int> sem(source);
deba@2290
    36
  SmartGraph::Node sn = INVALID;
deba@2290
    37
  SmartGraph::Edge se = INVALID;
deba@2290
    38
deba@2290
    39
  std::vector<SmartGraph::Node> snv;
deba@2290
    40
  for (int i = 0; i < nn; ++i) {
deba@2290
    41
    SmartGraph::Node node = source.addNode();
deba@2290
    42
    snv.push_back(node);
deba@2290
    43
    snm[node] = i * i;
deba@2290
    44
    if (i == 0) sn = node;
deba@2290
    45
  }
deba@2290
    46
deba@2290
    47
  for (int i = 0; i < nn; ++i) {
deba@2290
    48
    for (int j = 0; j < nn; ++j) {
deba@2290
    49
      SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]);
deba@2290
    50
      sem[edge] = i + j * j;
deba@2290
    51
      if (i == 0 && j == 0) se = edge;
deba@2290
    52
    }
deba@2290
    53
  }
deba@2290
    54
deba@2290
    55
  ListGraph target;
deba@2290
    56
  ListGraph::NodeMap<int> tnm(target);
deba@2290
    57
  ListGraph::EdgeMap<int> tem(target);
deba@2290
    58
  ListGraph::Node tn;
deba@2290
    59
  ListGraph::Edge te;
deba@2290
    60
deba@2290
    61
  SmartGraph::NodeMap<ListGraph::Node> nr(source);
deba@2290
    62
  SmartGraph::EdgeMap<ListGraph::Edge> er(source);
deba@2290
    63
deba@2290
    64
  ListGraph::NodeMap<SmartGraph::Node> ncr(target);
deba@2290
    65
  ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);
deba@2290
    66
deba@2290
    67
  GraphCopy<ListGraph, SmartGraph>(target, source).
deba@2290
    68
    nodeMap(tnm, snm).edgeMap(tem, sem).
deba@2290
    69
    nodeRef(nr).edgeRef(er).
deba@2290
    70
    nodeCrossRef(ncr).edgeCrossRef(ecr).
deba@2290
    71
    node(tn, sn).edge(te, se).run();
deba@2290
    72
deba@2290
    73
  for (SmartGraph::NodeIt it(source); it != INVALID; ++it) {
deba@2290
    74
    check(ncr[nr[it]] == it, "Wrong copy.");
deba@2290
    75
    check(snm[it] == tnm[nr[it]], "Wrong copy.");
deba@2290
    76
  }
deba@2290
    77
deba@2290
    78
  for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) {
deba@2290
    79
    check(ecr[er[it]] == it, "Wrong copy.");
deba@2290
    80
    check(sem[it] == tem[er[it]], "Wrong copy.");
deba@2290
    81
    check(nr[source.source(it)] == 
deba@2290
    82
                 target.source(er[it]), "Wrong copy.");
deba@2290
    83
    check(nr[source.target(it)] == 
deba@2290
    84
                 target.target(er[it]), "Wrong copy.");
deba@2290
    85
  }
deba@2290
    86
deba@2290
    87
  for (ListGraph::NodeIt it(target); it != INVALID; ++it) {
deba@2290
    88
    check(nr[ncr[it]] == it, "Wrong copy.");
deba@2290
    89
  }
deba@2290
    90
deba@2290
    91
  for (ListGraph::EdgeIt it(target); it != INVALID; ++it) {
deba@2290
    92
    check(er[ecr[it]] == it, "Wrong copy.");
deba@2290
    93
  }
deba@2290
    94
  check(tn == nr[sn], "Wrong copy.");
deba@2290
    95
  check(te == er[se], "Wrong copy.");
deba@2290
    96
}
deba@2290
    97
deba@2290
    98
void ugraph_copy_test() {
deba@2290
    99
  const int nn = 10;
deba@2290
   100
deba@2290
   101
  SmartUGraph source;
deba@2290
   102
  SmartUGraph::NodeMap<int> snm(source);
deba@2290
   103
  SmartUGraph::EdgeMap<int> sem(source);
deba@2290
   104
  SmartUGraph::UEdgeMap<int> suem(source);
deba@2290
   105
  SmartUGraph::Node sn = INVALID;
deba@2290
   106
  SmartUGraph::Edge se = INVALID;
deba@2290
   107
  SmartUGraph::UEdge sue = INVALID;
deba@2290
   108
deba@2344
   109
  std::vector<SmartUGraph::Node> snv;
deba@2290
   110
  for (int i = 0; i < nn; ++i) {
deba@2290
   111
    SmartUGraph::Node node = source.addNode();
deba@2290
   112
    snv.push_back(node);
deba@2290
   113
    snm[node] = i * i;
deba@2290
   114
    if (i == 0) sn = node;
deba@2290
   115
  }
deba@2290
   116
deba@2290
   117
  for (int i = 0; i < nn; ++i) {
deba@2290
   118
    for (int j = 0; j < nn; ++j) {
deba@2290
   119
      SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]);
deba@2290
   120
      suem[edge] = i * i + j * j;
deba@2290
   121
      sem[source.direct(edge, true)] = i + j * j;
deba@2290
   122
      sem[source.direct(edge, false)] = i * i + j;
deba@2290
   123
      if (i == 0 && j == 0) se = source.direct(edge, true);
deba@2290
   124
      if (i == 0 && j == 0) sue = edge;
deba@2290
   125
    }
deba@2290
   126
  }
deba@2290
   127
  
deba@2290
   128
  ListUGraph target;
deba@2290
   129
  ListUGraph::NodeMap<int> tnm(target);
deba@2290
   130
  ListUGraph::EdgeMap<int> tem(target);
deba@2290
   131
  ListUGraph::UEdgeMap<int> tuem(target);
deba@2290
   132
  ListUGraph::Node tn;
deba@2290
   133
  ListUGraph::Edge te;
deba@2290
   134
  ListUGraph::UEdge tue;
deba@2290
   135
deba@2290
   136
  SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
deba@2290
   137
  SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
deba@2290
   138
  SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);
deba@2290
   139
deba@2290
   140
  ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
deba@2290
   141
  ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
deba@2290
   142
  ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);
deba@2290
   143
deba@2290
   144
  UGraphCopy<ListUGraph, SmartUGraph>(target, source).
deba@2290
   145
    nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem).
deba@2290
   146
    nodeRef(nr).edgeRef(er).uEdgeRef(uer).
deba@2290
   147
    nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr).
deba@2290
   148
    node(tn, sn).edge(te, se).uEdge(tue, sue).run();
deba@2290
   149
deba@2290
   150
  for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) {
deba@2290
   151
    check(ncr[nr[it]] == it, "Wrong copy.");
deba@2290
   152
    check(snm[it] == tnm[nr[it]], "Wrong copy.");
deba@2290
   153
  }
deba@2290
   154
deba@2290
   155
  for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) {
deba@2290
   156
    check(ecr[er[it]] == it, "Wrong copy.");
deba@2290
   157
    check(sem[it] == tem[er[it]], "Wrong copy.");
deba@2290
   158
    check(nr[source.source(it)] == 
deba@2290
   159
                 target.source(er[it]), "Wrong copy.");
deba@2290
   160
    check(nr[source.target(it)] == 
deba@2290
   161
                 target.target(er[it]), "Wrong copy.");
deba@2290
   162
  }
deba@2290
   163
deba@2290
   164
  for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) {
deba@2290
   165
    check(uecr[uer[it]] == it, "Wrong copy.");
deba@2290
   166
    check(suem[it] == tuem[uer[it]], "Wrong copy.");
deba@2290
   167
    check(nr[source.source(it)] == target.source(uer[it]) ||
deba@2290
   168
                 nr[source.source(it)] == target.target(uer[it]), 
deba@2290
   169
                 "Wrong copy.");
deba@2290
   170
    check(nr[source.target(it)] == target.source(uer[it]) ||
deba@2290
   171
                 nr[source.target(it)] == target.target(uer[it]), 
deba@2290
   172
                 "Wrong copy.");
deba@2290
   173
    check((source.source(it) != source.target(it)) ==
deba@2290
   174
                 (target.source(uer[it]) != target.target(uer[it])), 
deba@2290
   175
                 "Wrong copy.");
deba@2290
   176
  }
deba@2290
   177
deba@2290
   178
  for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {
deba@2290
   179
    check(nr[ncr[it]] == it, "Wrong copy.");
deba@2290
   180
  }
deba@2290
   181
deba@2290
   182
  for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) {
deba@2290
   183
    check(er[ecr[it]] == it, "Wrong copy.");
deba@2290
   184
  }
deba@2290
   185
  for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) {
deba@2290
   186
    check(uer[uecr[it]] == it, "Wrong copy.");
deba@2290
   187
  }
deba@2290
   188
  check(tn == nr[sn], "Wrong copy.");
deba@2290
   189
  check(te == er[se], "Wrong copy.");
deba@2290
   190
  check(tue == uer[sue], "Wrong copy.");
deba@2290
   191
}
deba@2290
   192
deba@2290
   193
void bpugraph_copy_test() {
deba@2290
   194
  const int nn = 10;
deba@2290
   195
deba@2290
   196
  SmartBpUGraph source;
deba@2290
   197
  SmartBpUGraph::ANodeMap<int> sanm(source);
deba@2290
   198
  SmartBpUGraph::BNodeMap<int> sbnm(source);
deba@2290
   199
  SmartBpUGraph::NodeMap<int> snm(source);
deba@2290
   200
  SmartBpUGraph::EdgeMap<int> sem(source);
deba@2290
   201
  SmartBpUGraph::UEdgeMap<int> suem(source);
deba@2290
   202
  SmartBpUGraph::Node sn = INVALID;
deba@2290
   203
  SmartBpUGraph::Edge se = INVALID;
deba@2290
   204
  SmartBpUGraph::UEdge sue = INVALID;
deba@2290
   205
deba@2290
   206
  std::vector<SmartBpUGraph::Node> sanv;
deba@2290
   207
  for (int i = 0; i < nn; ++i) {
deba@2290
   208
    SmartBpUGraph::Node node = source.addANode();
deba@2290
   209
    sanv.push_back(node);
deba@2290
   210
    sanm[node] = i * i;
deba@2290
   211
    snm[node] = i * i + i;
deba@2290
   212
    if (i == 0) sn = node;
deba@2290
   213
  }
deba@2290
   214
deba@2290
   215
  std::vector<SmartBpUGraph::Node> sbnv;
deba@2290
   216
  for (int i = 0; i < nn; ++i) {
deba@2290
   217
    SmartBpUGraph::Node node = source.addBNode();
deba@2290
   218
    sbnv.push_back(node);
deba@2290
   219
    sbnm[node] = i * i - i;
deba@2290
   220
    snm[node] = i * i + i + 1;
deba@2290
   221
  }
deba@2290
   222
deba@2290
   223
  for (int i = 0; i < nn; ++i) {
deba@2290
   224
    for (int j = 0; j < nn; ++j) {
deba@2290
   225
      SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]);
deba@2290
   226
      suem[edge] = i * i + j * j;
deba@2290
   227
      sem[source.direct(edge, true)] = i + j * j;
deba@2290
   228
      sem[source.direct(edge, false)] = i * i + j;
deba@2290
   229
      if (i == 0 && j == 0) se = source.direct(edge, true);
deba@2290
   230
      if (i == 0 && j == 0) sue = edge;
deba@2290
   231
    }
deba@2290
   232
  }
deba@2290
   233
  
deba@2290
   234
  ListBpUGraph target;
deba@2290
   235
  ListBpUGraph::ANodeMap<int> tanm(target);
deba@2290
   236
  ListBpUGraph::BNodeMap<int> tbnm(target);
deba@2290
   237
  ListBpUGraph::NodeMap<int> tnm(target);
deba@2290
   238
  ListBpUGraph::EdgeMap<int> tem(target);
deba@2290
   239
  ListBpUGraph::UEdgeMap<int> tuem(target);
deba@2290
   240
  ListBpUGraph::Node tn;
deba@2290
   241
  ListBpUGraph::Edge te;
deba@2290
   242
  ListBpUGraph::UEdge tue;
deba@2290
   243
deba@2290
   244
  SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);
deba@2290
   245
  SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);
deba@2290
   246
  SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);
deba@2290
   247
  SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);
deba@2290
   248
  SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);
deba@2290
   249
deba@2290
   250
  ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);
deba@2290
   251
  ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);
deba@2290
   252
  ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);
deba@2290
   253
  ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);
deba@2290
   254
  ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);
deba@2290
   255
deba@2290
   256
  BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(target, source).
deba@2290
   257
    aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm).
deba@2290
   258
    edgeMap(tem, sem).uEdgeMap(tuem, suem).
deba@2290
   259
    aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer).
deba@2290
   260
    aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr).
deba@2290
   261
    edgeCrossRef(ecr).uEdgeCrossRef(uecr).
deba@2290
   262
    node(tn, sn).edge(te, se).uEdge(tue, sue).run();
deba@2290
   263
deba@2290
   264
  for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) {
deba@2290
   265
    check(nr[it] == anr[it], "Wrong copy.");
deba@2290
   266
    check(ancr[anr[it]] == it, "Wrong copy.");
deba@2290
   267
    check(sanm[it] == tanm[anr[it]], "Wrong copy.");
deba@2290
   268
  }
deba@2290
   269
deba@2290
   270
  for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) {
deba@2290
   271
    check(nr[it] == bnr[it], "Wrong copy.");
deba@2290
   272
    check(bncr[bnr[it]] == it, "Wrong copy.");
deba@2290
   273
    check(sbnm[it] == tbnm[bnr[it]], "Wrong copy.");
deba@2290
   274
  }
deba@2290
   275
deba@2290
   276
  for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) {
deba@2290
   277
    check(ncr[nr[it]] == it, "Wrong copy.");
deba@2290
   278
    check(snm[it] == tnm[nr[it]], "Wrong copy.");
deba@2290
   279
  }
deba@2290
   280
deba@2290
   281
  for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) {
deba@2290
   282
    check(ecr[er[it]] == it, "Wrong copy.");
deba@2290
   283
    check(sem[it] == tem[er[it]], "Wrong copy.");
deba@2290
   284
    check(nr[source.source(it)] == 
deba@2290
   285
                 target.source(er[it]), "Wrong copy.");
deba@2290
   286
    check(nr[source.target(it)] == 
deba@2290
   287
                 target.target(er[it]), "Wrong copy.");
deba@2290
   288
  }
deba@2290
   289
deba@2290
   290
  for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) {
deba@2290
   291
    check(uecr[uer[it]] == it, "Wrong copy.");
deba@2290
   292
    check(suem[it] == tuem[uer[it]], "Wrong copy.");
deba@2290
   293
    check(nr[source.aNode(it)] == 
deba@2290
   294
                 target.aNode(uer[it]), "Wrong copy.");
deba@2290
   295
    check(nr[source.bNode(it)] == 
deba@2290
   296
                 target.bNode(uer[it]), "Wrong copy.");
deba@2290
   297
  }
deba@2290
   298
deba@2290
   299
  for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) {
deba@2290
   300
    check(ancr[it] == ncr[it], "Wrong copy.");
deba@2290
   301
    check(anr[ancr[it]] == it, "Wrong copy.");
deba@2290
   302
  }
deba@2290
   303
deba@2290
   304
  for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) {
deba@2290
   305
    check(bncr[it] == ncr[it], "Wrong copy.");
deba@2290
   306
    check(bnr[bncr[it]] == it, "Wrong copy.");
deba@2290
   307
  }
deba@2290
   308
deba@2290
   309
  for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {
deba@2290
   310
    check(nr[ncr[it]] == it, "Wrong copy.");
deba@2290
   311
  }
deba@2290
   312
deba@2290
   313
  for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) {
deba@2290
   314
    check(er[ecr[it]] == it, "Wrong copy.");
deba@2290
   315
  }
deba@2290
   316
  for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) {
deba@2290
   317
    check(uer[uecr[it]] == it, "Wrong copy.");
deba@2290
   318
  }
deba@2290
   319
  check(tn == nr[sn], "Wrong copy.");
deba@2290
   320
  check(te == er[se], "Wrong copy.");
deba@2290
   321
  check(tue == uer[sue], "Wrong copy.");
deba@2290
   322
}
deba@2290
   323
deba@2290
   324
int main() {
deba@2290
   325
  graph_copy_test();
deba@2290
   326
  ugraph_copy_test();
deba@2290
   327
  bpugraph_copy_test();
deba@2290
   328
deba@2290
   329
  return 0; 
deba@2290
   330
}