COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/graph_copy_test.cc @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

File size: 10.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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/graph_reader.h>
22#include <lemon/graph_utils.h>
23#include <lemon/error.h>
24
25#include "test_tools.h"
26
27using namespace std;
28using namespace lemon;
29
30void graph_copy_test() {
31  const int nn = 10;
32
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;
38
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  }
46
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  }
54
55  ListGraph target;
56  ListGraph::NodeMap<int> tnm(target);
57  ListGraph::EdgeMap<int> tem(target);
58  ListGraph::Node tn;
59  ListGraph::Edge te;
60
61  SmartGraph::NodeMap<ListGraph::Node> nr(source);
62  SmartGraph::EdgeMap<ListGraph::Edge> er(source);
63
64  ListGraph::NodeMap<SmartGraph::Node> ncr(target);
65  ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);
66
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();
72
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  }
77
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  }
86
87  for (ListGraph::NodeIt it(target); it != INVALID; ++it) {
88    check(nr[ncr[it]] == it, "Wrong copy.");
89  }
90
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}
97
98void ugraph_copy_test() {
99  const int nn = 10;
100
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;
108
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  }
116
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  }
127 
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;
135
136  SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
137  SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
138  SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);
139
140  ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
141  ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
142  ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);
143
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();
149
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  }
154
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  }
163
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  }
177
178  for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {
179    check(nr[ncr[it]] == it, "Wrong copy.");
180  }
181
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}
192
193void bpugraph_copy_test() {
194  const int nn = 10;
195
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;
205
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  }
214
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  }
222
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  }
233 
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;
243
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);
249
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);
255
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();
263
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  }
269
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  }
275
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  }
280
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  }
289
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  }
298
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  }
303
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  }
308
309  for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {
310    check(nr[ncr[it]] == it, "Wrong copy.");
311  }
312
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}
323
324int main() {
325  graph_copy_test();
326  ugraph_copy_test();
327  bpugraph_copy_test();
328
329  return 0;
330}
Note: See TracBrowser for help on using the repository browser.