143 lines
4.6 KiB
C++
143 lines
4.6 KiB
C++
// 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;
|
|
}
|