COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/test_tools.h @ 1909:2d806130e700

Last change on this file since 1909:2d806130e700 was 1909:2d806130e700, checked in by Mihaly Barasz, 14 years ago

Undir -> U transition

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