123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136 |
- // 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;
- }
|