COIN-OR::LEMON - Graph Library

source: lemon-main/test/graph_test.h @ 1163:db1d342a1087

Last change on this file since 1163:db1d342a1087 was 1131:4add05447ca0, checked in by Alpar Juttner <alpar@…>, 10 years ago

Tests and bugfixes for the STL style iterators (#325)

File size: 16.8 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-2013
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#ifdef LEMON_CXX11
43    {
44      typename Graph::NodeIt n(G);
45      for(auto u: G.nodes())
46        {
47          check(n==u,"Wrong STL Node iterator.");
48          ++n;
49        }
50      check(n==INVALID,"Wrong STL Node iterator.");
51    }
52    {
53      typename Graph::NodeIt n(G);
54      for(typename Graph::Node u: G.nodes())
55        {
56          check(n==u,"Wrong STL Node iterator.");
57          ++n;
58        }
59      check(n==INVALID,"Wrong STL Node iterator.");
60    }
61#endif
62  }
63
64  template<class Graph>
65  void checkGraphRedNodeList(const Graph &G, int cnt)
66  {
67    typename Graph::RedNodeIt n(G);
68    for(int i=0;i<cnt;i++) {
69      check(n!=INVALID,"Wrong red Node list linking.");
70      check(G.red(n),"Wrong node set check.");
71      check(!G.blue(n),"Wrong node set check.");
72      typename Graph::Node nn = n;
73      check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion.");
74      check(G.asRedNode(nn) == n,"Wrong node conversion.");
75      check(G.asBlueNode(nn) == INVALID,"Wrong node conversion.");
76      ++n;
77    }
78    check(n==INVALID,"Wrong red Node list linking.");
79    check(countRedNodes(G)==cnt,"Wrong red Node number.");
80#ifdef LEMON_CXX11
81    {
82      typename Graph::RedNodeIt n(G);
83      for(auto u: G.redNodes())
84        {
85          check(n==u,"Wrong STL RedNode iterator.");
86          ++n;
87        }
88      check(n==INVALID,"Wrong STL RedNode iterator.");
89    }
90    {
91      typename Graph::RedNodeIt n(G);
92      for(typename Graph::RedNode u: G.redNodes())
93        {
94          check(n==u,"Wrong STL RedNode iterator.");
95          ++n;
96        }
97      check(n==INVALID,"Wrong STL RedNode iterator.");
98    }
99#endif
100  }
101
102  template<class Graph>
103  void checkGraphBlueNodeList(const Graph &G, int cnt)
104  {
105    typename Graph::BlueNodeIt n(G);
106    for(int i=0;i<cnt;i++) {
107      check(n!=INVALID,"Wrong blue Node list linking.");
108      check(G.blue(n),"Wrong node set check.");
109      check(!G.red(n),"Wrong node set check.");
110      typename Graph::Node nn = n;
111      check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion.");
112      check(G.asBlueNode(nn) == n,"Wrong node conversion.");
113      check(G.asRedNode(nn) == INVALID,"Wrong node conversion.");
114      ++n;
115    }
116    check(n==INVALID,"Wrong blue Node list linking.");
117    check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
118#ifdef LEMON_CXX11
119    {
120      typename Graph::BlueNodeIt n(G);
121      for(auto u: G.blueNodes())
122        {
123          check(n==u,"Wrong STL BlueNode iterator.");
124          ++n;
125        }
126      check(n==INVALID,"Wrong STL BlueNode iterator.");
127    }
128    {
129      typename Graph::BlueNodeIt n(G);
130      for(typename Graph::BlueNode u: G.blueNodes())
131        {
132          check(n==u,"Wrong STL BlueNode iterator.");
133          ++n;
134        }
135      check(n==INVALID,"Wrong STL BlueNode iterator.");
136    }
137#endif
138
139  }
140
141  template<class Graph>
142  void checkGraphArcList(const Graph &G, int cnt)
143  {
144    typename Graph::ArcIt e(G);
145    for(int i=0;i<cnt;i++) {
146      check(e!=INVALID,"Wrong Arc list linking.");
147      check(G.oppositeNode(G.source(e), e) == G.target(e),
148            "Wrong opposite node");
149      check(G.oppositeNode(G.target(e), e) == G.source(e),
150            "Wrong opposite node");
151      ++e;
152    }
153    check(e==INVALID,"Wrong Arc list linking.");
154    check(countArcs(G)==cnt,"Wrong Arc number.");
155#ifdef LEMON_CXX11
156    {
157      typename Graph::ArcIt a(G);
158      for(auto e: G.arcs())
159        {
160          check(a==e,"Wrong STL Arc iterator.");
161          ++a;
162        }
163      check(a==INVALID,"Wrong STL Arc iterator.");
164    }
165    {
166      typename Graph::ArcIt a(G);
167      for(typename Graph::Arc e: G.arcs())
168        {
169          check(a==e,"Wrong STL Arc iterator.");
170          ++a;
171        }
172      check(a==INVALID,"Wrong STL Arc iterator.");
173    }
174#endif
175
176  }
177
178  template<class Graph>
179  void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
180  {
181    typename Graph::OutArcIt e(G,n);
182    for(int i=0;i<cnt;i++) {
183      check(e!=INVALID,"Wrong OutArc list linking.");
184      check(n==G.source(e),"Wrong OutArc list linking.");
185      check(n==G.baseNode(e),"Wrong OutArc list linking.");
186      check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
187      ++e;
188    }
189    check(e==INVALID,"Wrong OutArc list linking.");
190    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
191#ifdef LEMON_CXX11
192    {
193      typename Graph::OutArcIt a(G,n);
194      for(auto e: G.outArcs(n))
195        {
196          check(a==e,"Wrong STL OutArc iterator.");
197          ++a;
198        }
199      check(a==INVALID,"Wrong STL OutArc iterator.");
200    }
201    {
202      typename Graph::OutArcIt a(G,n);
203      for(typename Graph::Arc e: G.outArcs(n))
204        {
205          check(a==e,"Wrong STL OutArc iterator.");
206          ++a;
207        }
208      check(a==INVALID,"Wrong STL OutArc iterator.");
209    }
210#endif
211
212  }
213
214  template<class Graph>
215  void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
216  {
217    typename Graph::InArcIt e(G,n);
218    for(int i=0;i<cnt;i++) {
219      check(e!=INVALID,"Wrong InArc list linking.");
220      check(n==G.target(e),"Wrong InArc list linking.");
221      check(n==G.baseNode(e),"Wrong OutArc list linking.");
222      check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
223      ++e;
224    }
225    check(e==INVALID,"Wrong InArc list linking.");
226    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
227#ifdef LEMON_CXX11
228    {
229      typename Graph::InArcIt a(G,n);
230      for(auto e: G.inArcs(n))
231        {
232          check(a==e,"Wrong STL InArc iterator.");
233          ++a;
234        }
235      check(a==INVALID,"Wrong STL InArc iterator.");
236    }
237    {
238      typename Graph::InArcIt a(G,n);
239      for(typename Graph::Arc e: G.inArcs(n))
240        {
241          check(a==e,"Wrong STL InArc iterator.");
242          ++a;
243        }
244      check(a==INVALID,"Wrong STL InArc iterator.");
245    }
246#endif
247  }
248
249  template<class Graph>
250  void checkGraphEdgeList(const Graph &G, int cnt)
251  {
252    typename Graph::EdgeIt e(G);
253    for(int i=0;i<cnt;i++) {
254      check(e!=INVALID,"Wrong Edge list linking.");
255      check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
256      check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
257      ++e;
258    }
259    check(e==INVALID,"Wrong Edge list linking.");
260    check(countEdges(G)==cnt,"Wrong Edge number.");
261#ifdef LEMON_CXX11
262    {
263      typename Graph::EdgeIt a(G);
264      for(auto e: G.edges())
265        {
266          check(a==e,"Wrong STL Edge iterator.");
267          ++a;
268        }
269      check(a==INVALID,"Wrong STL Edge iterator.");
270    }
271    {
272      typename Graph::EdgeIt a(G);
273      for(typename Graph::Edge e: G.edges())
274        {
275          check(a==e,"Wrong STL Edge iterator.");
276          ++a;
277        }
278      check(a==INVALID,"Wrong STL Edge iterator.");
279    }
280#endif
281
282  }
283
284  template<class Graph>
285  void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
286  {
287    typename Graph::IncEdgeIt e(G,n);
288    for(int i=0;i<cnt;i++) {
289      check(e!=INVALID,"Wrong IncEdge list linking.");
290      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
291      check(n==G.baseNode(e),"Wrong OutArc list linking.");
292      check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
293            "Wrong OutArc list linking.");
294      ++e;
295    }
296    check(e==INVALID,"Wrong IncEdge list linking.");
297    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
298#ifdef LEMON_CXX11
299    {
300      typename Graph::IncEdgeIt a(G,n);
301      for(auto e: G.incEdges(n))
302        {
303          check(a==e,"Wrong STL IncEdge iterator.");
304          ++a;
305        }
306      check(a==INVALID,"Wrong STL IncEdge iterator.");
307    }
308    {
309      typename Graph::IncEdgeIt a(G,n);
310      for(typename Graph::Edge e: G.incEdges(n))
311        {
312          check(a==e,"Wrong STL IncEdge iterator.");
313          ++a;
314        }
315      check(a==INVALID,"Wrong STL IncEdge iterator.");
316    }
317#endif
318
319  }
320
321  template <class Graph>
322  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
323                                 int cnt)
324  {
325    checkGraphIncEdgeList(G, n, cnt);
326    checkGraphOutArcList(G, n, cnt);
327    checkGraphInArcList(G, n, cnt);
328  }
329
330  template <class Graph>
331  void checkGraphConArcList(const Graph &G, int cnt) {
332    int i = 0;
333    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
334      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
335        for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
336          check(G.source(a) == u, "Wrong iterator.");
337          check(G.target(a) == v, "Wrong iterator.");
338          ++i;
339        }
340      }
341    }
342    check(cnt == i, "Wrong iterator.");
343  }
344
345  template <class Graph>
346  void checkGraphConEdgeList(const Graph &G, int cnt) {
347    int i = 0;
348    for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
349      for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
350        for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
351          check((G.u(e) == u && G.v(e) == v) ||
352                (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
353          i += u == v ? 2 : 1;
354        }
355      }
356    }
357    check(2 * cnt == i, "Wrong iterator.");
358  }
359
360  template <typename Graph>
361  void checkArcDirections(const Graph& G) {
362    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
363      check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
364      check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
365      check(G.direct(a, G.direction(a)) == a, "Wrong direction");
366    }
367  }
368
369  template <typename Graph>
370  void checkNodeIds(const Graph& G) {
371    typedef typename Graph::Node Node;
372    std::set<int> values;
373    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
374      check(G.nodeFromId(G.id(n)) == n, "Wrong id");
375      check(values.find(G.id(n)) == values.end(), "Wrong id");
376      check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
377      values.insert(G.id(n));
378    }
379    check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id");
380  }
381
382  template <typename Graph>
383  void checkRedNodeIds(const Graph& G) {
384    typedef typename Graph::RedNode RedNode;
385    std::set<int> values;
386    for (typename Graph::RedNodeIt n(G); n != INVALID; ++n) {
387      check(G.red(n), "Wrong partition");
388      check(values.find(G.id(n)) == values.end(), "Wrong id");
389      check(G.id(n) <= G.maxRedId(), "Wrong maximum id");
390      values.insert(G.id(n));
391    }
392    check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
393  }
394
395  template <typename Graph>
396  void checkBlueNodeIds(const Graph& G) {
397    typedef typename Graph::BlueNode BlueNode;
398    std::set<int> values;
399    for (typename Graph::BlueNodeIt n(G); n != INVALID; ++n) {
400      check(G.blue(n), "Wrong partition");
401      check(values.find(G.id(n)) == values.end(), "Wrong id");
402      check(G.id(n) <= G.maxBlueId(), "Wrong maximum id");
403      values.insert(G.id(n));
404    }
405    check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");
406  }
407
408  template <typename Graph>
409  void checkArcIds(const Graph& G) {
410    typedef typename Graph::Arc Arc;
411    std::set<int> values;
412    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
413      check(G.arcFromId(G.id(a)) == a, "Wrong id");
414      check(values.find(G.id(a)) == values.end(), "Wrong id");
415      check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
416      values.insert(G.id(a));
417    }
418    check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
419  }
420
421  template <typename Graph>
422  void checkEdgeIds(const Graph& G) {
423    typedef typename Graph::Edge Edge;
424    std::set<int> values;
425    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
426      check(G.edgeFromId(G.id(e)) == e, "Wrong id");
427      check(values.find(G.id(e)) == values.end(), "Wrong id");
428      check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
429      values.insert(G.id(e));
430    }
431    check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
432  }
433
434  template <typename Graph>
435  void checkGraphNodeMap(const Graph& G) {
436    typedef typename Graph::Node Node;
437    typedef typename Graph::NodeIt NodeIt;
438
439    typedef typename Graph::template NodeMap<int> IntNodeMap;
440    IntNodeMap map(G, 42);
441    for (NodeIt it(G); it != INVALID; ++it) {
442      check(map[it] == 42, "Wrong map constructor.");
443    }
444    int s = 0;
445    for (NodeIt it(G); it != INVALID; ++it) {
446      map[it] = 0;
447      check(map[it] == 0, "Wrong operator[].");
448      map.set(it, s);
449      check(map[it] == s, "Wrong set.");
450      ++s;
451    }
452    s = s * (s - 1) / 2;
453    for (NodeIt it(G); it != INVALID; ++it) {
454      s -= map[it];
455    }
456    check(s == 0, "Wrong sum.");
457
458    // map = constMap<Node>(12);
459    // for (NodeIt it(G); it != INVALID; ++it) {
460    //   check(map[it] == 12, "Wrong operator[].");
461    // }
462  }
463
464  template <typename Graph>
465  void checkGraphRedNodeMap(const Graph& G) {
466    typedef typename Graph::Node Node;
467    typedef typename Graph::RedNodeIt RedNodeIt;
468
469    typedef typename Graph::template RedNodeMap<int> IntRedNodeMap;
470    IntRedNodeMap map(G, 42);
471    for (RedNodeIt it(G); it != INVALID; ++it) {
472      check(map[it] == 42, "Wrong map constructor.");
473    }
474    int s = 0;
475    for (RedNodeIt it(G); it != INVALID; ++it) {
476      map[it] = 0;
477      check(map[it] == 0, "Wrong operator[].");
478      map.set(it, s);
479      check(map[it] == s, "Wrong set.");
480      ++s;
481    }
482    s = s * (s - 1) / 2;
483    for (RedNodeIt it(G); it != INVALID; ++it) {
484      s -= map[it];
485    }
486    check(s == 0, "Wrong sum.");
487
488    // map = constMap<Node>(12);
489    // for (NodeIt it(G); it != INVALID; ++it) {
490    //   check(map[it] == 12, "Wrong operator[].");
491    // }
492  }
493
494  template <typename Graph>
495  void checkGraphBlueNodeMap(const Graph& G) {
496    typedef typename Graph::Node Node;
497    typedef typename Graph::BlueNodeIt BlueNodeIt;
498
499    typedef typename Graph::template BlueNodeMap<int> IntBlueNodeMap;
500    IntBlueNodeMap map(G, 42);
501    for (BlueNodeIt it(G); it != INVALID; ++it) {
502      check(map[it] == 42, "Wrong map constructor.");
503    }
504    int s = 0;
505    for (BlueNodeIt it(G); it != INVALID; ++it) {
506      map[it] = 0;
507      check(map[it] == 0, "Wrong operator[].");
508      map.set(it, s);
509      check(map[it] == s, "Wrong set.");
510      ++s;
511    }
512    s = s * (s - 1) / 2;
513    for (BlueNodeIt it(G); it != INVALID; ++it) {
514      s -= map[it];
515    }
516    check(s == 0, "Wrong sum.");
517
518    // map = constMap<Node>(12);
519    // for (NodeIt it(G); it != INVALID; ++it) {
520    //   check(map[it] == 12, "Wrong operator[].");
521    // }
522  }
523
524  template <typename Graph>
525  void checkGraphArcMap(const Graph& G) {
526    typedef typename Graph::Arc Arc;
527    typedef typename Graph::ArcIt ArcIt;
528
529    typedef typename Graph::template ArcMap<int> IntArcMap;
530    IntArcMap map(G, 42);
531    for (ArcIt it(G); it != INVALID; ++it) {
532      check(map[it] == 42, "Wrong map constructor.");
533    }
534    int s = 0;
535    for (ArcIt it(G); it != INVALID; ++it) {
536      map[it] = 0;
537      check(map[it] == 0, "Wrong operator[].");
538      map.set(it, s);
539      check(map[it] == s, "Wrong set.");
540      ++s;
541    }
542    s = s * (s - 1) / 2;
543    for (ArcIt it(G); it != INVALID; ++it) {
544      s -= map[it];
545    }
546    check(s == 0, "Wrong sum.");
547
548    // map = constMap<Arc>(12);
549    // for (ArcIt it(G); it != INVALID; ++it) {
550    //   check(map[it] == 12, "Wrong operator[].");
551    // }
552  }
553
554  template <typename Graph>
555  void checkGraphEdgeMap(const Graph& G) {
556    typedef typename Graph::Edge Edge;
557    typedef typename Graph::EdgeIt EdgeIt;
558
559    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
560    IntEdgeMap map(G, 42);
561    for (EdgeIt it(G); it != INVALID; ++it) {
562      check(map[it] == 42, "Wrong map constructor.");
563    }
564    int s = 0;
565    for (EdgeIt it(G); it != INVALID; ++it) {
566      map[it] = 0;
567      check(map[it] == 0, "Wrong operator[].");
568      map.set(it, s);
569      check(map[it] == s, "Wrong set.");
570      ++s;
571    }
572    s = s * (s - 1) / 2;
573    for (EdgeIt it(G); it != INVALID; ++it) {
574      s -= map[it];
575    }
576    check(s == 0, "Wrong sum.");
577
578    // map = constMap<Edge>(12);
579    // for (EdgeIt it(G); it != INVALID; ++it) {
580    //   check(map[it] == 12, "Wrong operator[].");
581    // }
582  }
583
584
585} //namespace lemon
586
587#endif
Note: See TracBrowser for help on using the repository browser.