1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/stdcpp/tsrc/Boost_test/graph/src/layout_test.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,377 @@
1.4 +// Copyright 2004 The Trustees of Indiana University.
1.5 +
1.6 +// Use, modification and distribution is subject to the Boost Software
1.7 +// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// Authors: Douglas Gregor
1.11 +// Andrew Lumsdaine
1.12 +/*
1.13 + * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
1.14 +*/
1.15 +
1.16 +#include <boost/graph/fruchterman_reingold.hpp>
1.17 +#include <boost/graph/random_layout.hpp>
1.18 +#include <boost/graph/kamada_kawai_spring_layout.hpp>
1.19 +#include <boost/graph/circle_layout.hpp>
1.20 +#include <boost/graph/adjacency_list.hpp>
1.21 +#include <boost/random/linear_congruential.hpp>
1.22 +#include <boost/test/minimal.hpp>
1.23 +#include <iostream>
1.24 +#include <boost/limits.hpp>
1.25 +#include <fstream>
1.26 +#include <string>
1.27 +#ifdef __SYMBIAN32__
1.28 +#include "std_log_result.h"
1.29 +#define LOG_FILENAME_LINE __FILE__, __LINE__
1.30 +#endif
1.31 +using namespace boost;
1.32 +
1.33 +enum vertex_position_t { vertex_position };
1.34 +namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }
1.35 +
1.36 +struct point
1.37 +{
1.38 + double x;
1.39 + double y;
1.40 +};
1.41 +
1.42 +template<typename Graph, typename PositionMap>
1.43 +void print_graph_layout(const Graph& g, PositionMap position)
1.44 +{
1.45 + typename graph_traits<Graph>::vertex_iterator vi, vi_end;
1.46 + int xmin = 0, xmax = 0, ymin = 0, ymax = 0;
1.47 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
1.48 + if ((int)position[*vi].x < xmin) xmin = (int)position[*vi].x;
1.49 + if ((int)position[*vi].x > xmax) xmax = (int)position[*vi].x;
1.50 + if ((int)position[*vi].y < ymin) ymin = (int)position[*vi].y;
1.51 + if ((int)position[*vi].y > ymax) ymax = (int)position[*vi].y;
1.52 + }
1.53 +
1.54 + for (int y = ymin; y <= ymax; ++y) {
1.55 + for (int x = xmin; x <= xmax; ++x) {
1.56 + // Find vertex at this position
1.57 + typename graph_traits<Graph>::vertices_size_type index = 0;
1.58 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++index) {
1.59 + if ((int)position[*vi].x == x && (int)position[*vi].y == y)
1.60 + break;
1.61 + }
1.62 +
1.63 + if (vi == vi_end) std::cout << ' ';
1.64 + else std::cout << (char)(index + 'A');
1.65 + }
1.66 + std::cout << std::endl;
1.67 + }
1.68 +}
1.69 +
1.70 +template<typename Graph, typename PositionMap>
1.71 +void dump_graph_layout(std::string name, const Graph& g, PositionMap position)
1.72 +{
1.73 + std::ofstream out((name + ".dot").c_str());
1.74 + out << "graph " << name << " {" << std::endl;
1.75 +
1.76 + typename graph_traits<Graph>::vertex_iterator vi, vi_end;
1.77 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
1.78 + out << " n" << get(vertex_index, g, *vi) << "[ pos=\""
1.79 + << (int)position[*vi].x + 25 << ", " << (int)position[*vi].y + 25
1.80 + << "\" ];\n";
1.81 + }
1.82 +
1.83 + typename graph_traits<Graph>::edge_iterator ei, ei_end;
1.84 + for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
1.85 + out << " n" << get(vertex_index, g, source(*ei, g)) << " -- n"
1.86 + << get(vertex_index, g, target(*ei, g)) << ";\n";
1.87 + }
1.88 + out << "}\n";
1.89 +}
1.90 +
1.91 +template<typename Graph>
1.92 +void
1.93 +test_circle_layout(Graph*, typename graph_traits<Graph>::vertices_size_type n)
1.94 +{
1.95 + typedef typename graph_traits<Graph>::vertex_descriptor vertex;
1.96 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.97 + typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
1.98 + typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
1.99 +
1.100 + Graph g(n);
1.101 +
1.102 + // Initialize vertex indices
1.103 + vertex_iterator vi = vertices(g).first;
1.104 + for (vertices_size_type i = 0; i < n; ++i, ++vi)
1.105 + put(vertex_index, g, *vi, i);
1.106 +
1.107 + circle_graph_layout(g, get(vertex_position, g), 10.0);
1.108 +
1.109 + std::cout << "Regular polygon layout with " << n << " points.\n";
1.110 + print_graph_layout(g, get(vertex_position, g));
1.111 +}
1.112 +
1.113 +struct simple_edge
1.114 +{
1.115 + int first, second;
1.116 +};
1.117 +
1.118 +struct kamada_kawai_done
1.119 +{
1.120 + kamada_kawai_done() : last_delta() {}
1.121 +
1.122 + template<typename Graph>
1.123 + bool operator()(double delta_p,
1.124 + typename boost::graph_traits<Graph>::vertex_descriptor p,
1.125 + const Graph& g,
1.126 + bool global)
1.127 + {
1.128 + if (global) {
1.129 + double diff = last_delta - delta_p;
1.130 + if (diff < 0) diff = -diff;
1.131 + last_delta = delta_p;
1.132 + return diff < 0.01;
1.133 + } else {
1.134 + return delta_p < 0.01;
1.135 + }
1.136 + }
1.137 +
1.138 + double last_delta;
1.139 +};
1.140 +
1.141 +template<typename Graph>
1.142 +void
1.143 +test_triangle(Graph*)
1.144 +{
1.145 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.146 + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
1.147 +
1.148 + Graph g;
1.149 +
1.150 + vertex_descriptor u = add_vertex(g); put(vertex_index, g, u, 0);
1.151 + vertex_descriptor v = add_vertex(g); put(vertex_index, g, v, 1);
1.152 + vertex_descriptor w = add_vertex(g); put(vertex_index, g, w, 2);
1.153 +
1.154 + edge_descriptor e1 = add_edge(u, v, g).first; put(edge_weight, g, e1, 1.0);
1.155 + edge_descriptor e2 = add_edge(v, w, g).first; put(edge_weight, g, e2, 1.0);
1.156 + edge_descriptor e3 = add_edge(w, u, g).first; put(edge_weight, g, e3, 1.0);
1.157 +
1.158 + circle_graph_layout(g, get(vertex_position, g), 25.0);
1.159 +
1.160 + bool ok = kamada_kawai_spring_layout(g,
1.161 + get(vertex_position, g),
1.162 + get(edge_weight, g),
1.163 + side_length(50.0));
1.164 + BOOST_CHECK(ok);
1.165 +
1.166 + std::cout << "Triangle layout (Kamada-Kawai).\n";
1.167 + print_graph_layout(g, get(vertex_position, g));
1.168 +}
1.169 +
1.170 +template<typename Graph>
1.171 +void
1.172 +test_cube(Graph*)
1.173 +{
1.174 + enum {A, B, C, D, E, F, G, H};
1.175 + simple_edge cube_edges[12] = {
1.176 + {A, E}, {A, B}, {A, D}, {B, F}, {B, C}, {C, D}, {C, G}, {D, H},
1.177 + {E, H}, {E, F}, {F, G}, {G, H}
1.178 + };
1.179 +
1.180 + Graph g(&cube_edges[0], &cube_edges[12], 8);
1.181 +
1.182 + typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
1.183 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.184 +
1.185 + vertex_iterator vi, vi_end;
1.186 + int i = 0;
1.187 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.188 + put(vertex_index, g, *vi, i++);
1.189 +
1.190 + edge_iterator ei, ei_end;
1.191 + for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
1.192 + put(edge_weight, g, *ei, 1.0);
1.193 + std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')
1.194 + << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')
1.195 + << ") ";
1.196 + }
1.197 + std::cerr << std::endl;
1.198 +
1.199 + circle_graph_layout(g, get(vertex_position, g), 25.0);
1.200 +
1.201 + bool ok = kamada_kawai_spring_layout(g,
1.202 + get(vertex_position, g),
1.203 + get(edge_weight, g),
1.204 + side_length(50.0),
1.205 + kamada_kawai_done());
1.206 + BOOST_CHECK(ok);
1.207 +
1.208 + std::cout << "Cube layout (Kamada-Kawai).\n";
1.209 + print_graph_layout(g, get(vertex_position, g));
1.210 +
1.211 + dump_graph_layout("cube", g, get(vertex_position, g));
1.212 +
1.213 + minstd_rand gen;
1.214 + random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,
1.215 + gen);
1.216 +
1.217 + std::vector<point> displacements(num_vertices(g));
1.218 + fruchterman_reingold_force_directed_layout
1.219 + (g,
1.220 + get(vertex_position, g),
1.221 + 50.0,
1.222 + 50.0,
1.223 + square_distance_attractive_force(),
1.224 + square_distance_repulsive_force(),
1.225 + all_force_pairs(),
1.226 + linear_cooling<double>(100),
1.227 + make_iterator_property_map(displacements.begin(),
1.228 + get(vertex_index, g),
1.229 + point()));
1.230 +
1.231 + std::cout << "Cube layout (Fruchterman-Reingold).\n";
1.232 + print_graph_layout(g, get(vertex_position, g));
1.233 +
1.234 + dump_graph_layout("cube-fr", g, get(vertex_position, g));
1.235 +}
1.236 +
1.237 +template<typename Graph>
1.238 +void
1.239 +test_triangular(Graph*)
1.240 +{
1.241 + enum {A, B, C, D, E, F, G, H, I, J};
1.242 + simple_edge triangular_edges[18] = {
1.243 + {A, B}, {A, C}, {B, C}, {B, D}, {B, E}, {C, E}, {C, F}, {D, E}, {D, G},
1.244 + {D, H}, {E, F}, {E, H}, {E, I}, {F, I}, {F, J}, {G, H}, {H, I}, {I, J}
1.245 + };
1.246 +
1.247 + Graph g(&triangular_edges[0], &triangular_edges[18], 10);
1.248 +
1.249 + typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
1.250 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.251 +
1.252 + vertex_iterator vi, vi_end;
1.253 + int i = 0;
1.254 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.255 + put(vertex_index, g, *vi, i++);
1.256 +
1.257 + edge_iterator ei, ei_end;
1.258 + for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
1.259 + put(edge_weight, g, *ei, 1.0);
1.260 + std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')
1.261 + << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')
1.262 + << ") ";
1.263 + }
1.264 + std::cerr << std::endl;
1.265 +
1.266 + circle_graph_layout(g, get(vertex_position, g), 25.0);
1.267 +
1.268 + bool ok = kamada_kawai_spring_layout(g,
1.269 + get(vertex_position, g),
1.270 + get(edge_weight, g),
1.271 + side_length(50.0),
1.272 + kamada_kawai_done());
1.273 + BOOST_CHECK(ok);
1.274 +
1.275 + std::cout << "Triangular layout (Kamada-Kawai).\n";
1.276 + print_graph_layout(g, get(vertex_position, g));
1.277 +
1.278 + dump_graph_layout("triangular-kk", g, get(vertex_position, g));
1.279 +
1.280 + minstd_rand gen;
1.281 + random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,
1.282 + gen);
1.283 +
1.284 + dump_graph_layout("random", g, get(vertex_position, g));
1.285 +
1.286 + std::vector<point> displacements(num_vertices(g));
1.287 + fruchterman_reingold_force_directed_layout
1.288 + (g,
1.289 + get(vertex_position, g),
1.290 + 50.0,
1.291 + 50.0,
1.292 + attractive_force(square_distance_attractive_force()).
1.293 + cooling(linear_cooling<double>(100)));
1.294 +
1.295 + std::cout << "Triangular layout (Fruchterman-Reingold).\n";
1.296 + print_graph_layout(g, get(vertex_position, g));
1.297 +
1.298 + dump_graph_layout("triangular-fr", g, get(vertex_position, g));
1.299 +}
1.300 +
1.301 +template<typename Graph>
1.302 +void
1.303 +test_disconnected(Graph*)
1.304 +{
1.305 + enum {A, B, C, D, E, F, G, H};
1.306 + simple_edge triangular_edges[13] = {
1.307 + {A, B}, {B, C}, {C, A},
1.308 + {D, E}, {E, F}, {F, G}, {G, H}, {H, D},
1.309 + {D, F}, {F, H}, {H, E}, {E, G}, {G, D}
1.310 + };
1.311 +
1.312 + Graph g(&triangular_edges[0], &triangular_edges[13], 8);
1.313 +
1.314 + typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
1.315 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.316 +
1.317 + vertex_iterator vi, vi_end;
1.318 + int i = 0;
1.319 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1.320 + put(vertex_index, g, *vi, i++);
1.321 +
1.322 + edge_iterator ei, ei_end;
1.323 + for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
1.324 + put(edge_weight, g, *ei, 1.0);
1.325 + std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')
1.326 + << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')
1.327 + << ") ";
1.328 + }
1.329 + std::cerr << std::endl;
1.330 +
1.331 + circle_graph_layout(g, get(vertex_position, g), 25.0);
1.332 +
1.333 + bool ok = kamada_kawai_spring_layout(g,
1.334 + get(vertex_position, g),
1.335 + get(edge_weight, g),
1.336 + side_length(50.0),
1.337 + kamada_kawai_done());
1.338 + BOOST_CHECK(!ok);
1.339 +
1.340 + minstd_rand gen;
1.341 + random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,
1.342 + gen);
1.343 +
1.344 + std::vector<point> displacements(num_vertices(g));
1.345 + fruchterman_reingold_force_directed_layout
1.346 + (g,
1.347 + get(vertex_position, g),
1.348 + 50.0,
1.349 + 50.0,
1.350 + attractive_force(square_distance_attractive_force()).
1.351 + cooling(linear_cooling<double>(50)));
1.352 +
1.353 + std::cout << "Disconnected layout (Fruchterman-Reingold).\n";
1.354 + print_graph_layout(g, get(vertex_position, g));
1.355 +
1.356 + dump_graph_layout("disconnected-fr", g, get(vertex_position, g));
1.357 +}
1.358 +
1.359 +int test_main(int, char*[])
1.360 +{
1.361 + typedef adjacency_list<listS, listS, undirectedS,
1.362 + // Vertex properties
1.363 + property<vertex_index_t, int,
1.364 + property<vertex_position_t, point> >,
1.365 + // Edge properties
1.366 + property<edge_weight_t, double> > Graph;
1.367 +
1.368 + test_circle_layout((Graph*)0, 5);
1.369 + test_cube((Graph*)0);
1.370 + test_triangular((Graph*)0);
1.371 + test_disconnected((Graph*)0);
1.372 +
1.373 +#ifdef __SYMBIAN32__
1.374 +std_log(LOG_FILENAME_LINE,"[End Test Case ]");
1.375 +
1.376 + testResultXml("layout_test");
1.377 + close_log_file();
1.378 +#endif
1.379 + return 0;
1.380 +}