1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
// 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: Douglas Gregor
// Andrew Lumsdaine
#include <boost/graph/fruchterman_reingold.hpp>
#include <boost/graph/random_layout.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/simple_point.hpp>
#include <boost/lexical_cast.hpp>
#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <boost/random/linear_congruential.hpp>
#include <boost/progress.hpp>
#include <boost/shared_ptr.hpp>
using namespace boost;
void usage()
{
std::cerr << "Usage: fr_layout [options] <width> <height>\n"
<< "Arguments:\n"
<< "\t<width>\tWidth of the display area (floating point)\n"
<< "\t<Height>\tHeight of the display area (floating point)\n\n"
<< "Options:\n"
<< "\t--iterations n\tNumber of iterations to execute.\n"
<< "\t\t\tThe default value is 100.\n"
<< "Input:\n"
<< " Input is read from standard input as a list of edges, one per line.\n"
<< " Each edge contains two string labels (the endpoints) separated by a space.\n\n"
<< "Output:\n"
<< " Vertices and their positions are written to standard output with the label,\n x-position, and y-position of a vertex on each line, separated by spaces.\n";
}
typedef adjacency_list<listS, vecS, undirectedS,
property<vertex_name_t, std::string> > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef std::map<std::string, Vertex> NameToVertex;
Vertex get_vertex(const std::string& name, Graph& g, NameToVertex& names)
{
NameToVertex::iterator i = names.find(name);
if (i == names.end())
i = names.insert(std::make_pair(name, add_vertex(name, g))).first;
return i->second;
}
class progress_cooling : public linear_cooling<double>
{
typedef linear_cooling<double> inherited;
public:
explicit progress_cooling(std::size_t iterations) : inherited(iterations)
{
display.reset(new progress_display(iterations + 1, std::cerr));
}
double operator()()
{
++(*display);
return inherited::operator()();
}
private:
shared_ptr<boost::progress_display> display;
};
int main(int argc, char* argv[])
{
int iterations = 100;
if (argc < 3) { usage(); return -1; }
double width = 0;
double height = 0;
for (int arg_idx = 1; arg_idx < argc; ++arg_idx) {
std::string arg = argv[arg_idx];
if (arg == "--iterations") {
++arg_idx;
if (arg_idx >= argc) { usage(); return -1; }
iterations = lexical_cast<int>(argv[arg_idx]);
} else {
if (width == 0.0) width = lexical_cast<double>(arg);
else if (height == 0.0) height = lexical_cast<double>(arg);
else {
usage();
return -1;
}
}
}
if (width == 0.0 || height == 0.0) {
usage();
return -1;
}
Graph g;
NameToVertex names;
std::string source, target;
while (std::cin >> source >> target) {
add_edge(get_vertex(source, g, names), get_vertex(target, g, names), g);
}
typedef std::vector<simple_point<double> > PositionVec;
PositionVec position_vec(num_vertices(g));
typedef iterator_property_map<PositionVec::iterator,
property_map<Graph, vertex_index_t>::type>
PositionMap;
PositionMap position(position_vec.begin(), get(vertex_index, g));
minstd_rand gen;
random_graph_layout(g, position, -width/2, width/2, -height/2, height/2, gen);
fruchterman_reingold_force_directed_layout
(g, position, width, height,
cooling(progress_cooling(iterations)));
graph_traits<Graph>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
std::cout << get(vertex_name, g, *vi) << '\t'
<< position[*vi].x << '\t' << position[*vi].y << std::endl;
}
return 0;
}
|
