graph/distributed/graphviz.hpp

0001 // Copyright (C) 2004-2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_PARALLEL_GRAPHVIZ_HPP
0010 #define BOOST_GRAPH_PARALLEL_GRAPHVIZ_HPP
0011
0012 #ifndef BOOST_GRAPH_USE_MPI
0013 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0014 #endif
0015
0016 #include <boost/graph/graph_traits.hpp>
0017 #include <boost/graph/distributed/concepts.hpp>
0018 #include <boost/property_map/property_map.hpp>
0019 #include <boost/property_map/parallel/parallel_property_maps.hpp>
0020 #include <boost/graph/graphviz.hpp>
0021 #include <boost/type_traits/is_base_and_derived.hpp>
0022 #include <boost/type_traits/is_same.hpp>
0023 #include <fstream>
0024 #include <sstream>
0025 #include <iostream>
0026 #include <string>
0027 #include <boost/graph/parallel/container_traits.hpp>
0028 #include <boost/graph/parallel/process_group.hpp>
0029 #include <boost/property_map/parallel/global_index_map.hpp>
0030
0031 namespace boost {
0032
0033 template<typename Graph>
0034 struct graph_id_writer
0035 {
0036   explicit graph_id_writer(const Graph& g) : g(g) { }
0037
0038   void operator()(std::ostream& out)
0039   {
0040     out << "    label=\"p" << process_id(g.process_group()) << "\";\n";
0041   }
0042
0043  private:
0044   const Graph& g;
0045 };
0046
0047 template<typename NumberMap>
0048 struct paint_by_number_writer
0049 {
0050   explicit paint_by_number_writer(NumberMap number) : number(number) { }
0051
0052   template<typename Descriptor>
0053   void operator()(std::ostream& out, Descriptor k)
0054   {
0055     static const char* color_names[] = {
0056       "blue",
0057       "brown",
0058       "cyan",
0059       "darkgreen",
0060       "darkorchid",
0061       "darksalmon",
0062       "darkviolet",
0063       "deeppink",
0064       "gold3",
0065       "green",
0066       "magenta",
0067       "navy",
0068       "red",
0069       "yellow",
0070       "palegreen",
0071       "gray65",
0072       "gray21",
0073       "bisque2",
0074       "greenyellow",
0075       "indianred4",
0076       "lightblue2",
0077       "mediumspringgreen",
0078       "orangered",
0079       "orange"
0080     };
0081     const int colors = sizeof(color_names) / sizeof(color_names[0]);
0082     if (get(number, k) < colors) {
0083       out << " [ style=\"filled\", fillcolor=\"" << color_names[get(number, k)]
0084           << "\" ]";
0085     } else {
0086       out << " [ label=\"(" << get(number, k) << ")\" ]";
0087     }
0088   }
0089
0090  private:
0091   NumberMap number;
0092 };
0093
0094 template<typename NumberMap>
0095 inline paint_by_number_writer<NumberMap>
0096 paint_by_number(NumberMap number)
0097 { return paint_by_number_writer<NumberMap>(number); }
0098
0099 template<typename Graph, typename VertexPropertiesWriter,
0100          typename EdgePropertiesWriter, typename GraphPropertiesWriter>
0101 void
0102 write_graphviz(std::ostream& out,
0103                const Graph& g,
0104                VertexPropertiesWriter vpw,
0105                EdgePropertiesWriter epw,
0106                GraphPropertiesWriter gpw
0107                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0108 {
0109   typedef typename graph_traits<Graph>::directed_category directed_category;
0110   typedef typename boost::graph::parallel::process_group_type<Graph>::type
0111     process_group_type;
0112   typedef typename property_map<Graph, vertex_index_t>::const_type
0113     VertexIndexMap;
0114   typedef typename property_map<Graph, vertex_global_t>::const_type
0115     VertexGlobalMap;
0116
0117   static const bool is_undirected
0118     = (is_base_and_derived<undirected_tag, directed_category>::value
0119        || is_same<undirected_tag, directed_category>::value);
0120   static const char* graph_kind = is_undirected? "graph" : "digraph";
0121   static const char* edge_kind = is_undirected? "--" : "->";
0122
0123   using boost::graph::parallel::process_group;
0124   process_group_type pg = process_group(g);
0125
0126   parallel::global_index_map<VertexIndexMap, VertexGlobalMap>
0127     global_index(pg, num_vertices(g), get(vertex_index, g),
0128                  get(vertex_global, g));
0129
0130   std::ostringstream local_graph_out;
0131
0132   local_graph_out << "  subgraph cluster_" << process_id(pg) << " {\n";
0133   gpw(local_graph_out);
0134
0135   typename graph_traits<Graph>::vertex_iterator vi, vi_end;
0136   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
0137
0138     int global_idx = get(global_index, *vi);
0139     local_graph_out << "    n" << global_idx;
0140     vpw(local_graph_out, *vi);
0141     local_graph_out << ";\n";
0142   }
0143   local_graph_out << "  }\n\n";
0144
0145
0146   typename graph_traits<Graph>::edge_iterator ei, ei_end;
0147   for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
0148     int source_idx = get(global_index, source(*ei, g));
0149     int target_idx = get(global_index, target(*ei, g));
0150     local_graph_out << "  n" << source_idx << " " << edge_kind << " n"
0151                     << target_idx;
0152     epw(local_graph_out, *ei);
0153     local_graph_out << ";\n";
0154   }
0155
0156   if (process_id(pg) == 0) {
0157     out << graph_kind << " g {\n";
0158     out << local_graph_out.str();
0159
0160     synchronize(pg);
0161     for (int i = 1; i < num_processes(pg); ++i) {
0162       int len;
0163       receive(pg, i, 0, len);
0164       char* data = new char [len+1];
0165       data[len] = 0;
0166       receive(pg, i, 1, data, len);
0167       out << std::endl << data;
0168       delete [] data;
0169     }
0170     out << "}\n";
0171   } else {
0172     std::string result_str = local_graph_out.str();
0173     const char* data = result_str.c_str();
0174
0175     int len = result_str.length();
0176     send(pg, 0, 0, len);
0177     send(pg, 0, 1, data, len);
0178     synchronize(pg);
0179   }
0180   synchronize(pg);
0181   synchronize(pg);
0182   synchronize(pg);
0183 }
0184
0185 template<typename Graph, typename VertexPropertiesWriter,
0186          typename EdgePropertiesWriter>
0187 inline void
0188 write_graphviz(std::ostream& out,
0189                const Graph& g,
0190                VertexPropertiesWriter vpw,
0191                EdgePropertiesWriter epw
0192                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0193 {
0194   write_graphviz(out, g, vpw, epw, graph_id_writer<Graph>(g));
0195 }
0196
0197 template<typename Graph, typename VertexPropertiesWriter>
0198 inline void
0199 write_graphviz(std::ostream& out,
0200                const Graph& g,
0201                VertexPropertiesWriter vpw
0202                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0203 {
0204   write_graphviz(out, g, vpw, default_writer());
0205 }
0206
0207 template<typename Graph>
0208 inline void
0209 write_graphviz(std::ostream& out, const Graph& g
0210                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0211 {
0212   write_graphviz(out, g, default_writer());
0213 }
0214
0215 template<typename Graph, typename VertexPropertiesWriter,
0216          typename EdgePropertiesWriter, typename GraphPropertiesWriter>
0217 void
0218 write_graphviz(const std::string& filename,
0219                const Graph& g,
0220                VertexPropertiesWriter vpw,
0221                EdgePropertiesWriter epw,
0222                GraphPropertiesWriter gpw
0223                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0224 {
0225   if (process_id(g.process_group()) == 0) {
0226     std::ofstream out(filename.c_str());
0227     write_graphviz(out, g, vpw, epw, gpw);
0228   } else {
0229     write_graphviz(std::cout, g, vpw, epw, gpw);
0230   }
0231 }
0232
0233 template<typename Graph, typename VertexPropertiesWriter,
0234          typename EdgePropertiesWriter>
0235 void
0236 write_graphviz(const std::string& filename,
0237                const Graph& g,
0238                VertexPropertiesWriter vpw,
0239                EdgePropertiesWriter epw
0240                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0241 {
0242   if (process_id(g.process_group()) == 0) {
0243     std::ofstream out(filename.c_str());
0244     write_graphviz(out, g, vpw, epw);
0245   } else {
0246     write_graphviz(std::cout, g, vpw, epw);
0247   }
0248 }
0249
0250 template<typename Graph, typename VertexPropertiesWriter>
0251 void
0252 write_graphviz(const std::string& filename,
0253                const Graph& g,
0254                VertexPropertiesWriter vpw
0255                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0256 {
0257   if (process_id(g.process_group()) == 0) {
0258     std::ofstream out(filename.c_str());
0259     write_graphviz(out, g, vpw);
0260   } else {
0261     write_graphviz(std::cout, g, vpw);
0262   }
0263 }
0264
0265 template<typename Graph>
0266 void
0267 write_graphviz(const std::string& filename, const Graph& g
0268                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0269 {
0270   if (process_id(g.process_group()) == 0) {
0271     std::ofstream out(filename.c_str());
0272     write_graphviz(out, g);
0273   } else {
0274     write_graphviz(std::cout, g);
0275   }
0276 }
0277
0278 template<typename Graph>
0279 void
0280 write_graphviz(std::ostream& out, const Graph& g,
0281                const dynamic_properties& dp,
0282                const std::string& node_id = "node_id"
0283                BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,distributed_graph_tag))
0284 {
0285   write_graphviz
0286     (out, g,
0287      /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),
0288      /*edge_writer=*/dynamic_properties_writer(dp));
0289 }
0290
0291 } // end namespace boost
0292
0293 #endif // BOOST_GRAPH_PARALLEL_GRAPHVIZ_HPP