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;
}