ceph/src/boost/libs/graph/test/gursoy_atun_layout_test.cpp

   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: Jeremiah Willcock
   8 //           Douglas Gregor
   9 //           Andrew Lumsdaine
  10 #include <boost/graph/gursoy_atun_layout.hpp>
  11 #include "boost/graph/adjacency_list.hpp"
  12 #include "boost/graph/random.hpp"
  13 #include "boost/graph/graphviz.hpp"
  14 #include "boost/random/mersenne_twister.hpp"
  15 #include "boost/random/linear_congruential.hpp"
  16 #include "boost/random/uniform_01.hpp"
  17 #include <iostream>
  18 #include <fstream>
  19 #include <sstream>
  20
  21 #if 0
  22 #include <boost/graph/plod_generator.hpp>
  23 #include <boost/graph/small_world_generator.hpp>
  24 #endif
  25 using namespace boost;
  26
  27 template <class Property, class Vertex>
  28 struct position_writer {
  29   const Property& property;
  30
  31   position_writer(const Property& property): property(property) {}
  32
  33   void operator()(std::ostream& os, const Vertex& v) const {
  34     os << "[pos=\"" << int(property[v][0]) << "," << int(property[v][1]) << "\"]";
  35   }
  36 };
  37
  38 struct graph_writer {
  39   void operator()(std::ostream& os) const {
  40     os << "node [shape=point, width=\".01\", height=\".01\", fixedsize=\"true\"]"
  41        << std::endl;
  42   }
  43 };
  44
  45 int main(int, char*[]) {
  46   // Generate a graph structured like a grid, cylinder, or torus; lay it out in
  47   // a square grid; and output it in dot format
  48
  49   typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
  50                                 boost::no_property,
  51                                 boost::property<boost::edge_weight_t, double>
  52                                 > graph_type;
  53   typedef boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
  54   // boost::mt19937 rng;
  55   // boost::generate_random_graph(graph, 100, 600, rng, false, false);
  56
  57 #if 1
  58   graph_type graph;
  59
  60   // Make grid, like Gursoy and Atun used
  61   std::map<int, std::map<int, vertex_descriptor> > verts;
  62   const int grid_size = 20;
  63   boost::minstd_rand edge_weight_gen;
  64   boost::uniform_01<boost::minstd_rand> random_edge_weight(edge_weight_gen);
  65   for (int i = 0; i < grid_size; ++i)
  66     for (int j = 0; j < grid_size; ++j)
  67       verts[i][j] = add_vertex(graph);
  68   for (int i = 0; i < grid_size; ++i) {
  69     for (int j = 0; j < grid_size; ++j) {
  70       if (i != 0)
  71         add_edge(verts[i][j], verts[i-1][j], random_edge_weight(), graph);
  72       if (j != 0)
  73         add_edge(verts[i][j], verts[i][j-1], random_edge_weight(), graph);
  74 #if 0
  75       // Uncomment parts of this to get a cylinder or torus
  76       if (i == 0)
  77         add_edge(verts[0][j], verts[grid_size-1][j], random_edge_weight(),
  78                  graph);
  79       if (j == 0)
  80         add_edge(verts[i][0], verts[i][grid_size-1], random_edge_weight(),
  81                  graph);
  82 #endif
  83     }
  84   }
  85 #else
  86   using namespace boost;
  87
  88 #if 0
  89   int n = 10000;
  90   double alpha = 0.4;
  91   double beta = 50;
  92   minstd_rand gen;
  93   graph_type graph(plod_iterator<minstd_rand, graph_type>(gen, n, alpha, beta),
  94                    plod_iterator<minstd_rand, graph_type>(),
  95                    n);
  96 #else
  97   int n = 1000;
  98   int k = 6;
  99   double p = 0.001;
 100   minstd_rand gen;
 101   graph_type graph(small_world_iterator<minstd_rand>(gen, n, k, p),
 102                    small_world_iterator<minstd_rand>(n, k),
 103                    n);
 104 #endif
 105 #endif
 106   // boost::read_graphviz(stdin, graph);
 107
 108   typedef boost::property_map<graph_type, boost::vertex_index_t>::type
 109     VertexIndexMap;
 110   VertexIndexMap vertex_index = get(boost::vertex_index_t(), graph);
 111
 112   typedef boost::heart_topology<> topology;
 113   topology space;
 114
 115   typedef topology::point_type point;
 116   std::vector<point> position_vector(num_vertices(graph));
 117   typedef boost::iterator_property_map<std::vector<point>::iterator,
 118                                        VertexIndexMap, point, point&> Position;
 119   Position position(position_vector.begin(), vertex_index);
 120
 121   boost::gursoy_atun_layout(graph, space, position);
 122
 123 #if 0
 124   std::cerr << "--------Unweighted layout--------\n";
 125   boost::write_graphviz(std::cout, graph,
 126                         position_writer<Position, vertex_descriptor>(position),
 127                         boost::default_writer(),
 128                         graph_writer());
 129 #endif
 130
 131   boost::gursoy_atun_layout(graph, space, position,
 132                             weight_map(get(boost::edge_weight, graph)));
 133
 134 #if 0
 135   std::cerr << "--------Weighted layout--------\n";
 136   boost::write_graphviz(std::cout, graph,
 137                         position_writer<Position, vertex_descriptor>(position),
 138                         boost::default_writer(),
 139                         graph_writer());
 140 #endif
 141   return 0;
 142 }