COIN-OR::LEMON - Graph Library

source: lemon-1.1/test/graph_copy_test.cc @ 246:7c67988fca07

Last change on this file since 246:7c67988fca07 was 220:a5d8c039f218, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

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