1 // Copyright (C) 2006-2009 Dmitry Bufistov and Andrey Parfenov
2
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 #include <sstream>
8
9 #include <boost/graph/adjacency_list.hpp>
10 #include <boost/graph/adjacency_matrix.hpp>
11 #include <boost/graph/graphviz.hpp>
12 #include <boost/graph/iteration_macros.hpp>
13 #include <boost/graph/graph_utility.hpp>
14 #include <boost/graph/property_iter_range.hpp>
15 #include <boost/graph/howard_cycle_ratio.hpp>
16
17 #include <boost/test/minimal.hpp>
18
19 /**
20 * @author Dmitry Bufistov
21 * @author Andrey Parfenov
22 */
23
24 /*!
25 * The graph has two equal cycles with ratio 2/3
26 */
27 static const char test_graph1[] = "digraph G {\
28 edge [w1=1, w2=1];\
29 1->2\
30 2->3 [w1=0]\
31 3->4\
32 4->2\
33 1->5\
34 5->6\
35 6->7 [w1=0]\
36 7->5 \
37 }";
38
39 /*!
40 * The graph has no cycles
41 */
42 static const std::string test_graph2 = "digraph G {edge [w1=1]; 1->3 [w2=1]; 1->2 [w2=2]; 1->4 [w2=7]; }";
43
44 /*!
45 * Example from the paper "Nunerical computation of spectral elements"
46 * Maximum cycle ratio is 5.5
47 */
48 static const char test_graph3[] = "\
49 digraph article {\
50 edge [w2 =2];\
51 1->1 [w1 = 1];\
52 1->2 [w1 = 2];\
53 1->4 [w1 = 7];\
54 2->2 [w1 = 3];\
55 2->3 [w1 = 5];\
56 3->2 [w1 = 4];\
57 3->4 [w1 = 3];\
58 4->2 [w1 = 2];\
59 4->3 [w1 = 8];\
60 }";
61
62 /*!
63 * Simple multigraph.
64 * Maximum cycle ratio is 2.5, minimum 0.5
65 */
66 static const char test_graph4[] = "digraph G {\
67 edge [w2=1];\
68 a->b [w1=1];\
69 b->a [w1=0];\
70 a->b [w1=2];\
71 b->a [w1=3];\
72 }";
73
74 /*!
75 * The big graph with two equal cycles
76 */
77 static const char test_graph5[]= "digraph G { edge [w2=1, w1=1]; n94->n8; n95->n8; n93->n8; n93->n9; n42->n9; n23->n13;\
78 n29->n13; n95->n14; n37->n14; n95->n19; n37->n19; n94->n23; n60->n26; n76->n26; n94->n29; n9->n33 [w1=0]; n80->n33;\
79 n14->n34 [w1=0];n19->n34; n94->n37; n94->n42; n95->n42; n8->n60; n26->n60; n26->n76; n106->n76; n93->n80; n42->n80;\
80 n33->n93; n60->n93; n13->n94; n60->n94; n34->n95; n60->n95; n94->n106; n95->n106; n93->n106;\
81 }";
82
83 /*!
84 * Random graph generated by hands.
85 * Maximum cycle ratio is 3.58, minimum is 0.294118
86 */
87 static const char test_graph6[]= "digraph test_graph6 {\
88 16;\
89 17;\
90 \
91 1->2 [w1=1, w2=0.1];\
92 2->3 [w1 = 2, w2=3.6];\
93 3->4 [w1=7, w2=8];\
94 4->5 [w1=3.1,w2=0.8];\
95 4->5 [w1 = 4.2, w2=0.6];\
96 4->5 [w1 = 5.3, w2=0.4];\
97 5->6 [w1=-10, w2 = 34.75]\
98 6->1 [w1=100, w2 = 20]\
99 \
100 1->7 [w1=10, w2 = 20];\
101 7->8 [w1=3.75, w2 = 1.25];\
102 7->8 [w1=30, w2 = 22.2];\
103 8->9 [w1=10, w2 = 20];\
104 9->10 [w1=-2.1, w2 = 30]\
105 10->6 [w1=10, w2 = 20]\
106 \
107 11->12 [w1 = 5, w2=0.45];\
108 12->13 [w1 = 4, w2=0.2];\
109 13->14 [w1 = 3, w2=15.75];\
110 14->11 [w1 = -2.5, w2=0.6];\
111 11->10 [w1 = -8, w2=0.9];\
112 11->10 [w1 = -15, w2=2.9];\
113 \
114 18 -> 19 [w1=18, w2=6];\
115 18 -> 20 [w1=16.3, w2=8.2];\
116 18 -> 21 [w1=-3, w2=15];\
117 18 -> 18 [w1=2, w2=1];\
118 19 -> 18 [w1=0.06, w2=0.01];\
119 19 -> 19 [w1=1, w2=1.2];\
120 19 -> 20 [w1=5, w2=2];\
121 19 -> 21 [w1=3, w2=0.1];\
122 20 -> 18 [w1=4, w2=0.2];\
123 20 -> 19 [w1=11, w2=21];\
124 20 -> 20 [w1=6, w2=5];\
125 20 -> 21 [w1=7, w2=1];\
126 21 -> 18 [w1=8, w2=2];\
127 21 -> 19 [w1=12, w2=6];\
128 21 -> 20 [w1=7.5, w2=4.3];\
129 21 -> 21 [w1=1.25, w2=2.15];\
130 }";
131
132 using namespace boost;
133 typedef property<vertex_index_t, int, property<boost::vertex_name_t, std::string> > vertex_props_t;
134 template <typename TW1, typename TW2> struct Graph
135 {
136 typedef typename boost::property<
137 boost::edge_weight_t, TW1,
138 typename boost::property<
139 boost::edge_weight2_t, TW2, property<boost::edge_index_t, int>
140 >
141 > edge_props_t;
142 typedef typename boost::adjacency_list<
143 boost::listS, boost::listS, boost::directedS, vertex_props_t,
144 edge_props_t>
145 type;
146 };
147 typedef Graph<int, int>::type diGraphInt;
148 typedef Graph<double, double>::type diGraphReal;
149
150 template <typename TW1, typename TW2>
151 struct CEdgeProps
152 {
CEdgePropsCEdgeProps153 CEdgeProps(TW1 w1 = 1, TW2 w2 = 2) :
154 m_w1(w1), m_w2(w2), m_edge_index((std::numeric_limits<int>::max)())
155 {}
156 TW1 m_w1;
157 TW2 m_w2;
158 int m_edge_index;
159 };
160 typedef adjacency_matrix<directedS, no_property, CEdgeProps<int, int> > GraphMInt;
161
162 ///Create "tokens_map" for reading graph properties from .dot file
163 template <typename TG>
make_dynamic_properties(TG & g,dynamic_properties & p)164 void make_dynamic_properties(TG &g, dynamic_properties &p)
165 {
166 p.property("node_id", get(vertex_name, g));
167 p.property("label", get(edge_weight, g));
168 p.property("w1", get(edge_weight, g));
169 p.property("w2", get(edge_weight2, g));
170 }
171
172 template <typename TG>
read_data1(std::istream & is,TG & g)173 void read_data1(std::istream &is, TG &g)
174 {
175 dynamic_properties p;
176 make_dynamic_properties(g, p);
177 read_graphviz(is, g, p);
178 std::cout << "Number of vertices: " << num_vertices(g) << std::endl;
179 std::cout << "Number of edges: " << num_edges(g) << std::endl;
180 int i = 0;
181 BGL_FORALL_VERTICES_T(vd, g, TG)
182 {
183 put(vertex_index, g, vd, i++);
184 }
185 i=0;
186 BGL_FORALL_EDGES_T(ed, g, TG)
187 {
188 put(edge_index, g, ed, i++);
189 }
190 }
191
192 template <typename TG>
read_data(const char * file,TG & g)193 void read_data(const char *file, TG &g)
194 {
195 std::cout << "Reading data from file: " << file << std::endl;
196 std::ifstream ifs(file);
197 BOOST_REQUIRE(ifs.good());
198 read_data1(ifs, g);
199 }
200
201 struct my_float : boost::mcr_float<>
202 {
infinitymy_float203 static double infinity()
204 {
205 return 1000;
206 }
207 };
208
209 struct my_float2 : boost::mcr_float<>
210 {
infinitymy_float2211 static double infinity() { return 2; }
212 };
213
test_main(int argc,char * argv[])214 int test_main(int argc, char* argv[])
215 {
216 assert (argc >= 2);
217 using std::endl; using std::cout;
218 const double epsilon = 0.005;
219 double min_cr, max_cr; ///Minimum and maximum cycle ratio
220 typedef std::vector<graph_traits<diGraphInt>::edge_descriptor> ccInt_t;
221 typedef std::vector<graph_traits<diGraphReal>::edge_descriptor> ccReal_t;
222 ccInt_t cc; ///critical cycle
223
224 diGraphInt tg;
225 property_map<diGraphInt, vertex_index_t>::type vim = get(vertex_index, tg);
226 property_map<diGraphInt, edge_weight_t>::type ew1m = get(edge_weight, tg);
227 property_map<diGraphInt, edge_weight2_t>::type ew2m = get(edge_weight2, tg);
228
229
230
231 {
232 std::istringstream iss(test_graph1);
233 assert(iss.good());
234 read_data1(iss, tg);
235 max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
236 cout << "Maximum cycle ratio is " << max_cr << endl;
237 BOOST_CHECK(std::abs( max_cr - 0.666666666) < epsilon );
238 tg.clear();
239 }
240
241 {
242 std::istringstream iss(test_graph2);
243 read_data1(iss, tg);
244 // TODO: This is causing a failuire, but I'm not really sure what it's doing per se.
245 // Commented out for now.
246 // BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m) + (std::numeric_limits<double>::max)()) < epsilon );
247 BOOST_CHECK(std::abs(boost::maximum_cycle_ratio(tg, vim, ew1m, ew2m,
248 static_cast<ccInt_t*>(0), my_float()) + 1000) < epsilon );
249 tg.clear();
250 }
251
252 {
253 std::istringstream iss(test_graph3);
254 diGraphInt tgi;
255 read_data1(iss, tgi);
256 double max_cr = maximum_cycle_ratio(tgi, vim, ew1m, ew2m,
257 static_cast<ccInt_t*>(0));
258 cout << "Maximum cycle ratio is " << max_cr << endl;
259 BOOST_CHECK(std::abs( max_cr - 2.75) < epsilon );
260 double maxmc = maximum_cycle_mean(tgi, vim, ew1m, get(edge_index, tgi));
261 cout << "Maximum cycle mean is " << maxmc << endl;
262 BOOST_CHECK(std::abs( maxmc - 5.5) < epsilon );
263 tg.clear();
264 }
265
266 {
267 std::istringstream iss(test_graph4);
268 read_data1(iss, tg);
269 max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
270 cout << "Maximum cycle ratio is " << max_cr << endl;
271 BOOST_CHECK(std::abs( max_cr - 2.5) < epsilon );
272 min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m);
273 cout << "Minimum cycle ratio is " << min_cr << endl;
274 BOOST_CHECK(std::abs( min_cr - 0.5) < epsilon );
275 tg.clear();
276 }
277
278 {
279 std::istringstream iss(test_graph5);
280 read_data1(iss, tg);
281 min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, &cc, my_float());
282 BOOST_CHECK(std::abs( min_cr - 0.666666666) < epsilon );
283 cout << "Minimum cycle ratio is " << min_cr << endl;
284 cout << "Critical cycle is:\n";
285 for (ccInt_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
286 {
287 cout << "(" << get(vertex_name, tg, source(*itr, tg)) <<
288 "," << get(vertex_name, tg, target(*itr, tg)) << ") ";
289 }
290 cout << endl;
291 tg.clear();
292 }
293
294 {
295 read_data(argv[1], tg);
296 min_cr = boost::minimum_cycle_ratio(tg, vim, ew1m, ew2m, &cc, my_float2());
297 cout << "Minimum cycle ratio is " << min_cr << endl;
298 BOOST_CHECK(std::abs(min_cr - 0.33333333333) < epsilon );
299 cout << "Critical cycle is:" << endl;
300 for (ccInt_t::iterator it = cc.begin(); it != cc.end(); ++it)
301 {
302 cout << "(" << get(vertex_name, tg, source(*it, tg)) << "," <<
303 get(vertex_name, tg, target(*it, tg)) << ") ";
304 }
305 cout << endl;
306 tg.clear();
307 }
308
309 {
310 diGraphReal tgr;
311 ccReal_t cc1;
312 std::istringstream iss(test_graph6);
313 read_data1(iss, tgr);
314 max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
315 cout << "Maximum cycle ratio is " << max_cr << endl;
316 min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr),
317 get(edge_weight2, tgr), &cc);
318 cout << "Minimal cycle ratio is " << min_cr << endl;
319 std::pair<double, double> cr(.0,.0);
320 cout << "Critical cycle is:\n";
321 for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
322 {
323 cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
324 cout << "(" << get(vertex_name, tgr, source(*itr, tgr)) << "," <<
325 get(vertex_name, tgr, target(*itr, tgr)) << ") ";
326 }
327 BOOST_CHECK(std::abs(cr.first / cr.second - min_cr) < epsilon);
328 cout << endl;
329 }
330
331 {
332 GraphMInt gm(10);
333 typedef graph_traits<GraphMInt>::vertex_iterator VertexItM;
334 VertexItM vi1, vi2, vi_end;
335 for (boost::tie(vi1, vi_end) = vertices(gm); vi1 != vi_end; ++vi1)
336 {
337 for (vi2 = vertices(gm).first; vi2 != vi_end; ++vi2)
338 add_edge(*vi1, *vi2, gm);
339 }
340 max_cr = maximum_cycle_ratio(gm, get(vertex_index, gm),
341 get(&CEdgeProps<int, int>::m_w1, gm), get(&CEdgeProps<int, int>::m_w2, gm));
342 BOOST_CHECK(std::abs(max_cr - 0.5) < epsilon);
343 }
344
345 return 0;
346 }
347
348