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 | |
37 | namespace 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 | ///////////////////////////////////////////////////////////////////////////// |
619 | struct graph_exception : public std::exception { |
620 | virtual ~graph_exception() throw() {} |
621 | virtual const char* what() const throw() = 0; |
622 | }; |
623 | |
624 | struct 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 | |
642 | struct 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 | |
651 | struct 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 | |
660 | struct 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 | |
668 | namespace detail { namespace graph { |
669 | |
670 | typedef std::string id_t; |
671 | typedef id_t node_t; |
672 | |
673 | // edges are not uniquely determined by adjacent nodes |
674 | class edge_t { |
675 | int idx_; |
676 | explicit edge_t(int i) : idx_(i) {} |
677 | public: |
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 | |
691 | class 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 | |
715 | template<typename MutableGraph> |
716 | class 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 | |
792 | template<typename Directed, |
793 | typename VertexProperty, |
794 | typename EdgeProperty, |
795 | typename GraphProperty, |
796 | typename Vertex, |
797 | typename EdgeIndex> |
798 | class 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 | |
906 | namespace boost { |
907 | |
908 | // Parse the passed string as a GraphViz dot file. |
909 | template <typename MutableGraph> |
910 | bool 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. |
922 | template <typename InputIterator, typename MutableGraph> |
923 | bool 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. |
942 | template <typename MutableGraph> |
943 | bool 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 | |