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>
28using namespace boost;
29
30enum vertex_position_t
31{
32 vertex_position
33};
34namespace boost
35{
36BOOST_INSTALL_PROPERTY(vertex, position);
37}
38
39typedef square_topology<>::point_type point;
40
41template < typename Graph, typename PositionMap, typename Topology >
42void 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
77template < typename Graph, typename PositionMap >
78void 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
100template < typename Graph >
101void 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
122struct simple_edge
123{
124 int first, second;
125};
126
127struct 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
153template < 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
184template < 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
254template < 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
330template < 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
393int 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

source code of boost/libs/graph/test/layout_test.cpp