boost/graph/graphviz.hpp

   1 //=======================================================================
   2 // Copyright 2001 University of Notre Dame.
   3 // Copyright 2003 Jeremy Siek
   4 // Authors: Lie-Quan Lee, Jeremy Siek, and Douglas Gregor
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 #ifndef BOOST_GRAPHVIZ_HPP
  11 #define BOOST_GRAPHVIZ_HPP
  12
  13 #include <boost/config.hpp>
  14 #include <string>
  15 #include <map>
  16 #include <iostream>
  17 #include <fstream>
  18 #include <stdio.h> // for FILE
  19 #include <boost/property_map/property_map.hpp>
  20 #include <boost/tuple/tuple.hpp>
  21 #include <boost/graph/graph_traits.hpp>
  22 #include <boost/graph/properties.hpp>
  23 #include <boost/graph/subgraph.hpp>
  24 #include <boost/graph/adjacency_list.hpp>
  25 #include <boost/property_map/dynamic_property_map.hpp>
  26 #include <boost/graph/overloading.hpp>
  27
  28 #ifdef BOOST_HAS_DECLSPEC
  29 #  if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_GRAPH_DYN_LINK)
  30 #    ifdef BOOST_GRAPH_SOURCE
  31 #      define BOOST_GRAPH_DECL __declspec(dllexport)
  32 #    else
  33 #      define BOOST_GRAPH_DECL __declspec(dllimport)
  34 #    endif  // BOOST_GRAPH_SOURCE
  35 #  endif  // DYN_LINK
  36 #endif  // BOOST_HAS_DECLSPEC
  37
  38 #ifndef BOOST_GRAPH_DECL
  39 #  define BOOST_GRAPH_DECL
  40 #endif
  41
  42 namespace boost {
  43
  44   template <typename directed_category>
  45   struct graphviz_io_traits {
  46     static std::string name() {
  47       return "digraph";
  48     }
  49     static std::string delimiter() {
  50       return "->";
  51     }  };
  52
  53   template <>
  54   struct graphviz_io_traits <undirected_tag> {
  55     static std::string name() {
  56       return "graph";
  57     }
  58     static std::string delimiter() {
  59       return "--";
  60     }
  61   };
  62
  63   struct default_writer {
  64     void operator()(std::ostream&) const {
  65     }
  66     template <class VorE>
  67     void operator()(std::ostream&, const VorE&) const {
  68     }
  69   };
  70
  71   template <class Name>
  72   class label_writer {
  73   public:
  74     label_writer(Name _name) : name(_name) {}
  75     template <class VertexOrEdge>
  76     void operator()(std::ostream& out, const VertexOrEdge& v) const {
  77       out << "[label=\"" << get(name, v) << "\"]";
  78     }
  79   private:
  80     Name name;
  81   };
  82   template <class Name>
  83   inline label_writer<Name>
  84   make_label_writer(Name n) {
  85     return label_writer<Name>(n);
  86   }
  87
  88   enum edge_attribute_t        { edge_attribute        = 1111 };
  89   enum vertex_attribute_t      { vertex_attribute      = 2222 };
  90   enum graph_graph_attribute_t { graph_graph_attribute = 3333 };
  91   enum graph_vertex_attribute_t  { graph_vertex_attribute  = 4444 };
  92   enum graph_edge_attribute_t  { graph_edge_attribute  = 5555 };
  93
  94   BOOST_INSTALL_PROPERTY(edge, attribute);
  95   BOOST_INSTALL_PROPERTY(vertex, attribute);
  96   BOOST_INSTALL_PROPERTY(graph, graph_attribute);
  97   BOOST_INSTALL_PROPERTY(graph, vertex_attribute);
  98   BOOST_INSTALL_PROPERTY(graph, edge_attribute);
  99
 100
 101   template <class Attribute>
 102   inline void write_attributes(const Attribute& attr, std::ostream& out) {
 103     typename Attribute::const_iterator i, iend;
 104     i    = attr.begin();
 105     iend = attr.end();
 106
 107     while ( i != iend ) {
 108       out << i->first << "=\"" << i->second << "\"";
 109       ++i;
 110       if ( i != iend )
 111         out << ", ";
 112     }
 113   }
 114
 115   template<typename Attributes>
 116   inline void write_all_attributes(Attributes attributes,
 117                                    const std::string& name,
 118                                    std::ostream& out)
 119   {
 120     typename Attributes::const_iterator i = attributes.begin(),
 121                                         end = attributes.end();
 122     if (i != end) {
 123       out << name << " [\n";
 124       write_attributes(attributes, out);
 125       out << "];\n";
 126     }
 127   }
 128
 129   inline void write_all_attributes(detail::error_property_not_found,
 130                                    const std::string&,
 131                                    std::ostream&)
 132   {
 133     // Do nothing - no attributes exist
 134   }
 135
 136
 137
 138
 139   template <typename GraphGraphAttributes,
 140             typename GraphNodeAttributes,
 141             typename GraphEdgeAttributes>
 142   struct graph_attributes_writer
 143   {
 144     graph_attributes_writer(GraphGraphAttributes gg,
 145                             GraphNodeAttributes gn,
 146                             GraphEdgeAttributes ge)
 147       : g_attributes(gg), n_attributes(gn), e_attributes(ge) { }
 148
 149     void operator()(std::ostream& out) const {
 150       write_all_attributes(g_attributes, "graph", out);
 151       write_all_attributes(n_attributes, "node", out);
 152       write_all_attributes(e_attributes, "edge", out);
 153     }
 154     GraphGraphAttributes g_attributes;
 155     GraphNodeAttributes n_attributes;
 156     GraphEdgeAttributes e_attributes;
 157   };
 158
 159   template <typename GAttrMap, typename NAttrMap, typename EAttrMap>
 160   graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
 161   make_graph_attributes_writer(const GAttrMap& g_attr, const NAttrMap& n_attr,
 162                               const EAttrMap& e_attr) {
 163     return graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
 164       (g_attr, n_attr, e_attr);
 165   }
 166
 167
 168   template <typename Graph>
 169   graph_attributes_writer
 170     <typename graph_property<Graph, graph_graph_attribute_t>::type,
 171      typename graph_property<Graph, graph_vertex_attribute_t>::type,
 172      typename graph_property<Graph, graph_edge_attribute_t>::type>
 173   make_graph_attributes_writer(const Graph& g)
 174   {
 175     typedef typename graph_property<Graph, graph_graph_attribute_t>::type
 176       GAttrMap;
 177     typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
 178       NAttrMap;
 179     typedef typename graph_property<Graph, graph_edge_attribute_t>::type
 180       EAttrMap;
 181     GAttrMap gam = get_property(g, graph_graph_attribute);
 182     NAttrMap nam = get_property(g, graph_vertex_attribute);
 183     EAttrMap eam = get_property(g, graph_edge_attribute);
 184     graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
 185     return writer;
 186   }
 187
 188   template <typename AttributeMap>
 189   struct attributes_writer {
 190     attributes_writer(AttributeMap attr)
 191       : attributes(attr) { }
 192
 193     template <class VorE>
 194     void operator()(std::ostream& out, const VorE& e) const {
 195       this->write_attribute(out, attributes[e]);
 196     }
 197
 198     private:
 199       template<typename AttributeSequence>
 200       void write_attribute(std::ostream& out,
 201                            const AttributeSequence& seq) const
 202       {
 203         if (!seq.empty()) {
 204           out << "[";
 205           write_attributes(seq, out);
 206           out << "]";
 207         }
 208       }
 209
 210       void write_attribute(std::ostream&,
 211                            detail::error_property_not_found) const
 212       {
 213       }
 214     AttributeMap attributes;
 215   };
 216
 217   template <typename Graph>
 218   attributes_writer
 219     <typename property_map<Graph, edge_attribute_t>::const_type>
 220   make_edge_attributes_writer(const Graph& g)
 221   {
 222     typedef typename property_map<Graph, edge_attribute_t>::const_type
 223       EdgeAttributeMap;
 224     return attributes_writer<EdgeAttributeMap>(get(edge_attribute, g));
 225   }
 226
 227   template <typename Graph>
 228   attributes_writer
 229     <typename property_map<Graph, vertex_attribute_t>::const_type>
 230   make_vertex_attributes_writer(const Graph& g)
 231   {
 232     typedef typename property_map<Graph, vertex_attribute_t>::const_type
 233       VertexAttributeMap;
 234     return attributes_writer<VertexAttributeMap>(get(vertex_attribute, g));
 235   }
 236
 237   template <typename Graph, typename VertexPropertiesWriter,
 238             typename EdgePropertiesWriter, typename GraphPropertiesWriter,
 239             typename VertexID>
 240   inline void
 241   write_graphviz
 242     (std::ostream& out, const Graph& g,
 243      VertexPropertiesWriter vpw,
 244      EdgePropertiesWriter epw,
 245      GraphPropertiesWriter gpw,
 246      VertexID vertex_id
 247      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 248   {
 249     typedef typename graph_traits<Graph>::directed_category cat_type;
 250     typedef graphviz_io_traits<cat_type> Traits;
 251     std::string name = "G";
 252     out << Traits::name() << " " << name << " {" << std::endl;
 253
 254     gpw(out); //print graph properties
 255
 256     typename graph_traits<Graph>::vertex_iterator i, end;
 257
 258     for(tie(i,end) = vertices(g); i != end; ++i) {
 259       out << get(vertex_id, *i);
 260       vpw(out, *i); //print vertex attributes
 261       out << ";" << std::endl;
 262     }
 263     typename graph_traits<Graph>::edge_iterator ei, edge_end;
 264     for(tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
 265       out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " ";
 266       epw(out, *ei); //print edge attributes
 267       out << ";" << std::endl;
 268     }
 269     out << "}" << std::endl;
 270   }
 271
 272   template <typename Graph, typename VertexPropertiesWriter,
 273             typename EdgePropertiesWriter, typename GraphPropertiesWriter>
 274   inline void
 275   write_graphviz(std::ostream& out, const Graph& g,
 276                  VertexPropertiesWriter vpw,
 277                  EdgePropertiesWriter epw,
 278                  GraphPropertiesWriter gpw
 279                  BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 280   { write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g)); }
 281
 282 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
 283   // ambiguous overload problem with VC++
 284   template <typename Graph>
 285   inline void
 286   write_graphviz(std::ostream& out, const Graph& g
 287                  BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 288   {
 289     default_writer dw;
 290     default_writer gw;
 291     write_graphviz(out, g, dw, dw, gw);
 292   }
 293 #endif
 294
 295   template <typename Graph, typename VertexWriter>
 296   inline void
 297   write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw
 298                  BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 299   {
 300     default_writer dw;
 301     default_writer gw;
 302     write_graphviz(out, g, vw, dw, gw);
 303   }
 304
 305   template <typename Graph, typename VertexWriter, typename EdgeWriter>
 306   inline void
 307   write_graphviz(std::ostream& out, const Graph& g,
 308                  VertexWriter vw, EdgeWriter ew
 309                  BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 310   {
 311     default_writer gw;
 312     write_graphviz(out, g, vw, ew, gw);
 313   }
 314
 315   namespace detail {
 316
 317     template <class Graph_, class RandomAccessIterator, class VertexID>
 318     void write_graphviz_subgraph (std::ostream& out,
 319                                   const subgraph<Graph_>& g,
 320                                   RandomAccessIterator vertex_marker,
 321                                   RandomAccessIterator edge_marker,
 322                                   VertexID vertex_id)
 323     {
 324       typedef subgraph<Graph_> Graph;
 325       typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 326       typedef typename graph_traits<Graph>::directed_category cat_type;
 327       typedef graphviz_io_traits<cat_type> Traits;
 328
 329       typedef typename graph_property<Graph, graph_name_t>::type NameType;
 330       const NameType& g_name = get_property(g, graph_name);
 331
 332       if ( g.is_root() )
 333         out << Traits::name() ;
 334       else
 335         out << "subgraph";
 336
 337       out << " " << g_name << " {" << std::endl;
 338
 339       typename Graph::const_children_iterator i_child, j_child;
 340
 341       //print graph/node/edge attributes
 342 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
 343       typedef typename graph_property<Graph, graph_graph_attribute_t>::type
 344         GAttrMap;
 345       typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
 346         NAttrMap;
 347       typedef typename graph_property<Graph, graph_edge_attribute_t>::type
 348         EAttrMap;
 349       GAttrMap gam = get_property(g, graph_graph_attribute);
 350       NAttrMap nam = get_property(g, graph_vertex_attribute);
 351       EAttrMap eam = get_property(g, graph_edge_attribute);
 352       graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
 353       writer(out);
 354 #else
 355       make_graph_attributes_writer(g)(out);
 356 #endif
 357
 358       //print subgraph
 359       for ( tie(i_child,j_child) = g.children();
 360             i_child != j_child; ++i_child )
 361         write_graphviz_subgraph(out, *i_child, vertex_marker, edge_marker,
 362                                 vertex_id);
 363
 364       // Print out vertices and edges not in the subgraphs.
 365
 366       typename graph_traits<Graph>::vertex_iterator i, end;
 367       typename graph_traits<Graph>::edge_iterator ei, edge_end;
 368
 369       for(tie(i,end) = vertices(g); i != end; ++i) {
 370         Vertex v = g.local_to_global(*i);
 371         int pos = get(vertex_id, v);
 372         if ( vertex_marker[pos] ) {
 373           vertex_marker[pos] = false;
 374           out << pos;
 375 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
 376           typedef typename property_map<Graph, vertex_attribute_t>::const_type
 377             VertexAttributeMap;
 378           attributes_writer<VertexAttributeMap> vawriter(get(vertex_attribute,
 379                                                              g.root()));
 380           vawriter(out, v);
 381 #else
 382           make_vertex_attributes_writer(g.root())(out, v);
 383 #endif
 384           out << ";" << std::endl;
 385         }
 386       }
 387
 388       for (tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
 389         Vertex u = g.local_to_global(source(*ei,g)),
 390           v = g.local_to_global(target(*ei, g));
 391         int pos = get(get(edge_index, g.root()), g.local_to_global(*ei));
 392         if ( edge_marker[pos] ) {
 393           edge_marker[pos] = false;
 394           out << get(vertex_id, u) << " " << Traits::delimiter()
 395               << " " << get(vertex_id, v);
 396 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
 397           typedef typename property_map<Graph, edge_attribute_t>::const_type
 398             EdgeAttributeMap;
 399           attributes_writer<EdgeAttributeMap> eawriter(get(edge_attribute, g));
 400           eawriter(out, *ei);
 401 #else
 402           make_edge_attributes_writer(g)(out, *ei); //print edge properties
 403 #endif
 404           out << ";" << std::endl;
 405         }
 406       }
 407       out << "}" << std::endl;
 408     }
 409   } // namespace detail
 410
 411   // requires graph_name graph property
 412   template <typename Graph>
 413   void write_graphviz(std::ostream& out, const subgraph<Graph>& g) {
 414     std::vector<bool> edge_marker(num_edges(g), true);
 415     std::vector<bool> vertex_marker(num_vertices(g), true);
 416
 417     detail::write_graphviz_subgraph(out, g,
 418                                     vertex_marker.begin(),
 419                                     edge_marker.begin(),
 420                                     get(vertex_index, g));
 421   }
 422
 423   template <typename Graph>
 424   void write_graphviz(const std::string& filename, const subgraph<Graph>& g) {
 425     std::ofstream out(filename.c_str());
 426     std::vector<bool> edge_marker(num_edges(g), true);
 427     std::vector<bool> vertex_marker(num_vertices(g), true);
 428
 429     detail::write_graphviz_subgraph(out, g,
 430                                     vertex_marker.begin(),
 431                                     edge_marker.begin(),
 432                                     get(vertex_index, g));
 433   }
 434
 435   template <typename Graph, typename VertexID>
 436   void write_graphviz(std::ostream& out, const subgraph<Graph>& g,
 437                       VertexID vertex_id)
 438   {
 439     std::vector<bool> edge_marker(num_edges(g), true);
 440     std::vector<bool> vertex_marker(num_vertices(g), true);
 441
 442     detail::write_graphviz_subgraph(out, g,
 443                                     vertex_marker.begin(),
 444                                     edge_marker.begin(),
 445                                     vertex_id);
 446   }
 447
 448   template <typename Graph, typename VertexID>
 449   void write_graphviz(const std::string& filename, const subgraph<Graph>& g,
 450                       VertexID vertex_id)
 451   {
 452     std::ofstream out(filename.c_str());
 453     std::vector<bool> edge_marker(num_edges(g), true);
 454     std::vector<bool> vertex_marker(num_vertices(g), true);
 455
 456     detail::write_graphviz_subgraph(out, g,
 457                                     vertex_marker.begin(),
 458                                     edge_marker.begin(),
 459                                     vertex_id);
 460   }
 461
 462   typedef std::map<std::string, std::string> GraphvizAttrList;
 463
 464   typedef property<vertex_attribute_t, GraphvizAttrList>
 465           GraphvizVertexProperty;
 466
 467   typedef property<edge_attribute_t, GraphvizAttrList,
 468                    property<edge_index_t, int> >
 469           GraphvizEdgeProperty;
 470
 471   typedef property<graph_graph_attribute_t, GraphvizAttrList,
 472                    property<graph_vertex_attribute_t, GraphvizAttrList,
 473                    property<graph_edge_attribute_t, GraphvizAttrList,
 474                    property<graph_name_t, std::string> > > >
 475           GraphvizGraphProperty;
 476
 477   typedef subgraph<adjacency_list<vecS,
 478                    vecS, directedS,
 479                    GraphvizVertexProperty,
 480                    GraphvizEdgeProperty,
 481                    GraphvizGraphProperty> >
 482           GraphvizDigraph;
 483
 484   typedef subgraph<adjacency_list<vecS,
 485                    vecS, undirectedS,
 486                    GraphvizVertexProperty,
 487                    GraphvizEdgeProperty,
 488                    GraphvizGraphProperty> >
 489           GraphvizGraph;
 490
 491
 492   // These four require linking the BGL-Graphviz library: libbgl-viz.a
 493   // from the /src directory.
 494   extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
 495   extern void read_graphviz(FILE* file, GraphvizDigraph& g);
 496
 497   extern void read_graphviz(const std::string& file, GraphvizGraph& g);
 498   extern void read_graphviz(FILE* file, GraphvizGraph& g);
 499
 500   class dynamic_properties_writer
 501   {
 502   public:
 503     dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) { }
 504
 505     template<typename Descriptor>
 506     void operator()(std::ostream& out, Descriptor key) const
 507     {
 508       bool first = true;
 509       for (dynamic_properties::const_iterator i = dp->begin();
 510            i != dp->end(); ++i) {
 511         if (typeid(key) == i->second->key()) {
 512           if (first) out << " [";
 513           else out << ", ";
 514           first = false;
 515
 516           out << i->first << "=\"" << i->second->get_string(key) << "\"";
 517         }
 518       }
 519
 520       if (!first) out << "]";
 521     }
 522
 523   private:
 524     const dynamic_properties* dp;
 525   };
 526
 527   class dynamic_vertex_properties_writer
 528   {
 529   public:
 530     dynamic_vertex_properties_writer(const dynamic_properties& dp,
 531                                      const std::string& node_id)
 532       : dp(&dp), node_id(&node_id) { }
 533
 534     template<typename Descriptor>
 535     void operator()(std::ostream& out, Descriptor key) const
 536     {
 537       bool first = true;
 538       for (dynamic_properties::const_iterator i = dp->begin();
 539            i != dp->end(); ++i) {
 540         if (typeid(key) == i->second->key()
 541             && i->first != *node_id) {
 542           if (first) out << " [";
 543           else out << ", ";
 544           first = false;
 545
 546           out << i->first << "=\"" << i->second->get_string(key) << "\"";
 547         }
 548       }
 549
 550       if (!first) out << "]";
 551     }
 552
 553   private:
 554     const dynamic_properties* dp;
 555     const std::string* node_id;
 556   };
 557
 558   namespace graph { namespace detail {
 559
 560     template<typename Vertex>
 561     struct node_id_property_map
 562     {
 563       typedef std::string value_type;
 564       typedef value_type reference;
 565       typedef Vertex key_type;
 566       typedef readable_property_map_tag category;
 567
 568       node_id_property_map() {}
 569
 570       node_id_property_map(const dynamic_properties& dp,
 571                            const std::string& node_id)
 572         : dp(&dp), node_id(&node_id) { }
 573
 574       const dynamic_properties* dp;
 575       const std::string* node_id;
 576     };
 577
 578     template<typename Vertex>
 579     inline std::string
 580     get(node_id_property_map<Vertex> pm,
 581         typename node_id_property_map<Vertex>::key_type v)
 582     { return get(*pm.node_id, *pm.dp, v); }
 583
 584   } } // end namespace graph::detail
 585
 586   template<typename Graph>
 587   inline void
 588   write_graphviz(std::ostream& out, const Graph& g,
 589                  const dynamic_properties& dp,
 590                  const std::string& node_id = "node_id"
 591                  BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 592   {
 593     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 594     write_graphviz(out, g, dp, node_id,
 595                    graph::detail::node_id_property_map<Vertex>(dp, node_id));
 596   }
 597
 598   template<typename Graph, typename VertexID>
 599   void
 600   write_graphviz(std::ostream& out, const Graph& g,
 601                  const dynamic_properties& dp, const std::string& node_id,
 602                  VertexID id
 603                  BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 604   {
 605     write_graphviz
 606       (out, g,
 607        /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),
 608        /*edge_writer=*/dynamic_properties_writer(dp),
 609        /*graph_writer=*/default_writer(),
 610        id);
 611   }
 612
 613 /////////////////////////////////////////////////////////////////////////////
 614 // Graph reader exceptions
 615 /////////////////////////////////////////////////////////////////////////////
 616 struct graph_exception : public std::exception {
 617   virtual ~graph_exception() throw() {}
 618   virtual const char* what() const throw() = 0;
 619 };
 620
 621 struct bad_parallel_edge : public graph_exception {
 622   std::string from;
 623   std::string to;
 624   mutable std::string statement;
 625   bad_parallel_edge(const std::string& i, const std::string& j) :
 626     from(i), to(j) {}
 627
 628   virtual ~bad_parallel_edge() throw() {}
 629   const char* what() const throw() {
 630     if(statement.empty())
 631       statement =
 632         std::string("Failed to add parallel edge: (")
 633         + from +  "," + to + ")\n";
 634
 635     return statement.c_str();
 636   }
 637 };
 638
 639 struct directed_graph_error : public graph_exception {
 640   virtual ~directed_graph_error() throw() {}
 641   virtual const char* what() const throw() {
 642     return
 643       "read_graphviz: "
 644       "Tried to read a directed graph into an undirected graph.";
 645   }
 646 };
 647
 648 struct undirected_graph_error : public graph_exception {
 649   virtual ~undirected_graph_error() throw() {}
 650   virtual const char* what() const throw() {
 651     return
 652       "read_graphviz: "
 653       "Tried to read an undirected graph into a directed graph.";
 654   }
 655 };
 656
 657 namespace detail { namespace graph {
 658
 659 typedef std::string id_t;
 660 typedef id_t node_t;
 661
 662 // edges are not uniquely determined by adjacent nodes
 663 class edge_t {
 664   int idx_;
 665   explicit edge_t(int i) : idx_(i) {}
 666 public:
 667   static edge_t new_edge() {
 668     static int idx = 0;
 669     return edge_t(idx++);
 670   };
 671
 672   bool operator==(const edge_t& rhs) const {
 673     return idx_ == rhs.idx_;
 674   }
 675   bool operator<(const edge_t& rhs) const {
 676     return idx_ < rhs.idx_;
 677   }
 678 };
 679
 680 class mutate_graph
 681 {
 682  public:
 683   virtual ~mutate_graph() {}
 684   virtual bool is_directed() const = 0;
 685   virtual void do_add_vertex(const node_t& node) = 0;
 686
 687   virtual void
 688   do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
 689     = 0;
 690
 691   virtual void
 692   set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0;
 693
 694   virtual void
 695   set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0;
 696
 697   virtual void  // RG: need new second parameter to support BGL subgraphs
 698   set_graph_property(const id_t& key, const id_t& value) = 0;
 699 };
 700
 701 template<typename MutableGraph>
 702 class mutate_graph_impl : public mutate_graph
 703 {
 704   typedef typename graph_traits<MutableGraph>::vertex_descriptor bgl_vertex_t;
 705   typedef typename graph_traits<MutableGraph>::edge_descriptor   bgl_edge_t;
 706
 707  public:
 708   mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp,
 709                     std::string node_id_prop)
 710     : graph_(graph), dp_(dp), node_id_prop_(node_id_prop) { }
 711
 712   ~mutate_graph_impl() {}
 713
 714   bool is_directed() const
 715   {
 716     return
 717       boost::is_convertible<
 718         typename boost::graph_traits<MutableGraph>::directed_category,
 719         boost::directed_tag>::value;
 720   }
 721
 722   virtual void do_add_vertex(const node_t& node)
 723   {
 724     // Add the node to the graph.
 725     bgl_vertex_t v = add_vertex(graph_);
 726
 727     // Set up a mapping from name to BGL vertex.
 728     bgl_nodes.insert(std::make_pair(node, v));
 729
 730     // node_id_prop_ allows the caller to see the real id names for nodes.
 731     put(node_id_prop_, dp_, v, node);
 732   }
 733
 734   void
 735   do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
 736   {
 737     std::pair<bgl_edge_t, bool> result =
 738      add_edge(bgl_nodes[source], bgl_nodes[target], graph_);
 739
 740     if(!result.second) {
 741       // In the case of no parallel edges allowed
 742         boost::throw_exception(bad_parallel_edge(source, target));
 743     } else {
 744       bgl_edges.insert(std::make_pair(edge, result.first));
 745     }
 746   }
 747
 748   void
 749   set_node_property(const id_t& key, const node_t& node, const id_t& value)
 750   {
 751     put(key, dp_, bgl_nodes[node], value);
 752   }
 753
 754   void
 755   set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
 756   {
 757     put(key, dp_, bgl_edges[edge], value);
 758   }
 759
 760   void
 761   set_graph_property(const id_t& key, const id_t& value)
 762   {
 763     /* RG: pointer to graph prevents copying */
 764     put(key, dp_, &graph_, value);
 765   }
 766
 767
 768  protected:
 769   MutableGraph& graph_;
 770   dynamic_properties& dp_;
 771   std::string node_id_prop_;
 772   std::map<node_t, bgl_vertex_t> bgl_nodes;
 773   std::map<edge_t, bgl_edge_t> bgl_edges;
 774 };
 775
 776 BOOST_GRAPH_DECL
 777 bool read_graphviz(std::istream& in, mutate_graph& graph);
 778
 779 } } // end namespace detail::graph
 780
 781 // Parse the passed stream as a GraphViz dot file.
 782 template <typename MutableGraph>
 783 bool read_graphviz(std::istream& in, MutableGraph& graph,
 784                    dynamic_properties& dp,
 785                    std::string const& node_id = "node_id")
 786 {
 787   detail::graph::mutate_graph_impl<MutableGraph> m_graph(graph, dp, node_id);
 788   return detail::graph::read_graphviz(in, m_graph);
 789 }
 790
 791 } // namespace boost
 792
 793 #ifdef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
 794 #  include <boost/graph/detail/read_graphviz_spirit.hpp>
 795 #endif // BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
 796
 797 #ifdef BOOST_GRAPH_USE_MPI
 798 #  include <boost/graph/distributed/graphviz.hpp>
 799 #endif
 800
 801 #endif // BOOST_GRAPHVIZ_HPP