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 |
9 | #include <boost/config.hpp> |
10 | |
11 | #ifdef BOOST_MSVC |
12 | // Without disabling this we get hard errors about initialialized pointers: |
13 | #pragma warning(disable : 4703) |
14 | #endif |
15 | |
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> |
23 | #include <boost/core/lightweight_test.hpp> |
24 | #include <iostream> |
25 | #include <boost/limits.hpp> |
26 | #include <fstream> |
27 | #include <string> |
28 | using namespace boost; |
29 | |
30 | enum vertex_position_t |
31 | { |
32 | vertex_position |
33 | }; |
34 | namespace boost |
35 | { |
36 | BOOST_INSTALL_PROPERTY(vertex, position); |
37 | } |
38 | |
39 | typedef square_topology<>::point_type point; |
40 | |
41 | template < typename Graph, typename PositionMap, typename Topology > |
42 | void print_graph_layout( |
43 | const Graph& g, PositionMap position, const Topology& topology) |
44 | { |
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; |
74 | } |
75 | } |
76 | |
77 | template < typename Graph, typename PositionMap > |
78 | void dump_graph_layout(std::string name, const Graph& g, PositionMap position) |
79 | { |
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" ; |
98 | } |
99 | |
100 | template < typename Graph > |
101 | void test_circle_layout( |
102 | Graph*, typename graph_traits< Graph >::vertices_size_type n) |
103 | { |
104 | typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator; |
105 | typedef |
106 | typename graph_traits< Graph >::vertices_size_type vertices_size_type; |
107 | |
108 | Graph g(n); |
109 | |
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); |
114 | |
115 | circle_graph_layout(g, get(vertex_position, g), 10.0); |
116 | |
117 | std::cout << "Regular polygon layout with " << n << " points.\n" ; |
118 | square_topology<> topology; |
119 | print_graph_layout(g, get(vertex_position, g), topology); |
120 | } |
121 | |
122 | struct simple_edge |
123 | { |
124 | int first, second; |
125 | }; |
126 | |
127 | struct kamada_kawai_done |
128 | { |
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 | } |
148 | } |
149 | |
150 | double last_delta; |
151 | }; |
152 | |
153 | template < typename Graph > void test_triangle(Graph*) |
154 | { |
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(x: 50.0)); |
178 | BOOST_TEST(ok); |
179 | |
180 | std::cout << "Triangle layout (Kamada-Kawai).\n" ; |
181 | print_graph_layout(g, get(vertex_position, g)); |
182 | } |
183 | |
184 | template < typename Graph > void test_cube(Graph*) |
185 | { |
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(x: 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)); |
252 | } |
253 | |
254 | template < typename Graph > void test_triangular(Graph*) |
255 | { |
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(x: 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(p: square_distance_attractive_force()) |
322 | .cooling(p: 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)); |
328 | } |
329 | |
330 | template < typename Graph > void test_disconnected(Graph*) |
331 | { |
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(x: 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(p: square_distance_attractive_force()) |
385 | .cooling(p: 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)); |
391 | } |
392 | |
393 | int main(int, char*[]) |
394 | { |
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, n: 5); |
403 | test_cube((Graph*)0); |
404 | test_triangular((Graph*)0); |
405 | test_disconnected((Graph*)0); |
406 | return boost::report_errors(); |
407 | } |
408 | |