Symaptic: os/ossrv/stdcpp/tsrc/Boost_test/graph/src/layout

     1 // Copyright 2004 The Trustees of Indiana University.

     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)

     7 //  Authors: Douglas Gregor

     8 //           Andrew Lumsdaine

     9 /*

    10  * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

    11 */

    13 #include <boost/graph/fruchterman_reingold.hpp>

    14 #include <boost/graph/random_layout.hpp>

    15 #include <boost/graph/kamada_kawai_spring_layout.hpp>

    16 #include <boost/graph/circle_layout.hpp>

    17 #include <boost/graph/adjacency_list.hpp>

    18 #include <boost/random/linear_congruential.hpp>

    19 #include <boost/test/minimal.hpp>

    20 #include <iostream>

    21 #include <boost/limits.hpp>

    22 #include <fstream>

    23 #include <string>

    24 #ifdef __SYMBIAN32__

    25 #include "std_log_result.h"

    26 #define LOG_FILENAME_LINE __FILE__, __LINE__

    27 #endif

    28 using namespace boost;

    30 enum vertex_position_t { vertex_position };

    31 namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }

    33 struct point

    34 {

    35   double x;

    36   double y;

    37 };

    39 template<typename Graph, typename PositionMap>

    40 void print_graph_layout(const Graph& g, PositionMap position)

    41 {

    42   typename graph_traits<Graph>::vertex_iterator vi, vi_end;

    43   int xmin = 0, xmax = 0, ymin = 0, ymax = 0;

    44   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {

    45     if ((int)position[*vi].x < xmin) xmin = (int)position[*vi].x;

    46     if ((int)position[*vi].x > xmax) xmax = (int)position[*vi].x;

    47     if ((int)position[*vi].y < ymin) ymin = (int)position[*vi].y;

    48     if ((int)position[*vi].y > ymax) ymax = (int)position[*vi].y;

    49   }

    51   for (int y = ymin; y <= ymax; ++y) {

    52     for (int x = xmin; x <= xmax; ++x) {

    53       // Find vertex at this position

    54       typename graph_traits<Graph>::vertices_size_type index = 0;

    55       for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++index) {

    56         if ((int)position[*vi].x == x && (int)position[*vi].y == y)

    57           break;

    58       }

    60       if (vi == vi_end) std::cout << ' ';

    61       else std::cout << (char)(index + 'A');

    62     }

    63     std::cout << std::endl;

    64   }

    65 }

    67 template<typename Graph, typename PositionMap>

    68 void dump_graph_layout(std::string name, const Graph& g, PositionMap position)

    69 {

    70   std::ofstream out((name + ".dot").c_str());

    71   out << "graph " << name << " {" << std::endl;

    73   typename graph_traits<Graph>::vertex_iterator vi, vi_end;

    74   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {

    75     out << "  n" << get(vertex_index, g, *vi) << "[ pos=\""

    76         << (int)position[*vi].x + 25 << ", " << (int)position[*vi].y + 25

    77         << "\" ];\n";

    78   }

    80   typename graph_traits<Graph>::edge_iterator ei, ei_end;

    81   for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

    82     out << "  n" << get(vertex_index, g, source(*ei, g)) << " -- n"

    83         << get(vertex_index, g, target(*ei, g)) << ";\n";

    84   }

    85   out << "}\n";

    86 }

    88 template<typename Graph>

    89 void

    90 test_circle_layout(Graph*, typename graph_traits<Graph>::vertices_size_type n)

    91 {

    92   typedef typename graph_traits<Graph>::vertex_descriptor vertex;

    93   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

    94   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;

    95   typedef typename graph_traits<Graph>::edges_size_type edges_size_type;

    97   Graph g(n);

    99   // Initialize vertex indices

   100   vertex_iterator vi = vertices(g).first;

   101   for (vertices_size_type i = 0; i < n; ++i, ++vi)

   102     put(vertex_index, g, *vi, i);

   104   circle_graph_layout(g, get(vertex_position, g), 10.0);

   106   std::cout << "Regular polygon layout with " << n << " points.\n";

   107   print_graph_layout(g, get(vertex_position, g));

   108 }

   110 struct simple_edge

   111 {

   112   int first, second;

   113 };

   115 struct kamada_kawai_done

   116 {

   117   kamada_kawai_done() : last_delta() {}

   119   template<typename Graph>

   120   bool operator()(double delta_p,

   121                   typename boost::graph_traits<Graph>::vertex_descriptor p,

   122                   const Graph& g,

   123                   bool global)

   124   {

   125     if (global) {

   126       double diff = last_delta - delta_p;

   127       if (diff < 0) diff = -diff;

   128       last_delta = delta_p;

   129       return diff < 0.01;

   130     } else {

   131       return delta_p < 0.01;

   132     }

   133   }

   135   double last_delta;

   136 };

   138 template<typename Graph>

   139 void

   140 test_triangle(Graph*)

   141 {

   142   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

   143   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

   145   Graph g;

   147   vertex_descriptor u = add_vertex(g); put(vertex_index, g, u, 0);

   148   vertex_descriptor v = add_vertex(g); put(vertex_index, g, v, 1);

   149   vertex_descriptor w = add_vertex(g); put(vertex_index, g, w, 2);

   151   edge_descriptor e1 = add_edge(u, v, g).first; put(edge_weight, g, e1, 1.0);

   152   edge_descriptor e2 = add_edge(v, w, g).first; put(edge_weight, g, e2, 1.0);

   153   edge_descriptor e3 = add_edge(w, u, g).first; put(edge_weight, g, e3, 1.0);

   155   circle_graph_layout(g, get(vertex_position, g), 25.0);

   157   bool ok = kamada_kawai_spring_layout(g,

   158                                        get(vertex_position, g),

   159                                        get(edge_weight, g),

   160                                        side_length(50.0));

   161   BOOST_CHECK(ok);

   163   std::cout << "Triangle layout (Kamada-Kawai).\n";

   164   print_graph_layout(g, get(vertex_position, g));

   165 }

   167 template<typename Graph>

   168 void

   169 test_cube(Graph*)

   170 {

   171   enum {A, B, C, D, E, F, G, H};

   172   simple_edge cube_edges[12] = {

   173     {A, E}, {A, B}, {A, D}, {B, F}, {B, C}, {C, D}, {C, G}, {D, H},

   174     {E, H}, {E, F}, {F, G}, {G, H}

   175   };

   177   Graph g(&cube_edges[0], &cube_edges[12], 8);

   179   typedef typename graph_traits<Graph>::edge_iterator edge_iterator;

   180   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

   182   vertex_iterator vi, vi_end;

   183   int i = 0;

   184   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

   185     put(vertex_index, g, *vi, i++);

   187   edge_iterator ei, ei_end;

   188   for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

   189     put(edge_weight, g, *ei, 1.0);

   190     std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')

   191               << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')

   192               << ") ";

   193   }

   194   std::cerr << std::endl;

   196   circle_graph_layout(g, get(vertex_position, g), 25.0);

   198   bool ok = kamada_kawai_spring_layout(g,

   199                                        get(vertex_position, g),

   200                                        get(edge_weight, g),

   201                                        side_length(50.0),

   202                                        kamada_kawai_done());

   203   BOOST_CHECK(ok);

   205   std::cout << "Cube layout (Kamada-Kawai).\n";

   206   print_graph_layout(g, get(vertex_position, g));

   208   dump_graph_layout("cube", g, get(vertex_position, g));

   210   minstd_rand gen;

   211   random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,

   212                       gen);

   214   std::vector<point> displacements(num_vertices(g));

   215   fruchterman_reingold_force_directed_layout

   216     (g,

   217      get(vertex_position, g),

   218      50.0,

   219      50.0,

   220      square_distance_attractive_force(),

   221      square_distance_repulsive_force(),

   222      all_force_pairs(),

   223      linear_cooling<double>(100),

   224      make_iterator_property_map(displacements.begin(),

   225                                 get(vertex_index, g),

   226                                 point()));

   228   std::cout << "Cube layout (Fruchterman-Reingold).\n";

   229   print_graph_layout(g, get(vertex_position, g));

   231   dump_graph_layout("cube-fr", g, get(vertex_position, g));

   232 }

   234 template<typename Graph>

   235 void

   236 test_triangular(Graph*)

   237 {

   238   enum {A, B, C, D, E, F, G, H, I, J};

   239   simple_edge triangular_edges[18] = {

   240     {A, B}, {A, C}, {B, C}, {B, D}, {B, E}, {C, E}, {C, F}, {D, E}, {D, G},

   241     {D, H}, {E, F}, {E, H}, {E, I}, {F, I}, {F, J}, {G, H}, {H, I}, {I, J}

   242   };

   244   Graph g(&triangular_edges[0], &triangular_edges[18], 10);

   246   typedef typename graph_traits<Graph>::edge_iterator edge_iterator;

   247   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

   249   vertex_iterator vi, vi_end;

   250   int i = 0;

   251   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

   252     put(vertex_index, g, *vi, i++);

   254   edge_iterator ei, ei_end;

   255   for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

   256     put(edge_weight, g, *ei, 1.0);

   257     std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')

   258               << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')

   259               << ") ";

   260   }

   261   std::cerr << std::endl;

   263   circle_graph_layout(g, get(vertex_position, g), 25.0);

   265   bool ok = kamada_kawai_spring_layout(g,

   266                                        get(vertex_position, g),

   267                                        get(edge_weight, g),

   268                                        side_length(50.0),

   269                                        kamada_kawai_done());

   270   BOOST_CHECK(ok);

   272   std::cout << "Triangular layout (Kamada-Kawai).\n";

   273   print_graph_layout(g, get(vertex_position, g));

   275   dump_graph_layout("triangular-kk", g, get(vertex_position, g));

   277   minstd_rand gen;

   278   random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,

   279                       gen);

   281   dump_graph_layout("random", g, get(vertex_position, g));

   283   std::vector<point> displacements(num_vertices(g));

   284   fruchterman_reingold_force_directed_layout

   285     (g,

   286      get(vertex_position, g),

   287      50.0,

   288      50.0,

   289      attractive_force(square_distance_attractive_force()).

   290      cooling(linear_cooling<double>(100)));

   292   std::cout << "Triangular layout (Fruchterman-Reingold).\n";

   293   print_graph_layout(g, get(vertex_position, g));

   295   dump_graph_layout("triangular-fr", g, get(vertex_position, g));

   296 }

   298 template<typename Graph>

   299 void

   300 test_disconnected(Graph*)

   301 {

   302   enum {A, B, C, D, E, F, G, H};

   303   simple_edge triangular_edges[13] = {

   304     {A, B}, {B, C}, {C, A},

   305     {D, E}, {E, F}, {F, G}, {G, H}, {H, D},

   306     {D, F}, {F, H}, {H, E}, {E, G}, {G, D}

   307   };

   309   Graph g(&triangular_edges[0], &triangular_edges[13], 8);

   311   typedef typename graph_traits<Graph>::edge_iterator edge_iterator;

   312   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;

   314   vertex_iterator vi, vi_end;

   315   int i = 0;

   316   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)

   317     put(vertex_index, g, *vi, i++);

   319   edge_iterator ei, ei_end;

   320   for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

   321     put(edge_weight, g, *ei, 1.0);

   322     std::cerr << "(" << (char)(get(vertex_index, g, source(*ei, g)) + 'A')

   323               << ", " << (char)(get(vertex_index, g, target(*ei, g)) + 'A')

   324               << ") ";

   325   }

   326   std::cerr << std::endl;

   328   circle_graph_layout(g, get(vertex_position, g), 25.0);

   330   bool ok = kamada_kawai_spring_layout(g,

   331                                        get(vertex_position, g),

   332                                        get(edge_weight, g),

   333                                        side_length(50.0),

   334                                        kamada_kawai_done());

   335   BOOST_CHECK(!ok);

   337   minstd_rand gen;

   338   random_graph_layout(g, get(vertex_position, g), -25.0, 25.0, -25.0, 25.0,

   339                       gen);

   341   std::vector<point> displacements(num_vertices(g));

   342   fruchterman_reingold_force_directed_layout

   343     (g,

   344      get(vertex_position, g),

   345      50.0,

   346      50.0,

   347      attractive_force(square_distance_attractive_force()).

   348      cooling(linear_cooling<double>(50)));

   350   std::cout << "Disconnected layout (Fruchterman-Reingold).\n";

   351   print_graph_layout(g, get(vertex_position, g));

   353   dump_graph_layout("disconnected-fr", g, get(vertex_position, g));

   354 }

   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;

   365   test_circle_layout((Graph*)0, 5);

   366   test_cube((Graph*)0);

   367   test_triangular((Graph*)0);

   368   test_disconnected((Graph*)0);

   370 #ifdef __SYMBIAN32__

   371 std_log(LOG_FILENAME_LINE,"[End Test Case ]");

   373 	testResultXml("layout_test");

   374 	close_log_file();

   375 #endif

   376   return 0;

   377 }

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--