COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/graph_copy_test.cc @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2344:48ecc4feb42b, checked in by Balazs Dezso, 13 years ago

Bug fix

File size: 10.0 KB
Line 
1#include <lemon/smart_graph.h>
2#include <lemon/list_graph.h>
3#include <lemon/graph_reader.h>
4#include <lemon/graph_utils.h>
5#include <lemon/error.h>
6
7#include "test_tools.h"
8
9using namespace std;
10using namespace lemon;
11
12void graph_copy_test() {
13  const int nn = 10;
14
15  SmartGraph source;
16  SmartGraph::NodeMap<int> snm(source);
17  SmartGraph::EdgeMap<int> sem(source);
18  SmartGraph::Node sn = INVALID;
19  SmartGraph::Edge se = INVALID;
20
21  std::vector<SmartGraph::Node> snv;
22  for (int i = 0; i < nn; ++i) {
23    SmartGraph::Node node = source.addNode();
24    snv.push_back(node);
25    snm[node] = i * i;
26    if (i == 0) sn = node;
27  }
28
29  for (int i = 0; i < nn; ++i) {
30    for (int j = 0; j < nn; ++j) {
31      SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]);
32      sem[edge] = i + j * j;
33      if (i == 0 && j == 0) se = edge;
34    }
35  }
36
37  ListGraph target;
38  ListGraph::NodeMap<int> tnm(target);
39  ListGraph::EdgeMap<int> tem(target);
40  ListGraph::Node tn;
41  ListGraph::Edge te;
42
43  SmartGraph::NodeMap<ListGraph::Node> nr(source);
44  SmartGraph::EdgeMap<ListGraph::Edge> er(source);
45
46  ListGraph::NodeMap<SmartGraph::Node> ncr(target);
47  ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);
48
49  GraphCopy<ListGraph, SmartGraph>(target, source).
50    nodeMap(tnm, snm).edgeMap(tem, sem).
51    nodeRef(nr).edgeRef(er).
52    nodeCrossRef(ncr).edgeCrossRef(ecr).
53    node(tn, sn).edge(te, se).run();
54
55  for (SmartGraph::NodeIt it(source); it != INVALID; ++it) {
56    check(ncr[nr[it]] == it, "Wrong copy.");
57    check(snm[it] == tnm[nr[it]], "Wrong copy.");
58  }
59
60  for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) {
61    check(ecr[er[it]] == it, "Wrong copy.");
62    check(sem[it] == tem[er[it]], "Wrong copy.");
63    check(nr[source.source(it)] ==
64                 target.source(er[it]), "Wrong copy.");
65    check(nr[source.target(it)] ==
66                 target.target(er[it]), "Wrong copy.");
67  }
68
69  for (ListGraph::NodeIt it(target); it != INVALID; ++it) {
70    check(nr[ncr[it]] == it, "Wrong copy.");
71  }
72
73  for (ListGraph::EdgeIt it(target); it != INVALID; ++it) {
74    check(er[ecr[it]] == it, "Wrong copy.");
75  }
76  check(tn == nr[sn], "Wrong copy.");
77  check(te == er[se], "Wrong copy.");
78}
79
80void ugraph_copy_test() {
81  const int nn = 10;
82
83  SmartUGraph source;
84  SmartUGraph::NodeMap<int> snm(source);
85  SmartUGraph::EdgeMap<int> sem(source);
86  SmartUGraph::UEdgeMap<int> suem(source);
87  SmartUGraph::Node sn = INVALID;
88  SmartUGraph::Edge se = INVALID;
89  SmartUGraph::UEdge sue = INVALID;
90
91  std::vector<SmartUGraph::Node> snv;
92  for (int i = 0; i < nn; ++i) {
93    SmartUGraph::Node node = source.addNode();
94    snv.push_back(node);
95    snm[node] = i * i;
96    if (i == 0) sn = node;
97  }
98
99  for (int i = 0; i < nn; ++i) {
100    for (int j = 0; j < nn; ++j) {
101      SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]);
102      suem[edge] = i * i + j * j;
103      sem[source.direct(edge, true)] = i + j * j;
104      sem[source.direct(edge, false)] = i * i + j;
105      if (i == 0 && j == 0) se = source.direct(edge, true);
106      if (i == 0 && j == 0) sue = edge;
107    }
108  }
109 
110  ListUGraph target;
111  ListUGraph::NodeMap<int> tnm(target);
112  ListUGraph::EdgeMap<int> tem(target);
113  ListUGraph::UEdgeMap<int> tuem(target);
114  ListUGraph::Node tn;
115  ListUGraph::Edge te;
116  ListUGraph::UEdge tue;
117
118  SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
119  SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
120  SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);
121
122  ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
123  ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
124  ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);
125
126  UGraphCopy<ListUGraph, SmartUGraph>(target, source).
127    nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem).
128    nodeRef(nr).edgeRef(er).uEdgeRef(uer).
129    nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr).
130    node(tn, sn).edge(te, se).uEdge(tue, sue).run();
131
132  for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) {
133    check(ncr[nr[it]] == it, "Wrong copy.");
134    check(snm[it] == tnm[nr[it]], "Wrong copy.");
135  }
136
137  for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) {
138    check(ecr[er[it]] == it, "Wrong copy.");
139    check(sem[it] == tem[er[it]], "Wrong copy.");
140    check(nr[source.source(it)] ==
141                 target.source(er[it]), "Wrong copy.");
142    check(nr[source.target(it)] ==
143                 target.target(er[it]), "Wrong copy.");
144  }
145
146  for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) {
147    check(uecr[uer[it]] == it, "Wrong copy.");
148    check(suem[it] == tuem[uer[it]], "Wrong copy.");
149    check(nr[source.source(it)] == target.source(uer[it]) ||
150                 nr[source.source(it)] == target.target(uer[it]),
151                 "Wrong copy.");
152    check(nr[source.target(it)] == target.source(uer[it]) ||
153                 nr[source.target(it)] == target.target(uer[it]),
154                 "Wrong copy.");
155    check((source.source(it) != source.target(it)) ==
156                 (target.source(uer[it]) != target.target(uer[it])),
157                 "Wrong copy.");
158  }
159
160  for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {
161    check(nr[ncr[it]] == it, "Wrong copy.");
162  }
163
164  for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) {
165    check(er[ecr[it]] == it, "Wrong copy.");
166  }
167  for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) {
168    check(uer[uecr[it]] == it, "Wrong copy.");
169  }
170  check(tn == nr[sn], "Wrong copy.");
171  check(te == er[se], "Wrong copy.");
172  check(tue == uer[sue], "Wrong copy.");
173}
174
175void bpugraph_copy_test() {
176  const int nn = 10;
177
178  SmartBpUGraph source;
179  SmartBpUGraph::ANodeMap<int> sanm(source);
180  SmartBpUGraph::BNodeMap<int> sbnm(source);
181  SmartBpUGraph::NodeMap<int> snm(source);
182  SmartBpUGraph::EdgeMap<int> sem(source);
183  SmartBpUGraph::UEdgeMap<int> suem(source);
184  SmartBpUGraph::Node sn = INVALID;
185  SmartBpUGraph::Edge se = INVALID;
186  SmartBpUGraph::UEdge sue = INVALID;
187
188  std::vector<SmartBpUGraph::Node> sanv;
189  for (int i = 0; i < nn; ++i) {
190    SmartBpUGraph::Node node = source.addANode();
191    sanv.push_back(node);
192    sanm[node] = i * i;
193    snm[node] = i * i + i;
194    if (i == 0) sn = node;
195  }
196
197  std::vector<SmartBpUGraph::Node> sbnv;
198  for (int i = 0; i < nn; ++i) {
199    SmartBpUGraph::Node node = source.addBNode();
200    sbnv.push_back(node);
201    sbnm[node] = i * i - i;
202    snm[node] = i * i + i + 1;
203  }
204
205  for (int i = 0; i < nn; ++i) {
206    for (int j = 0; j < nn; ++j) {
207      SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]);
208      suem[edge] = i * i + j * j;
209      sem[source.direct(edge, true)] = i + j * j;
210      sem[source.direct(edge, false)] = i * i + j;
211      if (i == 0 && j == 0) se = source.direct(edge, true);
212      if (i == 0 && j == 0) sue = edge;
213    }
214  }
215 
216  ListBpUGraph target;
217  ListBpUGraph::ANodeMap<int> tanm(target);
218  ListBpUGraph::BNodeMap<int> tbnm(target);
219  ListBpUGraph::NodeMap<int> tnm(target);
220  ListBpUGraph::EdgeMap<int> tem(target);
221  ListBpUGraph::UEdgeMap<int> tuem(target);
222  ListBpUGraph::Node tn;
223  ListBpUGraph::Edge te;
224  ListBpUGraph::UEdge tue;
225
226  SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);
227  SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);
228  SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);
229  SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);
230  SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);
231
232  ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);
233  ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);
234  ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);
235  ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);
236  ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);
237
238  BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(target, source).
239    aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm).
240    edgeMap(tem, sem).uEdgeMap(tuem, suem).
241    aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer).
242    aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr).
243    edgeCrossRef(ecr).uEdgeCrossRef(uecr).
244    node(tn, sn).edge(te, se).uEdge(tue, sue).run();
245
246  for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) {
247    check(nr[it] == anr[it], "Wrong copy.");
248    check(ancr[anr[it]] == it, "Wrong copy.");
249    check(sanm[it] == tanm[anr[it]], "Wrong copy.");
250  }
251
252  for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) {
253    check(nr[it] == bnr[it], "Wrong copy.");
254    check(bncr[bnr[it]] == it, "Wrong copy.");
255    check(sbnm[it] == tbnm[bnr[it]], "Wrong copy.");
256  }
257
258  for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) {
259    check(ncr[nr[it]] == it, "Wrong copy.");
260    check(snm[it] == tnm[nr[it]], "Wrong copy.");
261  }
262
263  for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) {
264    check(ecr[er[it]] == it, "Wrong copy.");
265    check(sem[it] == tem[er[it]], "Wrong copy.");
266    check(nr[source.source(it)] ==
267                 target.source(er[it]), "Wrong copy.");
268    check(nr[source.target(it)] ==
269                 target.target(er[it]), "Wrong copy.");
270  }
271
272  for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) {
273    check(uecr[uer[it]] == it, "Wrong copy.");
274    check(suem[it] == tuem[uer[it]], "Wrong copy.");
275    check(nr[source.aNode(it)] ==
276                 target.aNode(uer[it]), "Wrong copy.");
277    check(nr[source.bNode(it)] ==
278                 target.bNode(uer[it]), "Wrong copy.");
279  }
280
281  for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) {
282    check(ancr[it] == ncr[it], "Wrong copy.");
283    check(anr[ancr[it]] == it, "Wrong copy.");
284  }
285
286  for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) {
287    check(bncr[it] == ncr[it], "Wrong copy.");
288    check(bnr[bncr[it]] == it, "Wrong copy.");
289  }
290
291  for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {
292    check(nr[ncr[it]] == it, "Wrong copy.");
293  }
294
295  for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) {
296    check(er[ecr[it]] == it, "Wrong copy.");
297  }
298  for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) {
299    check(uer[uecr[it]] == it, "Wrong copy.");
300  }
301  check(tn == nr[sn], "Wrong copy.");
302  check(te == er[se], "Wrong copy.");
303  check(tue == uer[sue], "Wrong copy.");
304}
305
306int main() {
307  graph_copy_test();
308  ugraph_copy_test();
309  bpugraph_copy_test();
310
311  return 0;
312}
Note: See TracBrowser for help on using the repository browser.