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 | |
31 | position_writer(const Property& property) : property(property) {} |
32 | |
33 | 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 | { |
42 | 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 | |
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(g_&: 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 | u: verts[i][j], v: verts[i - 1][j], p: random_edge_weight(), g_&: graph); |
81 | if (j != 0) |
82 | add_edge( |
83 | u: verts[i][j], v: verts[i][j - 1], p: random_edge_weight(), g_&: 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(p: boost::vertex_index_t(), g&: 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(g_: 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, params: weight_map(p: get(p: boost::edge_weight, g&: 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 | |