1 | #include <boost/graph/graph_traits.hpp>
|
---|
2 | #include <boost/graph/adjacency_list.hpp>
|
---|
3 | #include <boost/graph/circle_layout.hpp>
|
---|
4 | #include <boost/graph/kamada_kawai_spring_layout.hpp>
|
---|
5 |
|
---|
6 | enum vertex_position_t { vertex_position };
|
---|
7 | namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }
|
---|
8 |
|
---|
9 | typedef boost::rectangle_topology<> RectangleTopology;
|
---|
10 | typedef boost::rectangle_topology<>::point_type Point;
|
---|
11 |
|
---|
12 | typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,
|
---|
13 | // Vertex properties
|
---|
14 | boost::property<boost::vertex_index_t, int,
|
---|
15 | boost::property<vertex_position_t, Point> >,
|
---|
16 | // Edge properties
|
---|
17 | boost::property<boost::edge_weight_t, double> > Graph;
|
---|
18 |
|
---|
19 | typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescriptor;
|
---|
20 | typedef boost::graph_traits<Graph>::vertex_iterator VertexIterator;
|
---|
21 | typedef boost::graph_traits<Graph>::vertices_size_type VerticesSizeType;
|
---|
22 | typedef boost::graph_traits<Graph>::edge_descriptor EdgeDescriptor;
|
---|
23 | typedef boost::graph_traits<Graph>::edge_iterator EdgeIterator;
|
---|
24 | typedef boost::graph_traits<Graph>::edges_size_type EdgesSizeType;
|
---|
25 |
|
---|
26 | struct kamada_kawai_done
|
---|
27 | {
|
---|
28 | kamada_kawai_done(int maxGlobalIterations = 100, int maxLocalIterations = 1000)
|
---|
29 | : lastDelta_()
|
---|
30 | , maxGlobalIterations_(maxGlobalIterations)
|
---|
31 | , globalIterations_(0)
|
---|
32 | , maxLocalIterations_(maxLocalIterations)
|
---|
33 | , localIterations_(0)
|
---|
34 | {}
|
---|
35 |
|
---|
36 | template<typename Graph>
|
---|
37 | bool operator()(double delta_p,
|
---|
38 | typename boost::graph_traits<Graph>::vertex_descriptor /*p*/,
|
---|
39 | const Graph& /*g*/,
|
---|
40 | bool global)
|
---|
41 | {
|
---|
42 | //qDebug() << "Iteration =" << globalIterations_ << "/" << localIterations_;
|
---|
43 | if(globalIterations_ >= maxGlobalIterations_
|
---|
44 | || localIterations_ >= maxLocalIterations_)
|
---|
45 | return true;
|
---|
46 |
|
---|
47 | if (global)
|
---|
48 | {
|
---|
49 | double diff = lastDelta_ - delta_p;
|
---|
50 | if (diff < 0) diff = -diff;
|
---|
51 | lastDelta_ = delta_p;
|
---|
52 | ++globalIterations_;
|
---|
53 | localIterations_ = 0;
|
---|
54 | return diff < 0.01;
|
---|
55 | }
|
---|
56 | else
|
---|
57 | {
|
---|
58 | ++localIterations_;
|
---|
59 | return delta_p < 0.01;
|
---|
60 | }
|
---|
61 | }
|
---|
62 |
|
---|
63 | double lastDelta_;
|
---|
64 | int maxGlobalIterations_;
|
---|
65 | int globalIterations_;
|
---|
66 | int maxLocalIterations_;
|
---|
67 | int localIterations_;
|
---|
68 | };
|
---|
69 |
|
---|
70 | int main()
|
---|
71 | {
|
---|
72 | // Create a simple graph
|
---|
73 | Graph graph(3);
|
---|
74 |
|
---|
75 | VertexIterator vi = boost::vertices(graph).first;
|
---|
76 | std::vector<VertexDescriptor> vertices;
|
---|
77 | for(int i = 0; i < 3; ++i, ++vi)
|
---|
78 | {
|
---|
79 | boost::put(boost::vertex_index, graph, *vi, static_cast<size_t>(i));
|
---|
80 | Point p;
|
---|
81 | p[0] = 10*(i+1);
|
---|
82 | p[1] = 20*(i+2);
|
---|
83 | boost::put(vertex_position, graph, *vi, p);
|
---|
84 | vertices.push_back(*vi);
|
---|
85 | }
|
---|
86 |
|
---|
87 | std::pair<EdgeDescriptor, bool> result;
|
---|
88 |
|
---|
89 | result = boost::add_edge(vertices[0], vertices[1], graph);
|
---|
90 | boost::put(boost::edge_weight, graph, result.first, 1.0);
|
---|
91 |
|
---|
92 | result = boost::add_edge(vertices[0], vertices[2], graph);
|
---|
93 | boost::put(boost::edge_weight, graph, result.first, 1.0);
|
---|
94 |
|
---|
95 | // Create a simple rectangular topology to layout within
|
---|
96 | boost::minstd_rand randomGenerator;
|
---|
97 | randomGenerator.seed(time(0));
|
---|
98 |
|
---|
99 | RectangleTopology layoutTopology(randomGenerator, 0.0, 0.0, 19.18, 14.29);
|
---|
100 |
|
---|
101 | boost::circle_graph_layout(graph, boost::get(vertex_position, graph), 100.0);
|
---|
102 | boost::kamada_kawai_spring_layout(graph,
|
---|
103 | boost::get(vertex_position, graph),
|
---|
104 | boost::get(boost::edge_weight, graph),
|
---|
105 | layoutTopology,
|
---|
106 | boost::edge_length(3.0),
|
---|
107 | kamada_kawai_done());
|
---|
108 |
|
---|
109 | return 0;
|
---|
110 | }
|
---|