boost_1_45_0/libs/graph/test/gursoy_atun_layout_test.cpp

// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Jeremiah Willcock
//           Douglas Gregor
//           Andrew Lumsdaine
#include <boost/graph/gursoy_atun_layout.hpp>
#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/random.hpp"
#include "boost/graph/graphviz.hpp"
#include "boost/random/mersenne_twister.hpp"
#include "boost/random/linear_congruential.hpp"
#include "boost/random/uniform_01.hpp"
#include <iostream>
#include <fstream>
#include <sstream>

#if 0
#include <boost/graph/plod_generator.hpp>
#include <boost/graph/small_world_generator.hpp>
#endif
using namespace boost;

template <class Property, class Vertex>
struct position_writer {
  const Property& property;

  position_writer(const Property& property): property(property) {}

  void operator()(std::ostream& os, const Vertex& v) const {
    os << "[pos=\"" << int(property[v][0]) << "," << int(property[v][1]) << "\"]";
  }
};

struct graph_writer {
  void operator()(std::ostream& os) const {
    os << "node [shape=point, width=\".01\", height=\".01\", fixedsize=\"true\"]"
       << std::endl;
  }
};

int main(int, char*[]) {
  // Generate a graph structured like a grid, cylinder, or torus; lay it out in
  // a square grid; and output it in dot format

  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
                                boost::no_property, 
                                boost::property<boost::edge_weight_t, double>
                                > graph_type;
  typedef boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
  // boost::mt19937 rng;
  // boost::generate_random_graph(graph, 100, 600, rng, false, false);

#if 1
  graph_type graph;

  // Make grid, like Gursoy and Atun used
  std::map<int, std::map<int, vertex_descriptor> > verts;
  const int grid_size = 20;
  boost::minstd_rand edge_weight_gen;
  boost::uniform_01<boost::minstd_rand> random_edge_weight(edge_weight_gen);
  for (int i = 0; i < grid_size; ++i)
    for (int j = 0; j < grid_size; ++j)
      verts[i][j] = add_vertex(graph);
  for (int i = 0; i < grid_size; ++i) {
    for (int j = 0; j < grid_size; ++j) {
      if (i != 0)
        add_edge(verts[i][j], verts[i-1][j], random_edge_weight(), graph);
      if (j != 0)
        add_edge(verts[i][j], verts[i][j-1], random_edge_weight(), graph);
#if 0
      // Uncomment parts of this to get a cylinder or torus
      if (i == 0)
        add_edge(verts[0][j], verts[grid_size-1][j], random_edge_weight(), 
                 graph);
      if (j == 0)
        add_edge(verts[i][0], verts[i][grid_size-1], random_edge_weight(), 
                 graph);
#endif
    }
  }
#else
  using namespace boost;

#if 0
  int n = 10000;
  double alpha = 0.4;
  double beta = 50;
  minstd_rand gen;
  graph_type graph(plod_iterator<minstd_rand, graph_type>(gen, n, alpha, beta),
                   plod_iterator<minstd_rand, graph_type>(),
                   n);
#else 
  int n = 1000;
  int k = 6;
  double p = 0.001;
  minstd_rand gen;
  graph_type graph(small_world_iterator<minstd_rand>(gen, n, k, p),
                   small_world_iterator<minstd_rand>(n, k),
                   n);
#endif
#endif
  // boost::read_graphviz(stdin, graph);

  typedef boost::property_map<graph_type, boost::vertex_index_t>::type 
    VertexIndexMap;
  VertexIndexMap vertex_index = get(boost::vertex_index_t(), graph);

  typedef boost::heart_topology<> topology;
  topology space;

  typedef topology::point_type point;
  std::vector<point> position_vector(num_vertices(graph));
  typedef boost::iterator_property_map<std::vector<point>::iterator,
                                       VertexIndexMap, point, point&> Position;
  Position position(position_vector.begin(), vertex_index);

  boost::gursoy_atun_layout(graph, space, position);

#if 0
  std::cerr << "--------Unweighted layout--------\n";
  boost::write_graphviz(std::cout, graph, 
                        position_writer<Position, vertex_descriptor>(position),
                        boost::default_writer(),
                        graph_writer());
#endif

  boost::gursoy_atun_layout(graph, space, position,
                            weight_map(get(boost::edge_weight, graph)));

#if 0
  std::cerr << "--------Weighted layout--------\n";
  boost::write_graphviz(std::cout, graph, 
                        position_writer<Position, vertex_descriptor>(position),
                        boost::default_writer(),
                        graph_writer());
#endif
  return 0;
}