COIN-OR::LEMON - Graph Library

source: lemon-main/test/graph_test.h @ 1024:b84e68af8248

Last change on this file since 1024:b84e68af8248 was 1019:4c89e925cfe2, checked in by Balazs Dezso <deba@…>, 14 years ago

SmartBpGraph? implementation (#69)

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