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