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
25using namespace boost;
26
27template < 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
40struct 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
50int 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

source code of boost/libs/graph/test/gursoy_atun_layout_test.cpp