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