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