]>
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 | { | |
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 boost::rectangle_topology<> topology_type; | |
41 | typedef topology_type::point_type point_type; | |
42 | ||
43 | typedef adjacency_list<listS, vecS, undirectedS, | |
44 | property<vertex_name_t, std::string> > Graph; | |
45 | ||
46 | typedef graph_traits<Graph>::vertex_descriptor Vertex; | |
47 | ||
48 | typedef std::map<std::string, Vertex> NameToVertex; | |
49 | ||
50 | Vertex get_vertex(const std::string& name, Graph& g, NameToVertex& names) | |
51 | { | |
52 | NameToVertex::iterator i = names.find(name); | |
53 | if (i == names.end()) | |
54 | i = names.insert(std::make_pair(name, add_vertex(name, g))).first; | |
55 | return i->second; | |
56 | } | |
57 | ||
58 | class progress_cooling : public linear_cooling<double> | |
59 | { | |
60 | typedef linear_cooling<double> inherited; | |
61 | ||
62 | public: | |
63 | explicit progress_cooling(std::size_t iterations) : inherited(iterations) | |
64 | { | |
65 | display.reset(new progress_display(iterations + 1, std::cerr)); | |
66 | } | |
67 | ||
68 | double operator()() | |
69 | { | |
70 | ++(*display); | |
71 | return inherited::operator()(); | |
72 | } | |
73 | ||
74 | private: | |
75 | shared_ptr<boost::progress_display> display; | |
76 | }; | |
77 | ||
78 | int main(int argc, char* argv[]) | |
79 | { | |
80 | int iterations = 100; | |
81 | ||
82 | if (argc < 3) { usage(); return -1; } | |
83 | ||
84 | double width = 0; | |
85 | double height = 0; | |
86 | ||
87 | for (int arg_idx = 1; arg_idx < argc; ++arg_idx) { | |
88 | std::string arg = argv[arg_idx]; | |
89 | if (arg == "--iterations") { | |
90 | ++arg_idx; | |
91 | if (arg_idx >= argc) { usage(); return -1; } | |
92 | iterations = lexical_cast<int>(argv[arg_idx]); | |
93 | } else { | |
94 | if (width == 0.0) width = lexical_cast<double>(arg); | |
95 | else if (height == 0.0) height = lexical_cast<double>(arg); | |
96 | else { | |
97 | usage(); | |
98 | return -1; | |
99 | } | |
100 | } | |
101 | } | |
102 | ||
103 | if (width == 0.0 || height == 0.0) { | |
104 | usage(); | |
105 | return -1; | |
106 | } | |
107 | ||
108 | Graph g; | |
109 | NameToVertex names; | |
110 | ||
111 | std::string source, target; | |
112 | while (std::cin >> source >> target) { | |
113 | add_edge(get_vertex(source, g, names), get_vertex(target, g, names), g); | |
114 | } | |
115 | ||
116 | typedef std::vector<point_type> PositionVec; | |
117 | PositionVec position_vec(num_vertices(g)); | |
118 | typedef iterator_property_map<PositionVec::iterator, | |
119 | property_map<Graph, vertex_index_t>::type> | |
120 | PositionMap; | |
121 | PositionMap position(position_vec.begin(), get(vertex_index, g)); | |
122 | ||
123 | minstd_rand gen; | |
124 | topology_type topo(gen, -width/2, -height/2, width/2, height/2); | |
125 | random_graph_layout(g, position, topo); | |
126 | fruchterman_reingold_force_directed_layout | |
127 | (g, position, topo, | |
128 | cooling(progress_cooling(iterations))); | |
129 | ||
130 | graph_traits<Graph>::vertex_iterator vi, vi_end; | |
131 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { | |
132 | std::cout << get(vertex_name, g, *vi) << '\t' | |
133 | << position[*vi][0] << '\t' << position[*vi][1] << std::endl; | |
134 | } | |
135 | return 0; | |
136 | } |