]>
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> | |
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(s, valid_unquoted_id)) { | |
72 | return s; | |
73 | } else { | |
74 | boost::algorithm::replace_all(s, "\"", "\\\""); | |
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(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(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(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(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 |