COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/test_tools.h @ 1728:eb8bb91ba9e2

Last change on this file since 1728:eb8bb91ba9e2 was 1728:eb8bb91ba9e2, checked in by Balazs Dezso, 18 years ago

Updating tests

File size: 5.0 KB
RevLine 
[906]1/* -*- C++ -*-
[1435]2 * test/test_tools.h - Part of LEMON, a generic C++ optimization library
[906]3 *
[1164]4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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
[921]17#ifndef LEMON_TEST_TEST_TOOLS_H
18#define LEMON_TEST_TEST_TOOLS_H
[574]19
[978]20#include <iostream>
21#include <vector>
22
[1728]23#include <cstdlib>
24#include <ctime>
25
[978]26#include <lemon/invalid.h>
[1728]27#include <lemon/concept_check.h>
[978]28
29using namespace lemon;
30
[574]31//! \ingroup misc
32//! \file
[1200]33//! \brief Some utilities to write test programs.
[574]34
35
[679]36///If \c rc is fail, writes an error message end exit.
[574]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
[679]40///source code in a standard from, which makes it possible to go there
[574]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
[774]47///
48///\todo It should be in \c error.h
[574]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{
[825]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;
[574]71};
72
[721]73
74
[574]75///Adds a Petersen graph to \c G.
76
77///Adds a Petersen graph to \c G.
[937]78///\return The nodes and edges of the generated graph.
[721]79
80template<typename Graph>
[946]81PetStruct<Graph> addPetersen(Graph &G,int num = 5)
[574]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]));
[946]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]));
[574]94  }
95 return n;
96}
97
[1200]98/// \brief Adds to the graph the reverse pair of all edges.
[946]99///
[1200]100/// Adds to the graph the reverse pair of all edges.
[946]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++)
[986]112    G.addEdge(G.target(*p),G.source(*p));
[946]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
[1716]136///Structure returned by \ref addUndirPetersen().
[574]137
[1716]138///Structure returned by \ref addUndirPetersen().
[937]139///
[1716]140template<class Graph> struct UndirPetStruct
[937]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.
[1716]147  std::vector<typename Graph::UndirEdge> incir;
[937]148  ///Vector containing the edges of the outer circle.
[1716]149  std::vector<typename Graph::UndirEdge> outcir;
[937]150  ///Vector containing the chord edges.
[1716]151  std::vector<typename Graph::UndirEdge> chords;
[937]152};
153
[1716]154///Adds a Petersen graph to the undirected \c G.
[937]155
[1716]156///Adds a Petersen graph to the undirected \c G.
[937]157///\return The nodes and edges of the generated graph.
158
159template<typename Graph>
[1716]160UndirPetStruct<Graph> addUndirPetersen(Graph &G,int num=5)
[937]161{
[1716]162  UndirPetStruct<Graph> n;
[937]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}
[574]176
[1728]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
[574]189#endif
Note: See TracBrowser for help on using the repository browser.