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