]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2004 The Trustees of Indiana University. |
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 | // Authors: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
92f5a8d4 TL |
9 | #include <boost/config.hpp> |
10 | ||
11 | #ifdef BOOST_MSVC | |
12 | // Without disabling this we get hard errors about initialialized pointers: | |
f67539c2 | 13 | #pragma warning(disable : 4703) |
92f5a8d4 TL |
14 | #endif |
15 | ||
7c673cae FG |
16 | #include <boost/graph/fruchterman_reingold.hpp> |
17 | #include <boost/graph/random_layout.hpp> | |
18 | #include <boost/graph/kamada_kawai_spring_layout.hpp> | |
19 | #include <boost/graph/circle_layout.hpp> | |
20 | #include <boost/graph/adjacency_list.hpp> | |
21 | #include <boost/graph/point_traits.hpp> | |
22 | #include <boost/random/linear_congruential.hpp> | |
f67539c2 | 23 | #include <boost/core/lightweight_test.hpp> |
7c673cae FG |
24 | #include <iostream> |
25 | #include <boost/limits.hpp> | |
26 | #include <fstream> | |
27 | #include <string> | |
28 | using namespace boost; | |
29 | ||
f67539c2 TL |
30 | enum vertex_position_t |
31 | { | |
32 | vertex_position | |
33 | }; | |
34 | namespace boost | |
35 | { | |
36 | BOOST_INSTALL_PROPERTY(vertex, position); | |
37 | } | |
7c673cae FG |
38 | |
39 | typedef square_topology<>::point_type point; | |
40 | ||
f67539c2 TL |
41 | template < typename Graph, typename PositionMap, typename Topology > |
42 | void print_graph_layout( | |
43 | const Graph& g, PositionMap position, const Topology& topology) | |
7c673cae | 44 | { |
f67539c2 TL |
45 | typedef typename Topology::point_type Point; |
46 | // Find min/max ranges | |
47 | Point min_point = position[*vertices(g).first], max_point = min_point; | |
48 | BGL_FORALL_VERTICES_T(v, g, Graph) | |
49 | { | |
50 | min_point = topology.pointwise_min(min_point, position[v]); | |
51 | max_point = topology.pointwise_max(max_point, position[v]); | |
52 | } | |
53 | ||
54 | for (int y = (int)min_point[1]; y <= (int)max_point[1]; ++y) | |
55 | { | |
56 | for (int x = (int)min_point[0]; x <= (int)max_point[0]; ++x) | |
57 | { | |
58 | typename graph_traits< Graph >::vertex_iterator vi, vi_end; | |
59 | // Find vertex at this position | |
60 | typename graph_traits< Graph >::vertices_size_type index = 0; | |
61 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; | |
62 | ++vi, ++index) | |
63 | { | |
64 | if ((int)position[*vi][0] == x && (int)position[*vi][1] == y) | |
65 | break; | |
66 | } | |
67 | ||
68 | if (vi == vi_end) | |
69 | std::cout << ' '; | |
70 | else | |
71 | std::cout << (char)(index + 'A'); | |
72 | } | |
73 | std::cout << std::endl; | |
7c673cae | 74 | } |
7c673cae FG |
75 | } |
76 | ||
f67539c2 | 77 | template < typename Graph, typename PositionMap > |
7c673cae FG |
78 | void dump_graph_layout(std::string name, const Graph& g, PositionMap position) |
79 | { | |
f67539c2 TL |
80 | std::ofstream out((name + ".dot").c_str()); |
81 | out << "graph " << name << " {" << std::endl; | |
82 | ||
83 | typename graph_traits< Graph >::vertex_iterator vi, vi_end; | |
84 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
85 | { | |
86 | out << " n" << get(vertex_index, g, *vi) << "[ pos=\"" | |
87 | << (int)position[*vi][0] + 25 << ", " << (int)position[*vi][1] + 25 | |
88 | << "\" ];\n"; | |
89 | } | |
90 | ||
91 | typename graph_traits< Graph >::edge_iterator ei, ei_end; | |
92 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
93 | { | |
94 | out << " n" << get(vertex_index, g, source(*ei, g)) << " -- n" | |
95 | << get(vertex_index, g, target(*ei, g)) << ";\n"; | |
96 | } | |
97 | out << "}\n"; | |
7c673cae FG |
98 | } |
99 | ||
f67539c2 TL |
100 | template < typename Graph > |
101 | void test_circle_layout( | |
102 | Graph*, typename graph_traits< Graph >::vertices_size_type n) | |
7c673cae | 103 | { |
f67539c2 TL |
104 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; |
105 | typedef | |
106 | typename graph_traits< Graph >::vertices_size_type vertices_size_type; | |
7c673cae | 107 | |
f67539c2 | 108 | Graph g(n); |
7c673cae | 109 | |
f67539c2 TL |
110 | // Initialize vertex indices |
111 | vertex_iterator vi = vertices(g).first; | |
112 | for (vertices_size_type i = 0; i < n; ++i, ++vi) | |
113 | put(vertex_index, g, *vi, i); | |
7c673cae | 114 | |
f67539c2 | 115 | circle_graph_layout(g, get(vertex_position, g), 10.0); |
7c673cae | 116 | |
f67539c2 TL |
117 | std::cout << "Regular polygon layout with " << n << " points.\n"; |
118 | square_topology<> topology; | |
119 | print_graph_layout(g, get(vertex_position, g), topology); | |
7c673cae FG |
120 | } |
121 | ||
122 | struct simple_edge | |
123 | { | |
f67539c2 | 124 | int first, second; |
7c673cae FG |
125 | }; |
126 | ||
f67539c2 | 127 | struct kamada_kawai_done |
7c673cae | 128 | { |
f67539c2 TL |
129 | kamada_kawai_done() : last_delta() {} |
130 | ||
131 | template < typename Graph > | |
132 | bool operator()(double delta_p, | |
133 | typename boost::graph_traits< Graph >::vertex_descriptor /*p*/, | |
134 | const Graph& /*g*/, bool global) | |
135 | { | |
136 | if (global) | |
137 | { | |
138 | double diff = last_delta - delta_p; | |
139 | if (diff < 0) | |
140 | diff = -diff; | |
141 | last_delta = delta_p; | |
142 | return diff < 0.01; | |
143 | } | |
144 | else | |
145 | { | |
146 | return delta_p < 0.01; | |
147 | } | |
7c673cae | 148 | } |
7c673cae | 149 | |
f67539c2 | 150 | double last_delta; |
7c673cae FG |
151 | }; |
152 | ||
f67539c2 | 153 | template < typename Graph > void test_triangle(Graph*) |
7c673cae | 154 | { |
f67539c2 TL |
155 | typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor; |
156 | typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor; | |
157 | ||
158 | Graph g; | |
159 | ||
160 | vertex_descriptor u = add_vertex(g); | |
161 | put(vertex_index, g, u, 0); | |
162 | vertex_descriptor v = add_vertex(g); | |
163 | put(vertex_index, g, v, 1); | |
164 | vertex_descriptor w = add_vertex(g); | |
165 | put(vertex_index, g, w, 2); | |
166 | ||
167 | edge_descriptor e1 = add_edge(u, v, g).first; | |
168 | put(edge_weight, g, e1, 1.0); | |
169 | edge_descriptor e2 = add_edge(v, w, g).first; | |
170 | put(edge_weight, g, e2, 1.0); | |
171 | edge_descriptor e3 = add_edge(w, u, g).first; | |
172 | put(edge_weight, g, e3, 1.0); | |
173 | ||
174 | circle_graph_layout(g, get(vertex_position, g), 25.0); | |
175 | ||
176 | bool ok = kamada_kawai_spring_layout(g, get(vertex_position, g), | |
177 | get(edge_weight, g), square_topology<>(50.0), side_length(50.0)); | |
178 | BOOST_TEST(ok); | |
179 | ||
180 | std::cout << "Triangle layout (Kamada-Kawai).\n"; | |
181 | print_graph_layout(g, get(vertex_position, g)); | |
7c673cae FG |
182 | } |
183 | ||
f67539c2 | 184 | template < typename Graph > void test_cube(Graph*) |
7c673cae | 185 | { |
f67539c2 TL |
186 | enum |
187 | { | |
188 | A, | |
189 | B, | |
190 | C, | |
191 | D, | |
192 | E, | |
193 | F, | |
194 | G, | |
195 | H | |
196 | }; | |
197 | simple_edge cube_edges[12] | |
198 | = { { A, E }, { A, B }, { A, D }, { B, F }, { B, C }, { C, D }, | |
199 | { C, G }, { D, H }, { E, H }, { E, F }, { F, G }, { G, H } }; | |
200 | ||
201 | Graph g(&cube_edges[0], &cube_edges[12], 8); | |
202 | ||
203 | typedef typename graph_traits< Graph >::edge_iterator edge_iterator; | |
204 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; | |
205 | ||
206 | vertex_iterator vi, vi_end; | |
207 | int i = 0; | |
208 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
209 | put(vertex_index, g, *vi, i++); | |
210 | ||
211 | edge_iterator ei, ei_end; | |
212 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
213 | { | |
214 | put(edge_weight, g, *ei, 1.0); | |
215 | std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A') | |
216 | << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A') | |
217 | << ") "; | |
218 | } | |
219 | std::cerr << std::endl; | |
220 | ||
221 | circle_graph_layout(g, get(vertex_position, g), 25.0); | |
222 | ||
223 | bool ok = kamada_kawai_spring_layout(g, get(vertex_position, g), | |
224 | get(edge_weight, g), square_topology<>(50.0), side_length(50.0), | |
225 | kamada_kawai_done()); | |
226 | BOOST_TEST(ok); | |
227 | ||
228 | std::cout << "Cube layout (Kamada-Kawai).\n"; | |
229 | print_graph_layout(g, get(vertex_position, g), square_topology<>(50.)); | |
230 | ||
231 | dump_graph_layout("cube", g, get(vertex_position, g)); | |
232 | ||
233 | minstd_rand gen; | |
234 | typedef square_topology<> Topology; | |
235 | Topology topology(gen, 50.0); | |
236 | std::vector< Topology::point_difference_type > displacements( | |
237 | num_vertices(g)); | |
238 | rectangle_topology<> rect_top(gen, 0, 0, 50, 50); | |
239 | random_graph_layout(g, get(vertex_position, g), rect_top); | |
240 | ||
241 | fruchterman_reingold_force_directed_layout(g, get(vertex_position, g), | |
242 | topology, square_distance_attractive_force(), | |
243 | square_distance_repulsive_force(), all_force_pairs(), | |
244 | linear_cooling< double >(100), | |
245 | make_iterator_property_map(displacements.begin(), get(vertex_index, g), | |
246 | Topology::point_difference_type())); | |
247 | ||
248 | std::cout << "Cube layout (Fruchterman-Reingold).\n"; | |
249 | print_graph_layout(g, get(vertex_position, g), square_topology<>(50.)); | |
250 | ||
251 | dump_graph_layout("cube-fr", g, get(vertex_position, g)); | |
7c673cae FG |
252 | } |
253 | ||
f67539c2 | 254 | template < typename Graph > void test_triangular(Graph*) |
7c673cae | 255 | { |
f67539c2 TL |
256 | enum |
257 | { | |
258 | A, | |
259 | B, | |
260 | C, | |
261 | D, | |
262 | E, | |
263 | F, | |
264 | G, | |
265 | H, | |
266 | I, | |
267 | J | |
268 | }; | |
269 | simple_edge triangular_edges[18] = { { A, B }, { A, C }, { B, C }, { B, D }, | |
270 | { B, E }, { C, E }, { C, F }, { D, E }, { D, G }, { D, H }, { E, F }, | |
271 | { E, H }, { E, I }, { F, I }, { F, J }, { G, H }, { H, I }, { I, J } }; | |
272 | ||
273 | Graph g(&triangular_edges[0], &triangular_edges[18], 10); | |
274 | ||
275 | typedef typename graph_traits< Graph >::edge_iterator edge_iterator; | |
276 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; | |
277 | ||
278 | vertex_iterator vi, vi_end; | |
279 | int i = 0; | |
280 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
281 | put(vertex_index, g, *vi, i++); | |
282 | ||
283 | edge_iterator ei, ei_end; | |
284 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
285 | { | |
286 | put(edge_weight, g, *ei, 1.0); | |
287 | std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A') | |
288 | << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A') | |
289 | << ") "; | |
290 | } | |
291 | std::cerr << std::endl; | |
292 | ||
293 | typedef square_topology<> Topology; | |
294 | minstd_rand gen; | |
295 | Topology topology(gen, 50.0); | |
296 | Topology::point_type origin; | |
297 | origin[0] = origin[1] = 50.0; | |
298 | Topology::point_difference_type extent; | |
299 | extent[0] = extent[1] = 50.0; | |
300 | ||
301 | circle_graph_layout(g, get(vertex_position, g), 25.0); | |
302 | ||
303 | bool ok = kamada_kawai_spring_layout(g, get(vertex_position, g), | |
304 | get(edge_weight, g), topology, side_length(50.0), kamada_kawai_done()); | |
305 | BOOST_TEST(ok); | |
306 | ||
307 | std::cout << "Triangular layout (Kamada-Kawai).\n"; | |
308 | print_graph_layout(g, get(vertex_position, g), square_topology<>(50.)); | |
309 | ||
310 | dump_graph_layout("triangular-kk", g, get(vertex_position, g)); | |
311 | ||
312 | rectangle_topology<> rect_top(gen, -25, -25, 25, 25); | |
313 | random_graph_layout(g, get(vertex_position, g), rect_top); | |
314 | ||
315 | dump_graph_layout("random", g, get(vertex_position, g)); | |
316 | ||
317 | std::vector< Topology::point_difference_type > displacements( | |
318 | num_vertices(g)); | |
319 | fruchterman_reingold_force_directed_layout(g, get(vertex_position, g), | |
320 | topology, | |
321 | attractive_force(square_distance_attractive_force()) | |
322 | .cooling(linear_cooling< double >(100))); | |
323 | ||
324 | std::cout << "Triangular layout (Fruchterman-Reingold).\n"; | |
325 | print_graph_layout(g, get(vertex_position, g), square_topology<>(50.)); | |
326 | ||
327 | dump_graph_layout("triangular-fr", g, get(vertex_position, g)); | |
7c673cae FG |
328 | } |
329 | ||
f67539c2 | 330 | template < typename Graph > void test_disconnected(Graph*) |
7c673cae | 331 | { |
f67539c2 TL |
332 | enum |
333 | { | |
334 | A, | |
335 | B, | |
336 | C, | |
337 | D, | |
338 | E, | |
339 | F, | |
340 | G, | |
341 | H | |
342 | }; | |
343 | simple_edge triangular_edges[13] = { { A, B }, { B, C }, { C, A }, { D, E }, | |
344 | { E, F }, { F, G }, { G, H }, { H, D }, { D, F }, { F, H }, { H, E }, | |
345 | { E, G }, { G, D } }; | |
346 | ||
347 | Graph g(&triangular_edges[0], &triangular_edges[13], 8); | |
348 | ||
349 | typedef typename graph_traits< Graph >::edge_iterator edge_iterator; | |
350 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; | |
351 | ||
352 | vertex_iterator vi, vi_end; | |
353 | int i = 0; | |
354 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
355 | put(vertex_index, g, *vi, i++); | |
356 | ||
357 | edge_iterator ei, ei_end; | |
358 | for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
359 | { | |
360 | put(edge_weight, g, *ei, 1.0); | |
361 | std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A') | |
362 | << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A') | |
363 | << ") "; | |
364 | } | |
365 | std::cerr << std::endl; | |
366 | ||
367 | circle_graph_layout(g, get(vertex_position, g), 25.0); | |
368 | ||
369 | bool ok = kamada_kawai_spring_layout(g, get(vertex_position, g), | |
370 | get(edge_weight, g), square_topology<>(50.0), side_length(50.0), | |
371 | kamada_kawai_done()); | |
372 | BOOST_TEST(!ok); | |
373 | ||
374 | minstd_rand gen; | |
375 | rectangle_topology<> rect_top(gen, -25, -25, 25, 25); | |
376 | random_graph_layout(g, get(vertex_position, g), rect_top); | |
377 | ||
378 | typedef square_topology<> Topology; | |
379 | Topology topology(gen, 50.0); | |
380 | std::vector< Topology::point_difference_type > displacements( | |
381 | num_vertices(g)); | |
382 | fruchterman_reingold_force_directed_layout(g, get(vertex_position, g), | |
383 | topology, | |
384 | attractive_force(square_distance_attractive_force()) | |
385 | .cooling(linear_cooling< double >(50))); | |
386 | ||
387 | std::cout << "Disconnected layout (Fruchterman-Reingold).\n"; | |
388 | print_graph_layout(g, get(vertex_position, g), square_topology<>(50.)); | |
389 | ||
390 | dump_graph_layout("disconnected-fr", g, get(vertex_position, g)); | |
7c673cae FG |
391 | } |
392 | ||
f67539c2 | 393 | int main(int, char*[]) |
7c673cae | 394 | { |
f67539c2 TL |
395 | typedef adjacency_list< listS, listS, undirectedS, |
396 | // Vertex properties | |
397 | property< vertex_index_t, int, property< vertex_position_t, point > >, | |
398 | // Edge properties | |
399 | property< edge_weight_t, double > > | |
400 | Graph; | |
401 | ||
402 | test_circle_layout((Graph*)0, 5); | |
403 | test_cube((Graph*)0); | |
404 | test_triangular((Graph*)0); | |
405 | test_disconnected((Graph*)0); | |
406 | return boost::report_errors(); | |
7c673cae | 407 | } |