COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/test_tools.h @ 2100:6fbe90faf02a

Last change on this file since 2100:6fbe90faf02a was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

File size: 5.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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_TEST_TOOLS_H
20#define LEMON_TEST_TEST_TOOLS_H
21
22#include <iostream>
23#include <vector>
24
25#include <cstdlib>
26#include <ctime>
27
28#include <lemon/concept_check.h>
29#include <lemon/concept/graph.h>
30
31using namespace lemon;
32
33//! \ingroup misc
34//! \file
35//! \brief Some utilities to write test programs.
36
37
38///If \c rc is fail, writes an error message end exit.
39
40///If \c rc is fail, writes an error message end exit.
41///The error message contains the file name and the line number of the
42///source code in a standard from, which makes it possible to go there
43///using good source browsers like e.g. \c emacs.
44///
45///For example
46///\code check(0==1,"This is obviously false.");\endcode will
47///print this (and then exits).
48///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
49///
50///\todo It should be in \c error.h
51#define check(rc, msg) \
52  if(!(rc)) { \
53    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
54    exit(1); \
55  } else { } \
56
57///Structure returned by \ref addPetersen().
58
59///Structure returned by \ref addPetersen().
60///
61template<class Graph> struct PetStruct
62{
63  ///Vector containing the outer nodes.
64  std::vector<typename Graph::Node> outer;
65  ///Vector containing the inner nodes.
66  std::vector<typename Graph::Node> inner;
67  ///Vector containing the edges of the inner circle.
68  std::vector<typename Graph::Edge> incir;
69  ///Vector containing the edges of the outer circle.
70  std::vector<typename Graph::Edge> outcir;
71  ///Vector containing the chord edges.
72  std::vector<typename Graph::Edge> chords;
73};
74
75
76
77///Adds a Petersen graph to \c G.
78
79///Adds a Petersen graph to \c G.
80///\return The nodes and edges of the generated graph.
81
82template<typename Graph>
83PetStruct<Graph> addPetersen(Graph &G,int num = 5)
84{
85  PetStruct<Graph> n;
86
87  for(int i=0;i<num;i++) {
88    n.outer.push_back(G.addNode());
89    n.inner.push_back(G.addNode());
90  }
91
92 for(int i=0;i<num;i++) {
93   n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
94   n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1) % num]));
95   n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2) % num]));
96  }
97 return n;
98}
99
100/// \brief Adds to the graph the reverse pair of all edges.
101///
102/// Adds to the graph the reverse pair of all edges.
103///
104template<class Graph> void bidirGraph(Graph &G)
105{
106  typedef typename Graph::Edge Edge;
107  typedef typename Graph::EdgeIt EdgeIt;
108 
109  std::vector<Edge> ee;
110 
111  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
112
113  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
114    G.addEdge(G.target(*p),G.source(*p));
115}
116
117
118/// \brief Checks the bidirectioned Petersen graph.
119///
120///  Checks the bidirectioned Petersen graph.
121///
122template<class Graph> void checkBidirPetersen(Graph &G, int num = 5)
123{
124  typedef typename Graph::Node Node;
125
126  typedef typename Graph::EdgeIt EdgeIt;
127  typedef typename Graph::NodeIt NodeIt;
128
129  checkGraphNodeList(G, 2 * num);
130  checkGraphEdgeList(G, 6 * num);
131
132  for(NodeIt n(G);n!=INVALID;++n) {
133    checkGraphInEdgeList(G, n, 3);
134    checkGraphOutEdgeList(G, n, 3);
135  } 
136}
137
138///Structure returned by \ref addUPetersen().
139
140///Structure returned by \ref addUPetersen().
141///
142template<class Graph> struct UPetStruct
143{
144  ///Vector containing the outer nodes.
145  std::vector<typename Graph::Node> outer;
146  ///Vector containing the inner nodes.
147  std::vector<typename Graph::Node> inner;
148  ///Vector containing the edges of the inner circle.
149  std::vector<typename Graph::UEdge> incir;
150  ///Vector containing the edges of the outer circle.
151  std::vector<typename Graph::UEdge> outcir;
152  ///Vector containing the chord edges.
153  std::vector<typename Graph::UEdge> chords;
154};
155
156///Adds a Petersen graph to the undirected \c G.
157
158///Adds a Petersen graph to the undirected \c G.
159///\return The nodes and edges of the generated graph.
160
161template<typename Graph>
162UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
163{
164  UPetStruct<Graph> n;
165
166  for(int i=0;i<num;i++) {
167    n.outer.push_back(G.addNode());
168    n.inner.push_back(G.addNode());
169  }
170
171 for(int i=0;i<num;i++) {
172   n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
173   n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
174   n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
175  }
176 return n;
177}
178
179int _urandom_init() {
180  int seed = time(0);
181  srand(seed);
182  return seed;
183}
184
185int urandom(int n) {
186  static int seed = _urandom_init();
187  ignore_unused_variable_warning(seed);
188  return (int)(rand() / (1.0 + RAND_MAX) * n);
189}
190
191#endif
Note: See TracBrowser for help on using the repository browser.