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