COIN-OR::LEMON - Graph Library

source: lemon/test/graph_test.h @ 1296:330264b171cf

Last change on this file since 1296:330264b171cf was 1195:8b2b9e61d8ce, checked in by Balazs Dezso <deba@…>, 12 years ago

Remove asRedBludeNode() function (#69)

File size: 13.0 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#ifndef LEMON_TEST_GRAPH_TEST_H
20#define LEMON_TEST_GRAPH_TEST_H
21
22#include <set>
23
24#include <lemon/core.h>
25#include <lemon/maps.h>
26
27#include "test_tools.h"
28
29namespace lemon {
30
31  template<class Graph>
32  void checkGraphNodeList(const Graph &G, int cnt)
33  {
34    typename Graph::NodeIt n(G);
35    for(int i=0;i<cnt;i++) {
36      check(n!=INVALID,"Wrong Node list linking.");
37      ++n;
38    }
39    check(n==INVALID,"Wrong Node list linking.");
40    check(countNodes(G)==cnt,"Wrong Node number.");
41  }
42
43  template<class Graph>
44  void checkGraphRedNodeList(const Graph &G, int cnt)
45  {
46    typename Graph::RedNodeIt n(G);
47    for(int i=0;i<cnt;i++) {
48      check(n!=INVALID,"Wrong red Node list linking.");
49      check(G.red(n),"Wrong node set check.");
50      check(!G.blue(n),"Wrong node set check.");
51      typename Graph::Node nn = n;
52      check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion.");
53      check(G.asRedNode(nn) == n,"Wrong node conversion.");
54      check(G.asBlueNode(nn) == INVALID,"Wrong node conversion.");
55      ++n;
56    }
57    check(n==INVALID,"Wrong red Node list linking.");
58    check(countRedNodes(G)==cnt,"Wrong red Node number.");
59  }
60
61  template<class Graph>
62  void checkGraphBlueNodeList(const Graph &G, int cnt)
63  {
64    typename Graph::BlueNodeIt n(G);
65    for(int i=0;i<cnt;i++) {
66      check(n!=INVALID,"Wrong blue Node list linking.");
67      check(G.blue(n),"Wrong node set check.");
68      check(!G.red(n),"Wrong node set check.");
69      typename Graph::Node nn = n;
70      check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion.");
71      check(G.asBlueNode(nn) == n,"Wrong node conversion.");
72      check(G.asRedNode(nn) == INVALID,"Wrong node conversion.");
73      ++n;
74    }
75    check(n==INVALID,"Wrong blue Node list linking.");
76    check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
77  }
78
79  template<class Graph>
80  void checkGraphArcList(const Graph &G, int cnt)
81  {
82    typename Graph::ArcIt e(G);
83    for(int i=0;i<cnt;i++) {
84      check(e!=INVALID,"Wrong Arc list linking.");
85      check(G.oppositeNode(G.source(e), e) == G.target(e),
86            "Wrong opposite node");
87      check(G.oppositeNode(G.target(e), e) == G.source(e),
88            "Wrong opposite node");
89      ++e;
90    }
91    check(e==INVALID,"Wrong Arc list linking.");
92    check(countArcs(G)==cnt,"Wrong Arc number.");
93  }
94
95  template<class Graph>
96  void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
97  {
98    typename Graph::OutArcIt e(G,n);
99    for(int i=0;i<cnt;i++) {
100      check(e!=INVALID,"Wrong OutArc list linking.");
101      check(n==G.source(e),"Wrong OutArc list linking.");
102      check(n==G.baseNode(e),"Wrong OutArc list linking.");
103      check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
104      ++e;
105    }
106    check(e==INVALID,"Wrong OutArc list linking.");
107    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
108  }
109
110  template<class Graph>
111  void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
112  {
113    typename Graph::InArcIt e(G,n);
114    for(int i=0;i<cnt;i++) {
115      check(e!=INVALID,"Wrong InArc list linking.");
116      check(n==G.target(e),"Wrong InArc list linking.");
117      check(n==G.baseNode(e),"Wrong OutArc list linking.");
118      check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
119      ++e;
120    }
121    check(e==INVALID,"Wrong InArc list linking.");
122    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
123  }
124
125  template<class Graph>
126  void checkGraphEdgeList(const Graph &G, int cnt)
127  {
128    typename Graph::EdgeIt e(G);
129    for(int i=0;i<cnt;i++) {
130      check(e!=INVALID,"Wrong Edge list linking.");
131      check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
132      check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
133      ++e;
134    }
135    check(e==INVALID,"Wrong Edge list linking.");
136    check(countEdges(G)==cnt,"Wrong Edge number.");
137  }
138
139  template<class Graph>
140  void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
141  {
142    typename Graph::IncEdgeIt e(G,n);
143    for(int i=0;i<cnt;i++) {
144      check(e!=INVALID,"Wrong IncEdge list linking.");
145      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
146      check(n==G.baseNode(e),"Wrong OutArc list linking.");
147      check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
148            "Wrong OutArc list linking.");
149      ++e;
150    }
151    check(e==INVALID,"Wrong IncEdge list linking.");
152    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
153  }
154
155  template <class Graph>
156  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
157                                 int cnt)
158  {
159    checkGraphIncEdgeList(G, n, cnt);
160    checkGraphOutArcList(G, n, cnt);
161    checkGraphInArcList(G, n, cnt);
162  }
163
164  template <class Graph>
165  void checkGraphConArcList(const Graph &G, int cnt) {
166    int i = 0;
167    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
168      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
169        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
170          check(G.source(a) == u, "Wrong iterator.");
171          check(G.target(a) == v, "Wrong iterator.");
172          ++i;
173        }
174      }
175    }
176    check(cnt == i, "Wrong iterator.");
177  }
178
179  template <class Graph>
180  void checkGraphConEdgeList(const Graph &G, int cnt) {
181    int i = 0;
182    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
183      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
184        for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
185          check((G.u(e) == u && G.v(e) == v) ||
186                (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
187          i += u == v ? 2 : 1;
188        }
189      }
190    }
191    check(2 * cnt == i, "Wrong iterator.");
192  }
193
194  template <typename Graph>
195  void checkArcDirections(const Graph& G) {
196    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
197      check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
198      check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
199      check(G.direct(a, G.direction(a)) == a, "Wrong direction");
200    }
201  }
202
203  template <typename Graph>
204  void checkNodeIds(const Graph& G) {
205    typedef typename Graph::Node Node;
206    std::set<int> values;
207    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
208      check(G.nodeFromId(G.id(n)) == n, "Wrong id");
209      check(values.find(G.id(n)) == values.end(), "Wrong id");
210      check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
211      values.insert(G.id(n));
212    }
213    check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id");
214  }
215
216  template <typename Graph>
217  void checkRedNodeIds(const Graph& G) {
218    typedef typename Graph::RedNode RedNode;
219    std::set<int> values;
220    for (typename Graph::RedNodeIt n(G); n != INVALID; ++n) {
221      check(G.red(n), "Wrong partition");
222      check(values.find(G.id(n)) == values.end(), "Wrong id");
223      check(G.id(n) <= G.maxRedId(), "Wrong maximum id");
224      values.insert(G.id(n));
225    }
226    check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
227  }
228
229  template <typename Graph>
230  void checkBlueNodeIds(const Graph& G) {
231    typedef typename Graph::BlueNode BlueNode;
232    std::set<int> values;
233    for (typename Graph::BlueNodeIt n(G); n != INVALID; ++n) {
234      check(G.blue(n), "Wrong partition");
235      check(values.find(G.id(n)) == values.end(), "Wrong id");
236      check(G.id(n) <= G.maxBlueId(), "Wrong maximum id");
237      values.insert(G.id(n));
238    }
239    check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");
240  }
241
242  template <typename Graph>
243  void checkArcIds(const Graph& G) {
244    typedef typename Graph::Arc Arc;
245    std::set<int> values;
246    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
247      check(G.arcFromId(G.id(a)) == a, "Wrong id");
248      check(values.find(G.id(a)) == values.end(), "Wrong id");
249      check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
250      values.insert(G.id(a));
251    }
252    check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
253  }
254
255  template <typename Graph>
256  void checkEdgeIds(const Graph& G) {
257    typedef typename Graph::Edge Edge;
258    std::set<int> values;
259    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
260      check(G.edgeFromId(G.id(e)) == e, "Wrong id");
261      check(values.find(G.id(e)) == values.end(), "Wrong id");
262      check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
263      values.insert(G.id(e));
264    }
265    check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
266  }
267
268  template <typename Graph>
269  void checkGraphNodeMap(const Graph& G) {
270    typedef typename Graph::Node Node;
271    typedef typename Graph::NodeIt NodeIt;
272
273    typedef typename Graph::template NodeMap<int> IntNodeMap;
274    IntNodeMap map(G, 42);
275    for (NodeIt it(G); it != INVALID; ++it) {
276      check(map[it] == 42, "Wrong map constructor.");
277    }
278    int s = 0;
279    for (NodeIt it(G); it != INVALID; ++it) {
280      map[it] = 0;
281      check(map[it] == 0, "Wrong operator[].");
282      map.set(it, s);
283      check(map[it] == s, "Wrong set.");
284      ++s;
285    }
286    s = s * (s - 1) / 2;
287    for (NodeIt it(G); it != INVALID; ++it) {
288      s -= map[it];
289    }
290    check(s == 0, "Wrong sum.");
291
292    // map = constMap<Node>(12);
293    // for (NodeIt it(G); it != INVALID; ++it) {
294    //   check(map[it] == 12, "Wrong operator[].");
295    // }
296  }
297
298  template <typename Graph>
299  void checkGraphRedNodeMap(const Graph& G) {
300    typedef typename Graph::Node Node;
301    typedef typename Graph::RedNodeIt RedNodeIt;
302
303    typedef typename Graph::template RedNodeMap<int> IntRedNodeMap;
304    IntRedNodeMap map(G, 42);
305    for (RedNodeIt it(G); it != INVALID; ++it) {
306      check(map[it] == 42, "Wrong map constructor.");
307    }
308    int s = 0;
309    for (RedNodeIt it(G); it != INVALID; ++it) {
310      map[it] = 0;
311      check(map[it] == 0, "Wrong operator[].");
312      map.set(it, s);
313      check(map[it] == s, "Wrong set.");
314      ++s;
315    }
316    s = s * (s - 1) / 2;
317    for (RedNodeIt it(G); it != INVALID; ++it) {
318      s -= map[it];
319    }
320    check(s == 0, "Wrong sum.");
321
322    // map = constMap<Node>(12);
323    // for (NodeIt it(G); it != INVALID; ++it) {
324    //   check(map[it] == 12, "Wrong operator[].");
325    // }
326  }
327
328  template <typename Graph>
329  void checkGraphBlueNodeMap(const Graph& G) {
330    typedef typename Graph::Node Node;
331    typedef typename Graph::BlueNodeIt BlueNodeIt;
332
333    typedef typename Graph::template BlueNodeMap<int> IntBlueNodeMap;
334    IntBlueNodeMap map(G, 42);
335    for (BlueNodeIt it(G); it != INVALID; ++it) {
336      check(map[it] == 42, "Wrong map constructor.");
337    }
338    int s = 0;
339    for (BlueNodeIt it(G); it != INVALID; ++it) {
340      map[it] = 0;
341      check(map[it] == 0, "Wrong operator[].");
342      map.set(it, s);
343      check(map[it] == s, "Wrong set.");
344      ++s;
345    }
346    s = s * (s - 1) / 2;
347    for (BlueNodeIt it(G); it != INVALID; ++it) {
348      s -= map[it];
349    }
350    check(s == 0, "Wrong sum.");
351
352    // map = constMap<Node>(12);
353    // for (NodeIt it(G); it != INVALID; ++it) {
354    //   check(map[it] == 12, "Wrong operator[].");
355    // }
356  }
357
358  template <typename Graph>
359  void checkGraphArcMap(const Graph& G) {
360    typedef typename Graph::Arc Arc;
361    typedef typename Graph::ArcIt ArcIt;
362
363    typedef typename Graph::template ArcMap<int> IntArcMap;
364    IntArcMap map(G, 42);
365    for (ArcIt it(G); it != INVALID; ++it) {
366      check(map[it] == 42, "Wrong map constructor.");
367    }
368    int s = 0;
369    for (ArcIt it(G); it != INVALID; ++it) {
370      map[it] = 0;
371      check(map[it] == 0, "Wrong operator[].");
372      map.set(it, s);
373      check(map[it] == s, "Wrong set.");
374      ++s;
375    }
376    s = s * (s - 1) / 2;
377    for (ArcIt it(G); it != INVALID; ++it) {
378      s -= map[it];
379    }
380    check(s == 0, "Wrong sum.");
381
382    // map = constMap<Arc>(12);
383    // for (ArcIt it(G); it != INVALID; ++it) {
384    //   check(map[it] == 12, "Wrong operator[].");
385    // }
386  }
387
388  template <typename Graph>
389  void checkGraphEdgeMap(const Graph& G) {
390    typedef typename Graph::Edge Edge;
391    typedef typename Graph::EdgeIt EdgeIt;
392
393    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
394    IntEdgeMap map(G, 42);
395    for (EdgeIt it(G); it != INVALID; ++it) {
396      check(map[it] == 42, "Wrong map constructor.");
397    }
398    int s = 0;
399    for (EdgeIt it(G); it != INVALID; ++it) {
400      map[it] = 0;
401      check(map[it] == 0, "Wrong operator[].");
402      map.set(it, s);
403      check(map[it] == s, "Wrong set.");
404      ++s;
405    }
406    s = s * (s - 1) / 2;
407    for (EdgeIt it(G); it != INVALID; ++it) {
408      s -= map[it];
409    }
410    check(s == 0, "Wrong sum.");
411
412    // map = constMap<Edge>(12);
413    // for (EdgeIt it(G); it != INVALID; ++it) {
414    //   check(map[it] == 12, "Wrong operator[].");
415    // }
416  }
417
418
419} //namespace lemon
420
421#endif
Note: See TracBrowser for help on using the repository browser.