]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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/topology.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 | { | |
f67539c2 TL |
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 " | |
35 | "per line.\n" | |
36 | << " Each edge contains two string labels (the endpoints) " | |
37 | "separated by a space.\n\n" | |
38 | << "Output:\n" | |
39 | << " Vertices and their positions are written to standard " | |
40 | "output with the label,\n x-position, and y-position of a " | |
41 | "vertex on each line, separated by spaces.\n"; | |
7c673cae FG |
42 | } |
43 | ||
44 | typedef boost::rectangle_topology<> topology_type; | |
45 | typedef topology_type::point_type point_type; | |
46 | ||
f67539c2 TL |
47 | typedef adjacency_list< listS, vecS, undirectedS, |
48 | property< vertex_name_t, std::string > > | |
49 | Graph; | |
7c673cae | 50 | |
f67539c2 | 51 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
7c673cae | 52 | |
f67539c2 | 53 | typedef std::map< std::string, Vertex > NameToVertex; |
7c673cae FG |
54 | |
55 | Vertex get_vertex(const std::string& name, Graph& g, NameToVertex& names) | |
56 | { | |
f67539c2 TL |
57 | NameToVertex::iterator i = names.find(name); |
58 | if (i == names.end()) | |
59 | i = names.insert(std::make_pair(name, add_vertex(name, g))).first; | |
60 | return i->second; | |
7c673cae FG |
61 | } |
62 | ||
f67539c2 | 63 | class progress_cooling : public linear_cooling< double > |
7c673cae | 64 | { |
f67539c2 TL |
65 | typedef linear_cooling< double > inherited; |
66 | ||
67 | public: | |
68 | explicit progress_cooling(std::size_t iterations) : inherited(iterations) | |
69 | { | |
70 | display.reset(new progress_display(iterations + 1, std::cerr)); | |
71 | } | |
72 | ||
73 | double operator()() | |
74 | { | |
75 | ++(*display); | |
76 | return inherited::operator()(); | |
77 | } | |
78 | ||
79 | private: | |
80 | shared_ptr< boost::progress_display > display; | |
7c673cae FG |
81 | }; |
82 | ||
83 | int main(int argc, char* argv[]) | |
84 | { | |
f67539c2 TL |
85 | int iterations = 100; |
86 | ||
87 | if (argc < 3) | |
88 | { | |
7c673cae FG |
89 | usage(); |
90 | return -1; | |
7c673cae | 91 | } |
f67539c2 TL |
92 | |
93 | double width = 0; | |
94 | double height = 0; | |
95 | ||
96 | for (int arg_idx = 1; arg_idx < argc; ++arg_idx) | |
97 | { | |
98 | std::string arg = argv[arg_idx]; | |
99 | if (arg == "--iterations") | |
100 | { | |
101 | ++arg_idx; | |
102 | if (arg_idx >= argc) | |
103 | { | |
104 | usage(); | |
105 | return -1; | |
106 | } | |
107 | iterations = lexical_cast< int >(argv[arg_idx]); | |
108 | } | |
109 | else | |
110 | { | |
111 | if (width == 0.0) | |
112 | width = lexical_cast< double >(arg); | |
113 | else if (height == 0.0) | |
114 | height = lexical_cast< double >(arg); | |
115 | else | |
116 | { | |
117 | usage(); | |
118 | return -1; | |
119 | } | |
120 | } | |
121 | } | |
122 | ||
123 | if (width == 0.0 || height == 0.0) | |
124 | { | |
125 | usage(); | |
126 | return -1; | |
127 | } | |
128 | ||
129 | Graph g; | |
130 | NameToVertex names; | |
131 | ||
132 | std::string source, target; | |
133 | while (std::cin >> source >> target) | |
134 | { | |
135 | add_edge(get_vertex(source, g, names), get_vertex(target, g, names), g); | |
136 | } | |
137 | ||
138 | typedef std::vector< point_type > PositionVec; | |
139 | PositionVec position_vec(num_vertices(g)); | |
140 | typedef iterator_property_map< PositionVec::iterator, | |
141 | property_map< Graph, vertex_index_t >::type > | |
142 | PositionMap; | |
143 | PositionMap position(position_vec.begin(), get(vertex_index, g)); | |
144 | ||
145 | minstd_rand gen; | |
146 | topology_type topo(gen, -width / 2, -height / 2, width / 2, height / 2); | |
147 | random_graph_layout(g, position, topo); | |
148 | fruchterman_reingold_force_directed_layout( | |
149 | g, position, topo, cooling(progress_cooling(iterations))); | |
150 | ||
151 | graph_traits< Graph >::vertex_iterator vi, vi_end; | |
152 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
153 | { | |
154 | std::cout << get(vertex_name, g, *vi) << '\t' << position[*vi][0] | |
155 | << '\t' << position[*vi][1] << std::endl; | |
156 | } | |
157 | return 0; | |
7c673cae | 158 | } |