// 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/topology.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 boost::rectangle_topology<> topology_type; typedef topology_type::point_type point_type; 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<point_type> 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; topology_type topo(gen, -width/2, -height/2, width/2, height/2); random_graph_layout(g, position, topo); fruchterman_reingold_force_directed_layout (g, position, topo, cooling(progress_cooling(iterations))); graph_traits<Graph>::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) { std::cout << get(vertex_name, g, *vi) << '\t' << position[*vi][0] << '\t' << position[*vi][1] << std::endl; } return 0; }