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