COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-main/test/edge_set_test.cc @ 1087:dd1443e4a34c

Last change on this file since 1087:dd1443e4a34c was 1084:8b2d4e5d96e4, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge #294 to branches >=1.2
File size: 10.2 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-2010
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 <iostream>
20#include <vector>
21
22#include <lemon/concepts/digraph.h>
23#include <lemon/concepts/graph.h>
24#include <lemon/concept_check.h>
25
26#include <lemon/list_graph.h>
27
28#include <lemon/edge_set.h>
29
30#include "graph_test.h"
31#include "test_tools.h"
32
33using namespace lemon;
34
35void checkSmartArcSet() {
36  checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
37
38  typedef ListDigraph Digraph;
39  typedef SmartArcSet<Digraph> ArcSet;
40
41  Digraph digraph;
42  Digraph::Node
43    n1 = digraph.addNode(),
44    n2 = digraph.addNode();
45
46  Digraph::Arc ga1 = digraph.addArc(n1, n2);
47  ::lemon::ignore_unused_variable_warning(ga1);
48
49  ArcSet arc_set(digraph);
50
51  Digraph::Arc ga2 = digraph.addArc(n2, n1);
52  ::lemon::ignore_unused_variable_warning(ga2);
53
54  checkGraphNodeList(arc_set, 2);
55  checkGraphArcList(arc_set, 0);
56
57  Digraph::Node
58    n3 = digraph.addNode();
59  checkGraphNodeList(arc_set, 3);
60  checkGraphArcList(arc_set, 0);
61
62  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
63  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
64  checkGraphNodeList(arc_set, 3);
65  checkGraphArcList(arc_set, 1);
66
67  checkGraphOutArcList(arc_set, n1, 1);
68  checkGraphOutArcList(arc_set, n2, 0);
69  checkGraphOutArcList(arc_set, n3, 0);
70
71  checkGraphInArcList(arc_set, n1, 0);
72  checkGraphInArcList(arc_set, n2, 1);
73  checkGraphInArcList(arc_set, n3, 0);
74
75  checkGraphConArcList(arc_set, 1);
76
77  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
78    a3 = arc_set.addArc(n2, n3),
79    a4 = arc_set.addArc(n2, n3);
80  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
81
82  checkGraphNodeList(arc_set, 3);
83  checkGraphArcList(arc_set, 4);
84
85  checkGraphOutArcList(arc_set, n1, 1);
86  checkGraphOutArcList(arc_set, n2, 3);
87  checkGraphOutArcList(arc_set, n3, 0);
88
89  checkGraphInArcList(arc_set, n1, 1);
90  checkGraphInArcList(arc_set, n2, 1);
91  checkGraphInArcList(arc_set, n3, 2);
92
93  checkGraphConArcList(arc_set, 4);
94
95  checkNodeIds(arc_set);
96  checkArcIds(arc_set);
97  checkGraphNodeMap(arc_set);
98  checkGraphArcMap(arc_set);
99
100  check(arc_set.valid(), "Wrong validity");
101  digraph.erase(n1);
102  check(!arc_set.valid(), "Wrong validity");
103}
104
105void checkListArcSet() {
106  checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();
107
108  typedef ListDigraph Digraph;
109  typedef ListArcSet<Digraph> ArcSet;
110
111  Digraph digraph;
112  Digraph::Node
113    n1 = digraph.addNode(),
114    n2 = digraph.addNode();
115
116  Digraph::Arc ga1 = digraph.addArc(n1, n2);
117  ::lemon::ignore_unused_variable_warning(ga1);
118
119  ArcSet arc_set(digraph);
120
121  Digraph::Arc ga2 = digraph.addArc(n2, n1);
122  ::lemon::ignore_unused_variable_warning(ga2);
123
124  checkGraphNodeList(arc_set, 2);
125  checkGraphArcList(arc_set, 0);
126
127  Digraph::Node
128    n3 = digraph.addNode();
129  checkGraphNodeList(arc_set, 3);
130  checkGraphArcList(arc_set, 0);
131
132  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
133  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
134  checkGraphNodeList(arc_set, 3);
135  checkGraphArcList(arc_set, 1);
136
137  checkGraphOutArcList(arc_set, n1, 1);
138  checkGraphOutArcList(arc_set, n2, 0);
139  checkGraphOutArcList(arc_set, n3, 0);
140
141  checkGraphInArcList(arc_set, n1, 0);
142  checkGraphInArcList(arc_set, n2, 1);
143  checkGraphInArcList(arc_set, n3, 0);
144
145  checkGraphConArcList(arc_set, 1);
146
147  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
148    a3 = arc_set.addArc(n2, n3),
149    a4 = arc_set.addArc(n2, n3);
150  ::lemon::ignore_unused_variable_warning(a2,a3,a4);
151
152  checkGraphNodeList(arc_set, 3);
153  checkGraphArcList(arc_set, 4);
154
155  checkGraphOutArcList(arc_set, n1, 1);
156  checkGraphOutArcList(arc_set, n2, 3);
157  checkGraphOutArcList(arc_set, n3, 0);
158
159  checkGraphInArcList(arc_set, n1, 1);
160  checkGraphInArcList(arc_set, n2, 1);
161  checkGraphInArcList(arc_set, n3, 2);
162
163  checkGraphConArcList(arc_set, 4);
164
165  checkNodeIds(arc_set);
166  checkArcIds(arc_set);
167  checkGraphNodeMap(arc_set);
168  checkGraphArcMap(arc_set);
169
170  digraph.erase(n1);
171
172  checkGraphNodeList(arc_set, 2);
173  checkGraphArcList(arc_set, 2);
174
175  checkGraphOutArcList(arc_set, n2, 2);
176  checkGraphOutArcList(arc_set, n3, 0);
177
178  checkGraphInArcList(arc_set, n2, 0);
179  checkGraphInArcList(arc_set, n3, 2);
180
181  checkNodeIds(arc_set);
182  checkArcIds(arc_set);
183  checkGraphNodeMap(arc_set);
184  checkGraphArcMap(arc_set);
185
186  checkGraphConArcList(arc_set, 2);
187}
188
189void checkSmartEdgeSet() {
190  checkConcept<concepts::Digraph, SmartEdgeSet<ListDigraph> >();
191
192  typedef ListDigraph Digraph;
193  typedef SmartEdgeSet<Digraph> EdgeSet;
194
195  Digraph digraph;
196  Digraph::Node
197    n1 = digraph.addNode(),
198    n2 = digraph.addNode();
199
200  Digraph::Arc ga1 = digraph.addArc(n1, n2);
201  ::lemon::ignore_unused_variable_warning(ga1);
202
203  EdgeSet edge_set(digraph);
204
205  Digraph::Arc ga2 = digraph.addArc(n2, n1);
206  ::lemon::ignore_unused_variable_warning(ga2);
207
208  checkGraphNodeList(edge_set, 2);
209  checkGraphArcList(edge_set, 0);
210  checkGraphEdgeList(edge_set, 0);
211
212  Digraph::Node
213    n3 = digraph.addNode();
214  checkGraphNodeList(edge_set, 3);
215  checkGraphArcList(edge_set, 0);
216  checkGraphEdgeList(edge_set, 0);
217
218  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
219  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
220        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
221  checkGraphNodeList(edge_set, 3);
222  checkGraphArcList(edge_set, 2);
223  checkGraphEdgeList(edge_set, 1);
224
225  checkGraphOutArcList(edge_set, n1, 1);
226  checkGraphOutArcList(edge_set, n2, 1);
227  checkGraphOutArcList(edge_set, n3, 0);
228
229  checkGraphInArcList(edge_set, n1, 1);
230  checkGraphInArcList(edge_set, n2, 1);
231  checkGraphInArcList(edge_set, n3, 0);
232
233  checkGraphIncEdgeList(edge_set, n1, 1);
234  checkGraphIncEdgeList(edge_set, n2, 1);
235  checkGraphIncEdgeList(edge_set, n3, 0);
236
237  checkGraphConEdgeList(edge_set, 1);
238  checkGraphConArcList(edge_set, 2);
239
240  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
241    e3 = edge_set.addEdge(n2, n3),
242    e4 = edge_set.addEdge(n2, n3);
243  ::lemon::ignore_unused_variable_warning(e2,e3,e4);
244
245  checkGraphNodeList(edge_set, 3);
246  checkGraphEdgeList(edge_set, 4);
247
248  checkGraphOutArcList(edge_set, n1, 2);
249  checkGraphOutArcList(edge_set, n2, 4);
250  checkGraphOutArcList(edge_set, n3, 2);
251
252  checkGraphInArcList(edge_set, n1, 2);
253  checkGraphInArcList(edge_set, n2, 4);
254  checkGraphInArcList(edge_set, n3, 2);
255
256  checkGraphIncEdgeList(edge_set, n1, 2);
257  checkGraphIncEdgeList(edge_set, n2, 4);
258  checkGraphIncEdgeList(edge_set, n3, 2);
259
260  checkGraphConEdgeList(edge_set, 4);
261  checkGraphConArcList(edge_set, 8);
262
263  checkArcDirections(edge_set);
264
265  checkNodeIds(edge_set);
266  checkArcIds(edge_set);
267  checkEdgeIds(edge_set);
268  checkGraphNodeMap(edge_set);
269  checkGraphArcMap(edge_set);
270  checkGraphEdgeMap(edge_set);
271
272  check(edge_set.valid(), "Wrong validity");
273  digraph.erase(n1);
274  check(!edge_set.valid(), "Wrong validity");
275}
276
277void checkListEdgeSet() {
278  checkConcept<concepts::Digraph, ListEdgeSet<ListDigraph> >();
279
280  typedef ListDigraph Digraph;
281  typedef ListEdgeSet<Digraph> EdgeSet;
282
283  Digraph digraph;
284  Digraph::Node
285    n1 = digraph.addNode(),
286    n2 = digraph.addNode();
287
288  Digraph::Arc ga1 = digraph.addArc(n1, n2);
289  ::lemon::ignore_unused_variable_warning(ga1);
290
291  EdgeSet edge_set(digraph);
292
293  Digraph::Arc ga2 = digraph.addArc(n2, n1);
294  ::lemon::ignore_unused_variable_warning(ga2);
295
296  checkGraphNodeList(edge_set, 2);
297  checkGraphArcList(edge_set, 0);
298  checkGraphEdgeList(edge_set, 0);
299
300  Digraph::Node
301    n3 = digraph.addNode();
302  checkGraphNodeList(edge_set, 3);
303  checkGraphArcList(edge_set, 0);
304  checkGraphEdgeList(edge_set, 0);
305
306  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
307  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
308        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
309  checkGraphNodeList(edge_set, 3);
310  checkGraphArcList(edge_set, 2);
311  checkGraphEdgeList(edge_set, 1);
312
313  checkGraphOutArcList(edge_set, n1, 1);
314  checkGraphOutArcList(edge_set, n2, 1);
315  checkGraphOutArcList(edge_set, n3, 0);
316
317  checkGraphInArcList(edge_set, n1, 1);
318  checkGraphInArcList(edge_set, n2, 1);
319  checkGraphInArcList(edge_set, n3, 0);
320
321  checkGraphIncEdgeList(edge_set, n1, 1);
322  checkGraphIncEdgeList(edge_set, n2, 1);
323  checkGraphIncEdgeList(edge_set, n3, 0);
324
325  checkGraphConEdgeList(edge_set, 1);
326  checkGraphConArcList(edge_set, 2);
327
328  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
329    e3 = edge_set.addEdge(n2, n3),
330    e4 = edge_set.addEdge(n2, n3);
331  ::lemon::ignore_unused_variable_warning(e2,e3,e4);
332
333  checkGraphNodeList(edge_set, 3);
334  checkGraphEdgeList(edge_set, 4);
335
336  checkGraphOutArcList(edge_set, n1, 2);
337  checkGraphOutArcList(edge_set, n2, 4);
338  checkGraphOutArcList(edge_set, n3, 2);
339
340  checkGraphInArcList(edge_set, n1, 2);
341  checkGraphInArcList(edge_set, n2, 4);
342  checkGraphInArcList(edge_set, n3, 2);
343
344  checkGraphIncEdgeList(edge_set, n1, 2);
345  checkGraphIncEdgeList(edge_set, n2, 4);
346  checkGraphIncEdgeList(edge_set, n3, 2);
347
348  checkGraphConEdgeList(edge_set, 4);
349  checkGraphConArcList(edge_set, 8);
350
351  checkArcDirections(edge_set);
352
353  checkNodeIds(edge_set);
354  checkArcIds(edge_set);
355  checkEdgeIds(edge_set);
356  checkGraphNodeMap(edge_set);
357  checkGraphArcMap(edge_set);
358  checkGraphEdgeMap(edge_set);
359
360  digraph.erase(n1);
361
362  checkGraphNodeList(edge_set, 2);
363  checkGraphArcList(edge_set, 4);
364  checkGraphEdgeList(edge_set, 2);
365
366  checkGraphOutArcList(edge_set, n2, 2);
367  checkGraphOutArcList(edge_set, n3, 2);
368
369  checkGraphInArcList(edge_set, n2, 2);
370  checkGraphInArcList(edge_set, n3, 2);
371
372  checkGraphIncEdgeList(edge_set, n2, 2);
373  checkGraphIncEdgeList(edge_set, n3, 2);
374
375  checkNodeIds(edge_set);
376  checkArcIds(edge_set);
377  checkEdgeIds(edge_set);
378  checkGraphNodeMap(edge_set);
379  checkGraphArcMap(edge_set);
380  checkGraphEdgeMap(edge_set);
381
382  checkGraphConEdgeList(edge_set, 2);
383  checkGraphConArcList(edge_set, 4);
384
385}
386
387
388int main() {
389
390  checkSmartArcSet();
391  checkListArcSet();
392  checkSmartEdgeSet();
393  checkListEdgeSet();
394
395  return 0;
396}
Note: See TracBrowser for help on using the repository browser.