COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/test_tools.h @ 131:3125084667a3

Last change on this file since 131:3125084667a3 was 100:4f754b4cf82b, checked in by Alpar Juttner <alpar@…>, 12 years ago

Bfs/Dfs/Dijkstra? and their deps ported from svn trung -r 3441.

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