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