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