COIN-OR::LEMON - Graph Library

source: lemon/test/graph_copy_test.cc @ 989:24b3f18ed9e2

Last change on this file since 989:24b3f18ed9e2 was 989:24b3f18ed9e2, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Improve graph_copy_test.cc

File size: 6.6 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
212
213int main() {
214  digraph_copy_test<SmartDigraph>();
215  digraph_copy_test<ListDigraph>();
216  digraph_copy_test<StaticDigraph>();
217  graph_copy_test<SmartGraph>();
218  graph_copy_test<ListGraph>();
219
220  return 0;
221}
Note: See TracBrowser for help on using the repository browser.