COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/graph_copy_test.cc @ 912:cc9bb4f95ed3

1.2
Last change on this file since 912:cc9bb4f95ed3 was 896:e958855b8186, checked in by Alpar Juttner <alpar@…>, 9 years ago

Merge bugfix #371 to branch 1.2

File size: 6.3 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/lgf_reader.h>
22#include <lemon/error.h>
23
24#include "test_tools.h"
25
26using namespace std;
27using namespace lemon;
28
29void digraph_copy_test() {
30  const int nn = 10;
31
32  // Build a digraph
33  SmartDigraph from;
34  SmartDigraph::NodeMap<int> fnm(from);
35  SmartDigraph::ArcMap<int> fam(from);
36  SmartDigraph::Node fn = INVALID;
37  SmartDigraph::Arc fa = INVALID;
38
39  std::vector<SmartDigraph::Node> fnv;
40  for (int i = 0; i < nn; ++i) {
41    SmartDigraph::Node node = from.addNode();
42    fnv.push_back(node);
43    fnm[node] = i * i;
44    if (i == 0) fn = node;
45  }
46
47  for (int i = 0; i < nn; ++i) {
48    for (int j = 0; j < nn; ++j) {
49      SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);
50      fam[arc] = i + j * j;
51      if (i == 0 && j == 0) fa = arc;
52    }
53  }
54
55  // Test digraph copy
56  ListDigraph to;
57  ListDigraph::NodeMap<int> tnm(to);
58  ListDigraph::ArcMap<int> tam(to);
59  ListDigraph::Node tn;
60  ListDigraph::Arc ta;
61
62  SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
63  SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
64
65  ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
66  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
67
68  digraphCopy(from, to).
69    nodeMap(fnm, tnm).arcMap(fam, tam).
70    nodeRef(nr).arcRef(er).
71    nodeCrossRef(ncr).arcCrossRef(ecr).
72    node(fn, tn).arc(fa, ta).run();
73 
74  check(countNodes(from) == countNodes(to), "Wrong copy.");
75  check(countArcs(from) == countArcs(to), "Wrong copy.");
76
77  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
78    check(ncr[nr[it]] == it, "Wrong copy.");
79    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
80  }
81
82  for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
83    check(ecr[er[it]] == it, "Wrong copy.");
84    check(fam[it] == tam[er[it]], "Wrong copy.");
85    check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
86    check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
87  }
88
89  for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
90    check(nr[ncr[it]] == it, "Wrong copy.");
91  }
92
93  for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
94    check(er[ecr[it]] == it, "Wrong copy.");
95  }
96  check(tn == nr[fn], "Wrong copy.");
97  check(ta == er[fa], "Wrong copy.");
98
99  // Test repeated copy
100  digraphCopy(from, to).run();
101 
102  check(countNodes(from) == countNodes(to), "Wrong copy.");
103  check(countArcs(from) == countArcs(to), "Wrong copy.");
104}
105
106void graph_copy_test() {
107  const int nn = 10;
108
109  // Build a graph
110  SmartGraph from;
111  SmartGraph::NodeMap<int> fnm(from);
112  SmartGraph::ArcMap<int> fam(from);
113  SmartGraph::EdgeMap<int> fem(from);
114  SmartGraph::Node fn = INVALID;
115  SmartGraph::Arc fa = INVALID;
116  SmartGraph::Edge fe = INVALID;
117
118  std::vector<SmartGraph::Node> fnv;
119  for (int i = 0; i < nn; ++i) {
120    SmartGraph::Node node = from.addNode();
121    fnv.push_back(node);
122    fnm[node] = i * i;
123    if (i == 0) fn = node;
124  }
125
126  for (int i = 0; i < nn; ++i) {
127    for (int j = 0; j < nn; ++j) {
128      SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
129      fem[edge] = i * i + j * j;
130      fam[from.direct(edge, true)] = i + j * j;
131      fam[from.direct(edge, false)] = i * i + j;
132      if (i == 0 && j == 0) fa = from.direct(edge, true);
133      if (i == 0 && j == 0) fe = edge;
134    }
135  }
136
137  // Test graph copy
138  ListGraph to;
139  ListGraph::NodeMap<int> tnm(to);
140  ListGraph::ArcMap<int> tam(to);
141  ListGraph::EdgeMap<int> tem(to);
142  ListGraph::Node tn;
143  ListGraph::Arc ta;
144  ListGraph::Edge te;
145
146  SmartGraph::NodeMap<ListGraph::Node> nr(from);
147  SmartGraph::ArcMap<ListGraph::Arc> ar(from);
148  SmartGraph::EdgeMap<ListGraph::Edge> er(from);
149
150  ListGraph::NodeMap<SmartGraph::Node> ncr(to);
151  ListGraph::ArcMap<SmartGraph::Arc> acr(to);
152  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
153
154  graphCopy(from, to).
155    nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).
156    nodeRef(nr).arcRef(ar).edgeRef(er).
157    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
158    node(fn, tn).arc(fa, ta).edge(fe, te).run();
159
160  check(countNodes(from) == countNodes(to), "Wrong copy.");
161  check(countEdges(from) == countEdges(to), "Wrong copy.");
162  check(countArcs(from) == countArcs(to), "Wrong copy.");
163
164  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
165    check(ncr[nr[it]] == it, "Wrong copy.");
166    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
167  }
168
169  for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
170    check(acr[ar[it]] == it, "Wrong copy.");
171    check(fam[it] == tam[ar[it]], "Wrong copy.");
172    check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
173    check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
174  }
175
176  for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
177    check(ecr[er[it]] == it, "Wrong copy.");
178    check(fem[it] == tem[er[it]], "Wrong copy.");
179    check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
180          "Wrong copy.");
181    check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
182          "Wrong copy.");
183    check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
184          "Wrong copy.");
185  }
186
187  for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
188    check(nr[ncr[it]] == it, "Wrong copy.");
189  }
190
191  for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
192    check(ar[acr[it]] == it, "Wrong copy.");
193  }
194  for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
195    check(er[ecr[it]] == it, "Wrong copy.");
196  }
197  check(tn == nr[fn], "Wrong copy.");
198  check(ta == ar[fa], "Wrong copy.");
199  check(te == er[fe], "Wrong copy.");
200
201  // Test repeated copy
202  graphCopy(from, to).run();
203 
204  check(countNodes(from) == countNodes(to), "Wrong copy.");
205  check(countEdges(from) == countEdges(to), "Wrong copy.");
206  check(countArcs(from) == countArcs(to), "Wrong copy.");
207}
208
209
210int main() {
211  digraph_copy_test();
212  graph_copy_test();
213
214  return 0;
215}
Note: See TracBrowser for help on using the repository browser.