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
usage()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 "
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";
42 }
43
44 typedef boost::rectangle_topology<> topology_type;
45 typedef topology_type::point_type point_type;
46
47 typedef adjacency_list< listS, vecS, undirectedS,
48 property< vertex_name_t, std::string > >
49 Graph;
50
51 typedef graph_traits< Graph >::vertex_descriptor Vertex;
52
53 typedef std::map< std::string, Vertex > NameToVertex;
54
get_vertex(const std::string & name,Graph & g,NameToVertex & names)55 Vertex get_vertex(const std::string& name, Graph& g, NameToVertex& names)
56 {
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;
61 }
62
63 class progress_cooling : public linear_cooling< double >
64 {
65 typedef linear_cooling< double > inherited;
66
67 public:
progress_cooling(std::size_t iterations)68 explicit progress_cooling(std::size_t iterations) : inherited(iterations)
69 {
70 display.reset(new progress_display(iterations + 1, std::cerr));
71 }
72
operator ()()73 double operator()()
74 {
75 ++(*display);
76 return inherited::operator()();
77 }
78
79 private:
80 shared_ptr< boost::progress_display > display;
81 };
82
main(int argc,char * argv[])83 int main(int argc, char* argv[])
84 {
85 int iterations = 100;
86
87 if (argc < 3)
88 {
89 usage();
90 return -1;
91 }
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;
158 }
159