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