ceph/src/boost/libs/graph/example/fr_layout.cpp

   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 }