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