COIN-OR::LEMON - Graph Library

source: lemon-main/test/graph_copy_test.cc @ 1022:523e45e37e52

Last change on this file since 1022:523e45e37e52 was 1022:523e45e37e52, checked in by Balazs Dezso <deba@…>, 14 years ago

Implementation of BpGraphCopy? (#69)

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