00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_TEST_TEST_TOOLS_H
00020 #define LEMON_TEST_TEST_TOOLS_H
00021
00022 #include <iostream>
00023 #include <vector>
00024
00025 #include <cstdlib>
00026 #include <ctime>
00027
00028 #include <lemon/invalid.h>
00029 #include <lemon/concept_check.h>
00030
00031 using namespace lemon;
00032
00036
00037
00039
00051 #define check(rc, msg) \
00052 if(!(rc)) { \
00053 std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
00054 exit(1); \
00055 } else { } \
00056
00057
00058
00061 template<class Graph> struct PetStruct
00062 {
00064 std::vector<typename Graph::Node> outer;
00066 std::vector<typename Graph::Node> inner;
00068 std::vector<typename Graph::Edge> incir;
00070 std::vector<typename Graph::Edge> outcir;
00072 std::vector<typename Graph::Edge> chords;
00073 };
00074
00075
00076
00078
00081
00082 template<typename Graph>
00083 PetStruct<Graph> addPetersen(Graph &G,int num = 5)
00084 {
00085 PetStruct<Graph> n;
00086
00087 for(int i=0;i<num;i++) {
00088 n.outer.push_back(G.addNode());
00089 n.inner.push_back(G.addNode());
00090 }
00091
00092 for(int i=0;i<num;i++) {
00093 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
00094 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1) % num]));
00095 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2) % num]));
00096 }
00097 return n;
00098 }
00099
00104 template<class Graph> void bidirGraph(Graph &G)
00105 {
00106 typedef typename Graph::Edge Edge;
00107 typedef typename Graph::EdgeIt EdgeIt;
00108
00109 std::vector<Edge> ee;
00110
00111 for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
00112
00113 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
00114 G.addEdge(G.target(*p),G.source(*p));
00115 }
00116
00117
00122 template<class Graph> void checkBidirPetersen(Graph &G, int num = 5)
00123 {
00124 typedef typename Graph::Node Node;
00125
00126 typedef typename Graph::EdgeIt EdgeIt;
00127 typedef typename Graph::NodeIt NodeIt;
00128
00129 checkGraphNodeList(G, 2 * num);
00130 checkGraphEdgeList(G, 6 * num);
00131
00132 for(NodeIt n(G);n!=INVALID;++n) {
00133 checkGraphInEdgeList(G, n, 3);
00134 checkGraphOutEdgeList(G, n, 3);
00135 }
00136 }
00137
00139
00142 template<class Graph> struct UPetStruct
00143 {
00145 std::vector<typename Graph::Node> outer;
00147 std::vector<typename Graph::Node> inner;
00149 std::vector<typename Graph::UEdge> incir;
00151 std::vector<typename Graph::UEdge> outcir;
00153 std::vector<typename Graph::UEdge> chords;
00154 };
00155
00157
00160
00161 template<typename Graph>
00162 UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
00163 {
00164 UPetStruct<Graph> n;
00165
00166 for(int i=0;i<num;i++) {
00167 n.outer.push_back(G.addNode());
00168 n.inner.push_back(G.addNode());
00169 }
00170
00171 for(int i=0;i<num;i++) {
00172 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
00173 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
00174 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
00175 }
00176 return n;
00177 }
00178
00179 int _urandom_init() {
00180 int seed = time(0);
00181 srand(seed);
00182 return seed;
00183 }
00184
00185 int urandom(int n) {
00186 static int seed = _urandom_init();
00187 ignore_unused_variable_warning(seed);
00188 return (int)(rand() / (1.0 + RAND_MAX) * n);
00189 }
00190
00191 #endif