The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_TEST_TEST_TOOLS_H
20 #define LEMON_TEST_TEST_TOOLS_H
28 #include <lemon/invalid.h>
29 #include <lemon/concept_check.h>
31 using namespace lemon;
35 //! \brief Some utilities to write test programs.
38 ///If \c rc is fail, writes an error message end exit.
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.
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
50 ///\todo It should be in \c error.h
51 #define check(rc, msg) \
53 std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
57 ///Structure returned by \ref addPetersen().
59 ///Structure returned by \ref addPetersen().
61 template<class Graph> struct PetStruct
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;
77 ///Adds a Petersen graph to \c G.
79 ///Adds a Petersen graph to \c G.
80 ///\return The nodes and edges of the generated graph.
82 template<typename Graph>
83 PetStruct<Graph> addPetersen(Graph &G,int num = 5)
87 for(int i=0;i<num;i++) {
88 n.outer.push_back(G.addNode());
89 n.inner.push_back(G.addNode());
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]));
100 /// \brief Adds to the graph the reverse pair of all edges.
102 /// Adds to the graph the reverse pair of all edges.
104 template<class Graph> void bidirGraph(Graph &G)
106 typedef typename Graph::Edge Edge;
107 typedef typename Graph::EdgeIt EdgeIt;
109 std::vector<Edge> ee;
111 for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
113 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
114 G.addEdge(G.target(*p),G.source(*p));
118 /// \brief Checks the bidirectioned Petersen graph.
120 /// Checks the bidirectioned Petersen graph.
122 template<class Graph> void checkBidirPetersen(Graph &G, int num = 5)
124 typedef typename Graph::Node Node;
126 typedef typename Graph::EdgeIt EdgeIt;
127 typedef typename Graph::NodeIt NodeIt;
129 checkGraphNodeList(G, 2 * num);
130 checkGraphEdgeList(G, 6 * num);
132 for(NodeIt n(G);n!=INVALID;++n) {
133 checkGraphInEdgeList(G, n, 3);
134 checkGraphOutEdgeList(G, n, 3);
138 ///Structure returned by \ref addUPetersen().
140 ///Structure returned by \ref addUPetersen().
142 template<class Graph> struct UPetStruct
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;
156 ///Adds a Petersen graph to the undirected \c G.
158 ///Adds a Petersen graph to the undirected \c G.
159 ///\return The nodes and edges of the generated graph.
161 template<typename Graph>
162 UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
166 for(int i=0;i<num;i++) {
167 n.outer.push_back(G.addNode());
168 n.inner.push_back(G.addNode());
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]));
179 int _urandom_init() {
186 static int seed = _urandom_init();
187 ignore_unused_variable_warning(seed);
188 return (int)(rand() / (1.0 + RAND_MAX) * n);