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 | { |
153 | 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 > |
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 | |
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 | |
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 | { |
197 | static double infinity() { return 1000; } |
198 | }; |
199 | |
200 | struct my_float2 : boost::mcr_float<> |
201 | { |
202 | static double infinity() { return 2; } |
203 | }; |
204 | |
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(p: vertex_index, g&: tg); |
220 | property_map< diGraphInt, edge_weight_t >::type ew1m = get(p: edge_weight, g&: tg); |
221 | property_map< diGraphInt, edge_weight2_t >::type ew2m |
222 | = get(p: edge_weight2, g&: tg); |
223 | |
224 | { |
225 | std::istringstream iss(test_graph1); |
226 | assert(iss.good()); |
227 | read_data1(is&: iss, g&: tg); |
228 | max_cr = maximum_cycle_ratio(g: 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(is&: iss, g&: 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(is&: iss, g&: tgi); |
252 | double max_cr = maximum_cycle_ratio( |
253 | g: tgi, vim, ew1m, ew2m, pcc: 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(g: tgi, vim, ewm: ew1m, eim: get(p: edge_index, g&: 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(is&: iss, g&: tg); |
265 | max_cr = maximum_cycle_ratio(g: 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(g: 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(is&: iss, g&: tg); |
277 | min_cr = minimum_cycle_ratio(g: tg, vim, ew1m, ew2m, pcc: &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(p: vertex_name, g&: tg, key: source(e: *itr, tg)) << "," |
284 | << get(p: vertex_name, g&: tg, key: target(e: *itr, tg)) << ") " ; |
285 | } |
286 | cout << endl; |
287 | tg.clear(); |
288 | } |
289 | |
290 | { |
291 | read_data(file: argv[1], g&: tg); |
292 | min_cr |
293 | = boost::minimum_cycle_ratio(g: tg, vim, ew1m, ew2m, pcc: &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(p: vertex_name, g&: tg, key: source(e: *it, tg)) << "," |
300 | << get(p: vertex_name, g&: tg, key: target(e: *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(is&: iss, g&: tgr); |
311 | max_cr = maximum_cycle_ratio(g: tgr, vim: get(p: vertex_index, g&: tgr), |
312 | ew1m: get(p: edge_weight, g&: tgr), ew2m: get(p: edge_weight2, g&: tgr)); |
313 | cout << "Maximum cycle ratio is " << max_cr << endl; |
314 | min_cr = minimum_cycle_ratio(g: tgr, vim: get(p: vertex_index, g&: tgr), |
315 | ew1m: get(p: edge_weight, g&: tgr), ew2m: get(p: edge_weight2, g&: tgr), pcc: &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(p: edge_weight, g&: tgr, key: *itr); |
322 | cr.second += get(p: edge_weight2, g&: tgr, key: *itr); |
323 | cout << "(" << get(p: vertex_name, g&: tgr, key: source(e: *itr, tgr)) << "," |
324 | << get(p: vertex_name, g&: tgr, key: target(e: *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(t0&: vi1, t1&: vi_end) = vertices(g_: gm); vi1 != vi_end; ++vi1) |
335 | { |
336 | for (vi2 = vertices(g_: gm).first; vi2 != vi_end; ++vi2) |
337 | add_edge(u: *vi1, v: *vi2, g&: gm); |
338 | } |
339 | max_cr = maximum_cycle_ratio(g: gm, vim: get(vertex_index, gm), |
340 | ew1m: get(tag: &CEdgeProps< int, int >::m_w1, g&: gm), |
341 | ew2m: get(tag: &CEdgeProps< int, int >::m_w2, g&: gm)); |
342 | BOOST_TEST(std::abs(max_cr - 0.5) < epsilon); |
343 | } |
344 | |
345 | return boost::report_errors(); |
346 | } |
347 | |