COIN-OR::LEMON - Graph Library

source: lemon/test/graph_copy_test.cc @ 1392:7c86f14b3bc5

Last change on this file since 1392:7c86f14b3bc5 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 6 years ago

Apply unify-sources.sh to the source tree

File size: 12.5 KB
Line 
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-2013
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
27using namespace std;
28using namespace lemon;
29
30template <typename GR>
31void 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
108template <typename GR>
109void 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
212template <typename GR>
213void bpgraph_copy_test() {
214  const int nn = 10;
215
216  // Build a graph
217  SmartBpGraph from;
218  SmartBpGraph::NodeMap<int> fnm(from);
219  SmartBpGraph::RedNodeMap<int> frnm(from);
220  SmartBpGraph::BlueNodeMap<int> fbnm(from);
221  SmartBpGraph::ArcMap<int> fam(from);
222  SmartBpGraph::EdgeMap<int> fem(from);
223  SmartBpGraph::Node fn = INVALID;
224  SmartBpGraph::RedNode frn = INVALID;
225  SmartBpGraph::BlueNode fbn = INVALID;
226  SmartBpGraph::Arc fa = INVALID;
227  SmartBpGraph::Edge fe = INVALID;
228
229  std::vector<SmartBpGraph::RedNode> frnv;
230  for (int i = 0; i < nn; ++i) {
231    SmartBpGraph::RedNode node = from.addRedNode();
232    frnv.push_back(node);
233    fnm[node] = i * i;
234    frnm[node] = i + i;
235    if (i == 0) {
236      fn = node;
237      frn = node;
238    }
239  }
240
241  std::vector<SmartBpGraph::BlueNode> fbnv;
242  for (int i = 0; i < nn; ++i) {
243    SmartBpGraph::BlueNode node = from.addBlueNode();
244    fbnv.push_back(node);
245    fnm[node] = i * i;
246    fbnm[node] = i + i;
247    if (i == 0) fbn = node;
248  }
249
250  for (int i = 0; i < nn; ++i) {
251    for (int j = 0; j < nn; ++j) {
252      SmartBpGraph::Edge edge = from.addEdge(frnv[i], fbnv[j]);
253      fem[edge] = i * i + j * j;
254      fam[from.direct(edge, true)] = i + j * j;
255      fam[from.direct(edge, false)] = i * i + j;
256      if (i == 0 && j == 0) fa = from.direct(edge, true);
257      if (i == 0 && j == 0) fe = edge;
258    }
259  }
260
261  // Test graph copy
262  GR to;
263  typename GR::template NodeMap<int> tnm(to);
264  typename GR::template RedNodeMap<int> trnm(to);
265  typename GR::template BlueNodeMap<int> tbnm(to);
266  typename GR::template ArcMap<int> tam(to);
267  typename GR::template EdgeMap<int> tem(to);
268  typename GR::Node tn;
269  typename GR::RedNode trn;
270  typename GR::BlueNode tbn;
271  typename GR::Arc ta;
272  typename GR::Edge te;
273
274  SmartBpGraph::NodeMap<typename GR::Node> nr(from);
275  SmartBpGraph::RedNodeMap<typename GR::RedNode> rnr(from);
276  SmartBpGraph::BlueNodeMap<typename GR::BlueNode> bnr(from);
277  SmartBpGraph::ArcMap<typename GR::Arc> ar(from);
278  SmartBpGraph::EdgeMap<typename GR::Edge> er(from);
279
280  typename GR::template NodeMap<SmartBpGraph::Node> ncr(to);
281  typename GR::template RedNodeMap<SmartBpGraph::RedNode> rncr(to);
282  typename GR::template BlueNodeMap<SmartBpGraph::BlueNode> bncr(to);
283  typename GR::template ArcMap<SmartBpGraph::Arc> acr(to);
284  typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to);
285
286  bpGraphCopy(from, to).
287    nodeMap(fnm, tnm).
288    redNodeMap(frnm, trnm).blueNodeMap(fbnm, tbnm).
289    arcMap(fam, tam).edgeMap(fem, tem).
290    nodeRef(nr).redRef(rnr).blueRef(bnr).
291    arcRef(ar).edgeRef(er).
292    nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr).
293    arcCrossRef(acr).edgeCrossRef(ecr).
294    node(fn, tn).redNode(frn, trn).blueNode(fbn, tbn).
295    arc(fa, ta).edge(fe, te).run();
296
297  check(countNodes(from) == countNodes(to), "Wrong copy.");
298  check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");
299  check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");
300  check(countEdges(from) == countEdges(to), "Wrong copy.");
301  check(countArcs(from) == countArcs(to), "Wrong copy.");
302
303  for (SmartBpGraph::NodeIt it(from); it != INVALID; ++it) {
304    check(ncr[nr[it]] == it, "Wrong copy.");
305    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
306  }
307
308  for (SmartBpGraph::RedNodeIt it(from); it != INVALID; ++it) {
309    check(ncr[nr[it]] == it, "Wrong copy.");
310    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
311    check(rnr[it] == nr[it], "Wrong copy.");
312    check(rncr[rnr[it]] == it, "Wrong copy.");
313    check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
314    check(to.red(rnr[it]), "Wrong copy.");
315  }
316
317  for (SmartBpGraph::BlueNodeIt it(from); it != INVALID; ++it) {
318    check(ncr[nr[it]] == it, "Wrong copy.");
319    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
320    check(bnr[it] == nr[it], "Wrong copy.");
321    check(bncr[bnr[it]] == it, "Wrong copy.");
322    check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
323    check(to.blue(bnr[it]), "Wrong copy.");
324  }
325
326  for (SmartBpGraph::ArcIt it(from); it != INVALID; ++it) {
327    check(acr[ar[it]] == it, "Wrong copy.");
328    check(fam[it] == tam[ar[it]], "Wrong copy.");
329    check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
330    check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
331  }
332
333  for (SmartBpGraph::EdgeIt it(from); it != INVALID; ++it) {
334    check(ecr[er[it]] == it, "Wrong copy.");
335    check(fem[it] == tem[er[it]], "Wrong copy.");
336    check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
337          "Wrong copy.");
338    check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
339          "Wrong copy.");
340    check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
341          "Wrong copy.");
342  }
343
344  for (typename GR::NodeIt it(to); it != INVALID; ++it) {
345    check(nr[ncr[it]] == it, "Wrong copy.");
346  }
347  for (typename GR::RedNodeIt it(to); it != INVALID; ++it) {
348    check(rncr[it] == ncr[it], "Wrong copy.");
349    check(rnr[rncr[it]] == it, "Wrong copy.");
350  }
351  for (typename GR::BlueNodeIt it(to); it != INVALID; ++it) {
352    check(bncr[it] == ncr[it], "Wrong copy.");
353    check(bnr[bncr[it]] == it, "Wrong copy.");
354  }
355  for (typename GR::ArcIt it(to); it != INVALID; ++it) {
356    check(ar[acr[it]] == it, "Wrong copy.");
357  }
358  for (typename GR::EdgeIt it(to); it != INVALID; ++it) {
359    check(er[ecr[it]] == it, "Wrong copy.");
360  }
361  check(tn == nr[fn], "Wrong copy.");
362  check(trn == rnr[frn], "Wrong copy.");
363  check(tbn == bnr[fbn], "Wrong copy.");
364  check(ta == ar[fa], "Wrong copy.");
365  check(te == er[fe], "Wrong copy.");
366
367  // Test repeated copy
368  bpGraphCopy(from, to).run();
369
370  check(countNodes(from) == countNodes(to), "Wrong copy.");
371  check(countRedNodes(from) == countRedNodes(to), "Wrong copy.");
372  check(countBlueNodes(from) == countBlueNodes(to), "Wrong copy.");
373  check(countEdges(from) == countEdges(to), "Wrong copy.");
374  check(countArcs(from) == countArcs(to), "Wrong copy.");
375}
376
377
378int main() {
379  digraph_copy_test<SmartDigraph>();
380  digraph_copy_test<ListDigraph>();
381  digraph_copy_test<StaticDigraph>();
382  graph_copy_test<SmartGraph>();
383  graph_copy_test<ListGraph>();
384  bpgraph_copy_test<SmartBpGraph>();
385  bpgraph_copy_test<ListBpGraph>();
386
387  return 0;
388}
Note: See TracBrowser for help on using the repository browser.