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#include <boost/graph/dll_import_export.hpp>
28#include <boost/graph/compressed_sparse_row_graph.hpp>
29#include <boost/graph/iteration_macros.hpp>
30#include <boost/spirit/include/classic_multi_pass.hpp>
31#include <boost/lexical_cast.hpp>
32#include <boost/static_assert.hpp>
33#include <boost/algorithm/string/replace.hpp>
34#include <boost/xpressive/xpressive_static.hpp>
35#include <boost/foreach.hpp>
36
37namespace boost {
38
39 template <typename directed_category>
40 struct graphviz_io_traits {
41 static std::string name() {
42 return "digraph";
43 }
44 static std::string delimiter() {
45 return "->";
46 } };
47
48 template <>
49 struct graphviz_io_traits <undirected_tag> {
50 static std::string name() {
51 return "graph";
52 }
53 static std::string delimiter() {
54 return "--";
55 }
56 };
57
58 struct default_writer {
59 void operator()(std::ostream&) const {
60 }
61 template <class VorE>
62 void operator()(std::ostream&, const VorE&) const {
63 }
64 };
65
66 template <typename T>
67 inline std::string escape_dot_string(const T& obj) {
68 using namespace boost::xpressive;
69 static sregex valid_unquoted_id = (((alpha | '_') >> *_w) | (!as_xpr('-') >> (('.' >> *_d) | (+_d >> !('.' >> *_d)))));
70 std::string s(boost::lexical_cast<std::string>(obj));
71 if (regex_match(rng&: s, re: valid_unquoted_id)) {
72 return s;
73 } else {
74 boost::algorithm::replace_all(Input&: s, Search: "\"", Format: "\\\"");
75 return "\"" + s + "\"";
76 }
77 }
78
79 template <class Name>
80 class label_writer {
81 public:
82 label_writer(Name _name) : name(_name) {}
83 template <class VertexOrEdge>
84 void operator()(std::ostream& out, const VertexOrEdge& v) const {
85 out << "[label=" << escape_dot_string(get(name, v)) << "]";
86 }
87 private:
88 Name name;
89 };
90 template <class Name>
91 inline label_writer<Name>
92 make_label_writer(Name n) {
93 return label_writer<Name>(n);
94 }
95
96 enum edge_attribute_t { edge_attribute = 1111 };
97 enum vertex_attribute_t { vertex_attribute = 2222 };
98 enum graph_graph_attribute_t { graph_graph_attribute = 3333 };
99 enum graph_vertex_attribute_t { graph_vertex_attribute = 4444 };
100 enum graph_edge_attribute_t { graph_edge_attribute = 5555 };
101
102 BOOST_INSTALL_PROPERTY(edge, attribute);
103 BOOST_INSTALL_PROPERTY(vertex, attribute);
104 BOOST_INSTALL_PROPERTY(graph, graph_attribute);
105 BOOST_INSTALL_PROPERTY(graph, vertex_attribute);
106 BOOST_INSTALL_PROPERTY(graph, edge_attribute);
107
108
109 template <class Attribute>
110 inline void write_attributes(const Attribute& attr, std::ostream& out) {
111 typename Attribute::const_iterator i, iend;
112 i = attr.begin();
113 iend = attr.end();
114
115 while ( i != iend ) {
116 out << i->first << "=" << escape_dot_string(i->second);
117 ++i;
118 if ( i != iend )
119 out << ", ";
120 }
121 }
122
123 template<typename Attributes>
124 inline void write_all_attributes(Attributes attributes,
125 const std::string& name,
126 std::ostream& out)
127 {
128 typename Attributes::const_iterator i = attributes.begin(),
129 end = attributes.end();
130 if (i != end) {
131 out << name << " [\n";
132 write_attributes(attributes, out);
133 out << "];\n";
134 }
135 }
136
137 inline void write_all_attributes(detail::error_property_not_found,
138 const std::string&,
139 std::ostream&)
140 {
141 // Do nothing - no attributes exist
142 }
143
144
145
146
147 template <typename GraphGraphAttributes,
148 typename GraphNodeAttributes,
149 typename GraphEdgeAttributes>
150 struct graph_attributes_writer
151 {
152 graph_attributes_writer(GraphGraphAttributes gg,
153 GraphNodeAttributes gn,
154 GraphEdgeAttributes ge)
155 : g_attributes(gg), n_attributes(gn), e_attributes(ge) { }
156
157 void operator()(std::ostream& out) const {
158 write_all_attributes(g_attributes, "graph", out);
159 write_all_attributes(n_attributes, "node", out);
160 write_all_attributes(e_attributes, "edge", out);
161 }
162 GraphGraphAttributes g_attributes;
163 GraphNodeAttributes n_attributes;
164 GraphEdgeAttributes e_attributes;
165 };
166
167 template <typename GAttrMap, typename NAttrMap, typename EAttrMap>
168 graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
169 make_graph_attributes_writer(const GAttrMap& g_attr, const NAttrMap& n_attr,
170 const EAttrMap& e_attr) {
171 return graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
172 (g_attr, n_attr, e_attr);
173 }
174
175
176 template <typename Graph>
177 graph_attributes_writer
178 <typename graph_property<Graph, graph_graph_attribute_t>::type,
179 typename graph_property<Graph, graph_vertex_attribute_t>::type,
180 typename graph_property<Graph, graph_edge_attribute_t>::type>
181 make_graph_attributes_writer(const Graph& g)
182 {
183 typedef typename graph_property<Graph, graph_graph_attribute_t>::type
184 GAttrMap;
185 typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
186 NAttrMap;
187 typedef typename graph_property<Graph, graph_edge_attribute_t>::type
188 EAttrMap;
189 GAttrMap gam = get_property(g, graph_graph_attribute);
190 NAttrMap nam = get_property(g, graph_vertex_attribute);
191 EAttrMap eam = get_property(g, graph_edge_attribute);
192 graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
193 return writer;
194 }
195
196 template <typename AttributeMap>
197 struct attributes_writer {
198 attributes_writer(AttributeMap attr)
199 : attributes(attr) { }
200
201 template <class VorE>
202 void operator()(std::ostream& out, const VorE& e) const {
203 this->write_attribute(out, attributes[e]);
204 }
205
206 private:
207 template<typename AttributeSequence>
208 void write_attribute(std::ostream& out,
209 const AttributeSequence& seq) const
210 {
211 if (!seq.empty()) {
212 out << "[";
213 write_attributes(seq, out);
214 out << "]";
215 }
216 }
217
218 void write_attribute(std::ostream&,
219 detail::error_property_not_found) const
220 {
221 }
222 AttributeMap attributes;
223 };
224
225 template <typename Graph>
226 attributes_writer
227 <typename property_map<Graph, edge_attribute_t>::const_type>
228 make_edge_attributes_writer(const Graph& g)
229 {
230 typedef typename property_map<Graph, edge_attribute_t>::const_type
231 EdgeAttributeMap;
232 return attributes_writer<EdgeAttributeMap>(get(edge_attribute, g));
233 }
234
235 template <typename Graph>
236 attributes_writer
237 <typename property_map<Graph, vertex_attribute_t>::const_type>
238 make_vertex_attributes_writer(const Graph& g)
239 {
240 typedef typename property_map<Graph, vertex_attribute_t>::const_type
241 VertexAttributeMap;
242 return attributes_writer<VertexAttributeMap>(get(vertex_attribute, g));
243 }
244
245 template <typename Graph, typename VertexPropertiesWriter,
246 typename EdgePropertiesWriter, typename GraphPropertiesWriter,
247 typename VertexID>
248 inline void
249 write_graphviz
250 (std::ostream& out, const Graph& g,
251 VertexPropertiesWriter vpw,
252 EdgePropertiesWriter epw,
253 GraphPropertiesWriter gpw,
254 VertexID vertex_id
255 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
256 {
257 BOOST_CONCEPT_ASSERT((EdgeListGraphConcept<Graph>));
258
259 typedef typename graph_traits<Graph>::directed_category cat_type;
260 typedef graphviz_io_traits<cat_type> Traits;
261 std::string name = "G";
262 out << Traits::name() << " " << escape_dot_string(obj: name) << " {" << std::endl;
263
264 gpw(out); //print graph properties
265
266 typename graph_traits<Graph>::vertex_iterator i, end;
267
268 for(boost::tie(i,end) = vertices(g); i != end; ++i) {
269 out << escape_dot_string(get(vertex_id, *i));
270 vpw(out, *i); //print vertex attributes
271 out << ";" << std::endl;
272 }
273 typename graph_traits<Graph>::edge_iterator ei, edge_end;
274 for(boost::tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
275 out << escape_dot_string(get(vertex_id, source(*ei, g))) << Traits::delimiter() << escape_dot_string(get(vertex_id, target(*ei, g))) << " ";
276 epw(out, *ei); //print edge attributes
277 out << ";" << std::endl;
278 }
279 out << "}" << std::endl;
280 }
281
282 template <typename Graph, typename VertexPropertiesWriter,
283 typename EdgePropertiesWriter, typename GraphPropertiesWriter>
284 inline void
285 write_graphviz(std::ostream& out, const Graph& g,
286 VertexPropertiesWriter vpw,
287 EdgePropertiesWriter epw,
288 GraphPropertiesWriter gpw
289 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
290 { write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g)); }
291
292 template <typename Graph>
293 inline void
294 write_graphviz(std::ostream& out, const Graph& g
295 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
296 {
297 default_writer dw;
298 default_writer gw;
299 write_graphviz(out, g, dw, dw, gw);
300 }
301
302 template <typename Graph, typename VertexWriter>
303 inline void
304 write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw
305 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
306 {
307 default_writer dw;
308 default_writer gw;
309 write_graphviz(out, g, vw, dw, gw);
310 }
311
312 template <typename Graph, typename VertexWriter, typename EdgeWriter>
313 inline void
314 write_graphviz(std::ostream& out, const Graph& g,
315 VertexWriter vw, EdgeWriter ew
316 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
317 {
318 default_writer gw;
319 write_graphviz(out, g, vw, ew, gw);
320 }
321
322 namespace detail {
323
324 template <class Graph_, class RandomAccessIterator, class VertexID>
325 void write_graphviz_subgraph (std::ostream& out,
326 const subgraph<Graph_>& g,
327 RandomAccessIterator vertex_marker,
328 RandomAccessIterator edge_marker,
329 VertexID vertex_id)
330 {
331 typedef subgraph<Graph_> Graph;
332 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
333 typedef typename graph_traits<Graph>::directed_category cat_type;
334 typedef graphviz_io_traits<cat_type> Traits;
335
336 typedef typename graph_property<Graph, graph_name_t>::type NameType;
337 const NameType& g_name = get_property(g, graph_name);
338
339 if ( g.is_root() )
340 out << Traits::name() ;
341 else
342 out << "subgraph";
343
344 out << " " << escape_dot_string(g_name) << " {" << std::endl;
345
346 typename Graph::const_children_iterator i_child, j_child;
347
348 //print graph/node/edge attributes
349 make_graph_attributes_writer(g)(out);
350
351 //print subgraph
352 for ( boost::tie(i_child,j_child) = g.children();
353 i_child != j_child; ++i_child )
354 write_graphviz_subgraph(out, *i_child, vertex_marker, edge_marker,
355 vertex_id);
356
357 // Print out vertices and edges not in the subgraphs.
358
359 typename graph_traits<Graph>::vertex_iterator i, end;
360 typename graph_traits<Graph>::edge_iterator ei, edge_end;
361
362 for(boost::tie(i,end) = vertices(g); i != end; ++i) {
363 Vertex v = g.local_to_global(*i);
364 int pos = get(vertex_id, v);
365 if ( vertex_marker[pos] ) {
366 vertex_marker[pos] = false;
367 out << escape_dot_string(obj: pos);
368 make_vertex_attributes_writer(g.root())(out, v);
369 out << ";" << std::endl;
370 }
371 }
372
373 for (boost::tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
374 Vertex u = g.local_to_global(source(*ei,g)),
375 v = g.local_to_global(target(*ei, g));
376 int pos = get(get(edge_index, g.root()), g.local_to_global(*ei));
377 if ( edge_marker[pos] ) {
378 edge_marker[pos] = false;
379 out << escape_dot_string(get(vertex_id, u)) << " " << Traits::delimiter()
380 << " " << escape_dot_string(get(vertex_id, v));
381 make_edge_attributes_writer(g)(out, *ei); //print edge properties
382 out << ";" << std::endl;
383 }
384 }
385 out << "}" << std::endl;
386 }
387 } // namespace detail
388
389 // requires graph_name graph property
390 template <typename Graph>
391 void write_graphviz(std::ostream& out, const subgraph<Graph>& g) {
392 std::vector<bool> edge_marker(num_edges(g), true);
393 std::vector<bool> vertex_marker(num_vertices(g), true);
394
395 detail::write_graphviz_subgraph(out, g,
396 vertex_marker.begin(),
397 edge_marker.begin(),
398 get(vertex_index, g));
399 }
400
401 template <typename Graph>
402 void write_graphviz(const std::string& filename, const subgraph<Graph>& g) {
403 std::ofstream out(filename.c_str());
404 std::vector<bool> edge_marker(num_edges(g), true);
405 std::vector<bool> vertex_marker(num_vertices(g), true);
406
407 detail::write_graphviz_subgraph(out, g,
408 vertex_marker.begin(),
409 edge_marker.begin(),
410 get(vertex_index, g));
411 }
412
413 template <typename Graph, typename VertexID>
414 void write_graphviz(std::ostream& out, const subgraph<Graph>& g,
415 VertexID vertex_id)
416 {
417 std::vector<bool> edge_marker(num_edges(g), true);
418 std::vector<bool> vertex_marker(num_vertices(g), true);
419
420 detail::write_graphviz_subgraph(out, g,
421 vertex_marker.begin(),
422 edge_marker.begin(),
423 vertex_id);
424 }
425
426 template <typename Graph, typename VertexID>
427 void write_graphviz(const std::string& filename, const subgraph<Graph>& g,
428 VertexID vertex_id)
429 {
430 std::ofstream out(filename.c_str());
431 std::vector<bool> edge_marker(num_edges(g), true);
432 std::vector<bool> vertex_marker(num_vertices(g), true);
433
434 detail::write_graphviz_subgraph(out, g,
435 vertex_marker.begin(),
436 edge_marker.begin(),
437 vertex_id);
438 }
439
440#if 0
441 // This interface has not worked for a long time
442 typedef std::map<std::string, std::string> GraphvizAttrList;
443
444 typedef property<vertex_attribute_t, GraphvizAttrList>
445 GraphvizVertexProperty;
446
447 typedef property<edge_attribute_t, GraphvizAttrList,
448 property<edge_index_t, int> >
449 GraphvizEdgeProperty;
450
451 typedef property<graph_graph_attribute_t, GraphvizAttrList,
452 property<graph_vertex_attribute_t, GraphvizAttrList,
453 property<graph_edge_attribute_t, GraphvizAttrList,
454 property<graph_name_t, std::string> > > >
455 GraphvizGraphProperty;
456
457 typedef subgraph<adjacency_list<vecS,
458 vecS, directedS,
459 GraphvizVertexProperty,
460 GraphvizEdgeProperty,
461 GraphvizGraphProperty> >
462 GraphvizDigraph;
463
464 typedef subgraph<adjacency_list<vecS,
465 vecS, undirectedS,
466 GraphvizVertexProperty,
467 GraphvizEdgeProperty,
468 GraphvizGraphProperty> >
469 GraphvizGraph;
470
471 // These four require linking the BGL-Graphviz library: libbgl-viz.a
472 // from the /src directory.
473 // Library has not existed for a while
474 extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
475 extern void read_graphviz(FILE* file, GraphvizDigraph& g);
476
477 extern void read_graphviz(const std::string& file, GraphvizGraph& g);
478 extern void read_graphviz(FILE* file, GraphvizGraph& g);
479#endif
480
481 class dynamic_properties_writer
482 {
483 public:
484 dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) { }
485
486 template<typename Descriptor>
487 void operator()(std::ostream& out, Descriptor key) const
488 {
489 bool first = true;
490 for (dynamic_properties::const_iterator i = dp->begin();
491 i != dp->end(); ++i) {
492 if (typeid(key) == i->second->key()) {
493 if (first) out << " [";
494 else out << ", ";
495 first = false;
496
497 out << i->first << "=" << escape_dot_string(i->second->get_string(key));
498 }
499 }
500
501 if (!first) out << "]";
502 }
503
504 private:
505 const dynamic_properties* dp;
506 };
507
508 class dynamic_vertex_properties_writer
509 {
510 public:
511 dynamic_vertex_properties_writer(const dynamic_properties& dp,
512 const std::string& node_id)
513 : dp(&dp), node_id(&node_id) { }
514
515 template<typename Descriptor>
516 void operator()(std::ostream& out, Descriptor key) const
517 {
518 bool first = true;
519 for (dynamic_properties::const_iterator i = dp->begin();
520 i != dp->end(); ++i) {
521 if (typeid(key) == i->second->key()
522 && i->first != *node_id) {
523 if (first) out << " [";
524 else out << ", ";
525 first = false;
526
527 out << i->first << "=" << escape_dot_string(i->second->get_string(key));
528 }
529 }
530
531 if (!first) out << "]";
532 }
533
534 private:
535 const dynamic_properties* dp;
536 const std::string* node_id;
537 };
538
539 template <typename Graph>
540 class dynamic_graph_properties_writer
541 {
542 public:
543 dynamic_graph_properties_writer(const dynamic_properties& dp, const Graph& g) : g(&g), dp(&dp) { }
544
545 void operator()(std::ostream& out) const
546 {
547 for (dynamic_properties::const_iterator i = dp->begin();
548 i != dp->end(); ++i) {
549 if (typeid(Graph*) == i->second->key()) {
550 // const_cast here is to match interface used in read_graphviz
551 out << i->first << "=" << escape_dot_string(i->second->get_string(key: const_cast<Graph*>(g))) << ";\n";
552 }
553 }
554 }
555
556 private:
557 const Graph* g;
558 const dynamic_properties* dp;
559 };
560
561 namespace graph { namespace detail {
562
563 template<typename Vertex>
564 struct node_id_property_map
565 {
566 typedef std::string value_type;
567 typedef value_type reference;
568 typedef Vertex key_type;
569 typedef readable_property_map_tag category;
570
571 node_id_property_map() {}
572
573 node_id_property_map(const dynamic_properties& dp,
574 const std::string& node_id)
575 : dp(&dp), node_id(&node_id) { }
576
577 const dynamic_properties* dp;
578 const std::string* node_id;
579 };
580
581 template<typename Vertex>
582 inline std::string
583 get(node_id_property_map<Vertex> pm,
584 typename node_id_property_map<Vertex>::key_type v)
585 { return get(*pm.node_id, *pm.dp, v); }
586
587 } } // end namespace graph::detail
588
589 template<typename Graph>
590 inline void
591 write_graphviz_dp(std::ostream& out, const Graph& g,
592 const dynamic_properties& dp,
593 const std::string& node_id = "node_id"
594 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
595 {
596 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
597 write_graphviz_dp(out, g, dp, node_id,
598 graph::detail::node_id_property_map<Vertex>(dp, node_id));
599 }
600
601 template<typename Graph, typename VertexID>
602 void
603 write_graphviz_dp(std::ostream& out, const Graph& g,
604 const dynamic_properties& dp, const std::string& node_id,
605 VertexID id
606 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
607 {
608 write_graphviz
609 (out, g,
610 /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),
611 /*edge_writer=*/dynamic_properties_writer(dp),
612 /*graph_writer=*/dynamic_graph_properties_writer<Graph>(dp, g),
613 id);
614 }
615
616/////////////////////////////////////////////////////////////////////////////
617// Graph reader exceptions
618/////////////////////////////////////////////////////////////////////////////
619struct graph_exception : public std::exception {
620 virtual ~graph_exception() throw() {}
621 virtual const char* what() const throw() = 0;
622};
623
624struct bad_parallel_edge : public graph_exception {
625 std::string from;
626 std::string to;
627 mutable std::string statement;
628 bad_parallel_edge(const std::string& i, const std::string& j) :
629 from(i), to(j) {}
630
631 virtual ~bad_parallel_edge() throw() {}
632 const char* what() const throw() {
633 if(statement.empty())
634 statement =
635 std::string("Failed to add parallel edge: (")
636 + from + "," + to + ")\n";
637
638 return statement.c_str();
639 }
640};
641
642struct directed_graph_error : public graph_exception {
643 virtual ~directed_graph_error() throw() {}
644 virtual const char* what() const throw() {
645 return
646 "read_graphviz: "
647 "Tried to read a directed graph into an undirected graph.";
648 }
649};
650
651struct undirected_graph_error : public graph_exception {
652 virtual ~undirected_graph_error() throw() {}
653 virtual const char* what() const throw() {
654 return
655 "read_graphviz: "
656 "Tried to read an undirected graph into a directed graph.";
657 }
658};
659
660struct bad_graphviz_syntax: public graph_exception {
661 std::string errmsg;
662 bad_graphviz_syntax(const std::string& errmsg)
663 : errmsg(errmsg) {}
664 const char* what() const throw () {return errmsg.c_str();}
665 ~bad_graphviz_syntax() throw () {};
666};
667
668namespace detail { namespace graph {
669
670typedef std::string id_t;
671typedef id_t node_t;
672
673// edges are not uniquely determined by adjacent nodes
674class edge_t {
675 int idx_;
676 explicit edge_t(int i) : idx_(i) {}
677public:
678 static edge_t new_edge() {
679 static int idx = 0;
680 return edge_t(idx++);
681 };
682
683 bool operator==(const edge_t& rhs) const {
684 return idx_ == rhs.idx_;
685 }
686 bool operator<(const edge_t& rhs) const {
687 return idx_ < rhs.idx_;
688 }
689};
690
691class mutate_graph
692{
693 public:
694 virtual ~mutate_graph() {}
695 virtual bool is_directed() const = 0;
696 virtual void do_add_vertex(const node_t& node) = 0;
697
698 virtual void
699 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
700 = 0;
701
702 virtual void
703 set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0;
704
705 virtual void
706 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0;
707
708 virtual void // RG: need new second parameter to support BGL subgraphs
709 set_graph_property(const id_t& key, const id_t& value) = 0;
710
711 virtual void
712 finish_building_graph() = 0;
713};
714
715template<typename MutableGraph>
716class mutate_graph_impl : public mutate_graph
717{
718 typedef typename graph_traits<MutableGraph>::vertex_descriptor bgl_vertex_t;
719 typedef typename graph_traits<MutableGraph>::edge_descriptor bgl_edge_t;
720
721 public:
722 mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp,
723 std::string node_id_prop)
724 : graph_(graph), dp_(dp), node_id_prop_(node_id_prop) { }
725
726 ~mutate_graph_impl() {}
727
728 bool is_directed() const
729 {
730 return
731 boost::is_convertible<
732 typename boost::graph_traits<MutableGraph>::directed_category,
733 boost::directed_tag>::value;
734 }
735
736 virtual void do_add_vertex(const node_t& node)
737 {
738 // Add the node to the graph.
739 bgl_vertex_t v = add_vertex(graph_);
740
741 // Set up a mapping from name to BGL vertex.
742 bgl_nodes.insert(std::make_pair(node, v));
743
744 // node_id_prop_ allows the caller to see the real id names for nodes.
745 put(node_id_prop_, dp_, v, node);
746 }
747
748 void
749 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
750 {
751 std::pair<bgl_edge_t, bool> result =
752 add_edge(bgl_nodes[source], bgl_nodes[target], graph_);
753
754 if(!result.second) {
755 // In the case of no parallel edges allowed
756 boost::throw_exception(e: bad_parallel_edge(source, target));
757 } else {
758 bgl_edges.insert(std::make_pair(edge, result.first));
759 }
760 }
761
762 void
763 set_node_property(const id_t& key, const node_t& node, const id_t& value)
764 {
765 put(key, dp_, bgl_nodes[node], value);
766 }
767
768 void
769 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
770 {
771 put(key, dp_, bgl_edges[edge], value);
772 }
773
774 void
775 set_graph_property(const id_t& key, const id_t& value)
776 {
777 /* RG: pointer to graph prevents copying */
778 put(key, dp_, &graph_, value);
779 }
780
781 void finish_building_graph() {}
782
783
784 protected:
785 MutableGraph& graph_;
786 dynamic_properties& dp_;
787 std::string node_id_prop_;
788 std::map<node_t, bgl_vertex_t> bgl_nodes;
789 std::map<edge_t, bgl_edge_t> bgl_edges;
790};
791
792template<typename Directed,
793 typename VertexProperty,
794 typename EdgeProperty,
795 typename GraphProperty,
796 typename Vertex,
797 typename EdgeIndex>
798class mutate_graph_impl<compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> >
799 : public mutate_graph
800{
801 typedef compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> CSRGraph;
802 typedef typename graph_traits<CSRGraph>::vertices_size_type bgl_vertex_t;
803 typedef typename graph_traits<CSRGraph>::edges_size_type bgl_edge_t;
804 typedef typename graph_traits<CSRGraph>::edge_descriptor edge_descriptor;
805
806 public:
807 mutate_graph_impl(CSRGraph& graph, dynamic_properties& dp,
808 std::string node_id_prop)
809 : graph_(graph), dp_(dp), vertex_count(0), node_id_prop_(node_id_prop) { }
810
811 ~mutate_graph_impl() {}
812
813 void finish_building_graph() {
814 typedef compressed_sparse_row_graph<directedS, no_property, bgl_edge_t, GraphProperty, Vertex, EdgeIndex> TempCSRGraph;
815 TempCSRGraph temp(edges_are_unsorted_multi_pass,
816 edges_to_add.begin(), edges_to_add.end(),
817 counting_iterator<bgl_edge_t>(0),
818 vertex_count);
819 set_property(temp, graph_all, get_property(graph_, graph_all));
820 graph_.assign(temp); // Copies structure, not properties
821 std::vector<edge_descriptor> edge_permutation_from_sorting(num_edges(temp));
822 BGL_FORALL_EDGES_T(e, temp, TempCSRGraph) {
823 edge_permutation_from_sorting[temp[e]] = e;
824 }
825 typedef boost::tuple<id_t, bgl_vertex_t, id_t> v_prop;
826 BOOST_FOREACH(const v_prop& t, vertex_props) {
827 put(boost::get<0>(t), dp_, boost::get<1>(t), boost::get<2>(t));
828 }
829 typedef boost::tuple<id_t, bgl_edge_t, id_t> e_prop;
830 BOOST_FOREACH(const e_prop& t, edge_props) {
831 put(boost::get<0>(t), dp_, edge_permutation_from_sorting[boost::get<1>(t)], boost::get<2>(t));
832 }
833 }
834
835 bool is_directed() const
836 {
837 return
838 boost::is_convertible<
839 typename boost::graph_traits<CSRGraph>::directed_category,
840 boost::directed_tag>::value;
841 }
842
843 virtual void do_add_vertex(const node_t& node)
844 {
845 // Add the node to the graph.
846 bgl_vertex_t v = vertex_count++;
847
848 // Set up a mapping from name to BGL vertex.
849 bgl_nodes.insert(std::make_pair(node, v));
850
851 // node_id_prop_ allows the caller to see the real id names for nodes.
852 vertex_props.push_back(boost::make_tuple(node_id_prop_, v, node));
853 }
854
855 void
856 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
857 {
858 bgl_edge_t result = edges_to_add.size();
859 edges_to_add.push_back(std::make_pair(bgl_nodes[source], bgl_nodes[target]));
860 bgl_edges.insert(std::make_pair(edge, result));
861 }
862
863 void
864 set_node_property(const id_t& key, const node_t& node, const id_t& value)
865 {
866 vertex_props.push_back(boost::make_tuple(key, bgl_nodes[node], value));
867 }
868
869 void
870 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
871 {
872 edge_props.push_back(boost::make_tuple(key, bgl_edges[edge], value));
873 }
874
875 void
876 set_graph_property(const id_t& key, const id_t& value)
877 {
878 /* RG: pointer to graph prevents copying */
879 put(key, dp_, &graph_, value);
880 }
881
882
883 protected:
884 CSRGraph& graph_;
885 dynamic_properties& dp_;
886 bgl_vertex_t vertex_count;
887 std::string node_id_prop_;
888 std::vector<boost::tuple<id_t, bgl_vertex_t, id_t> > vertex_props;
889 std::vector<boost::tuple<id_t, bgl_edge_t, id_t> > edge_props;
890 std::vector<std::pair<bgl_vertex_t, bgl_vertex_t> > edges_to_add;
891 std::map<node_t, bgl_vertex_t> bgl_nodes;
892 std::map<edge_t, bgl_edge_t> bgl_edges;
893};
894
895} } } // end namespace boost::detail::graph
896
897#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
898# ifndef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
899# define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
900# endif
901# include <boost/graph/detail/read_graphviz_spirit.hpp>
902#else // New default parser
903# include <boost/graph/detail/read_graphviz_new.hpp>
904#endif // BOOST_GRAPH_USE_SPIRIT_PARSER
905
906namespace boost {
907
908// Parse the passed string as a GraphViz dot file.
909template <typename MutableGraph>
910bool read_graphviz(const std::string& data,
911 MutableGraph& graph,
912 dynamic_properties& dp,
913 std::string const& node_id = "node_id") {
914#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
915 return read_graphviz_spirit(data.begin(), data.end(), graph, dp, node_id);
916#else // Non-Spirit parser
917 return read_graphviz_new(data,graph,dp,node_id);
918#endif
919}
920
921// Parse the passed iterator range as a GraphViz dot file.
922template <typename InputIterator, typename MutableGraph>
923bool read_graphviz(InputIterator user_first,
924 InputIterator user_last,
925 MutableGraph& graph,
926 dynamic_properties& dp,
927 std::string const& node_id = "node_id") {
928#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
929 typedef InputIterator is_t;
930 typedef boost::spirit::classic::multi_pass<is_t> iterator_t;
931
932 iterator_t first(boost::spirit::classic::make_multi_pass(user_first));
933 iterator_t last(boost::spirit::classic::make_multi_pass(user_last));
934
935 return read_graphviz_spirit(first, last, graph, dp, node_id);
936#else // Non-Spirit parser
937 return read_graphviz_new(std::string(user_first, user_last), graph, dp, node_id);
938#endif
939}
940
941// Parse the passed stream as a GraphViz dot file.
942template <typename MutableGraph>
943bool read_graphviz(std::istream& in, MutableGraph& graph,
944 dynamic_properties& dp,
945 std::string const& node_id = "node_id")
946{
947 typedef std::istream_iterator<char> is_t;
948 in >> std::noskipws;
949 return read_graphviz(is_t(in), is_t(), graph, dp, node_id);
950}
951
952} // namespace boost
953
954#ifdef BOOST_GRAPH_USE_MPI
955# include <boost/graph/distributed/graphviz.hpp>
956#endif
957
958#endif // BOOST_GRAPHVIZ_HPP
959

source code of boost/boost/graph/graphviz.hpp