|
1 //======================================================================= |
|
2 // Copyright 2001 University of Notre Dame. |
|
3 // Copyright 2003 Jeremy Siek |
|
4 // Authors: Lie-Quan Lee and Jeremy Siek |
|
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.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/dynamic_property_map.hpp> |
|
26 |
|
27 #ifdef BOOST_HAS_DECLSPEC |
|
28 # if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_GRAPH_DYN_LINK) |
|
29 # ifdef BOOST_GRAPH_SOURCE |
|
30 # define BOOST_GRAPH_DECL __declspec(dllexport) |
|
31 # else |
|
32 # define BOOST_GRAPH_DECL __declspec(dllimport) |
|
33 # endif // BOOST_GRAPH_SOURCE |
|
34 # endif // DYN_LINK |
|
35 #endif // BOOST_HAS_DECLSPEC |
|
36 |
|
37 #ifndef BOOST_GRAPH_DECL |
|
38 # define BOOST_GRAPH_DECL |
|
39 #endif |
|
40 |
|
41 namespace boost { |
|
42 |
|
43 template <typename directed_category> |
|
44 struct graphviz_io_traits { |
|
45 static std::string name() { |
|
46 return "digraph"; |
|
47 } |
|
48 static std::string delimiter() { |
|
49 return "->"; |
|
50 } }; |
|
51 |
|
52 template <> |
|
53 struct graphviz_io_traits <undirected_tag> { |
|
54 static std::string name() { |
|
55 return "graph"; |
|
56 } |
|
57 static std::string delimiter() { |
|
58 return "--"; |
|
59 } |
|
60 }; |
|
61 |
|
62 struct default_writer { |
|
63 void operator()(std::ostream&) const { |
|
64 } |
|
65 template <class VorE> |
|
66 void operator()(std::ostream&, const VorE&) const { |
|
67 } |
|
68 }; |
|
69 |
|
70 template <class Name> |
|
71 class label_writer { |
|
72 public: |
|
73 label_writer(Name _name) : name(_name) {} |
|
74 template <class VertexOrEdge> |
|
75 void operator()(std::ostream& out, const VertexOrEdge& v) const { |
|
76 out << "[label=\"" << get(name, v) << "\"]"; |
|
77 } |
|
78 private: |
|
79 Name name; |
|
80 }; |
|
81 template <class Name> |
|
82 inline label_writer<Name> |
|
83 make_label_writer(Name n) { |
|
84 return label_writer<Name>(n); |
|
85 } |
|
86 |
|
87 enum edge_attribute_t { edge_attribute = 1111 }; |
|
88 enum vertex_attribute_t { vertex_attribute = 2222 }; |
|
89 enum graph_graph_attribute_t { graph_graph_attribute = 3333 }; |
|
90 enum graph_vertex_attribute_t { graph_vertex_attribute = 4444 }; |
|
91 enum graph_edge_attribute_t { graph_edge_attribute = 5555 }; |
|
92 |
|
93 BOOST_INSTALL_PROPERTY(edge, attribute); |
|
94 BOOST_INSTALL_PROPERTY(vertex, attribute); |
|
95 BOOST_INSTALL_PROPERTY(graph, graph_attribute); |
|
96 BOOST_INSTALL_PROPERTY(graph, vertex_attribute); |
|
97 BOOST_INSTALL_PROPERTY(graph, edge_attribute); |
|
98 |
|
99 |
|
100 template <class Attribute> |
|
101 inline void write_attributes(const Attribute& attr, std::ostream& out) { |
|
102 typename Attribute::const_iterator i, iend; |
|
103 i = attr.begin(); |
|
104 iend = attr.end(); |
|
105 |
|
106 while ( i != iend ) { |
|
107 out << i->first << "=\"" << i->second << "\""; |
|
108 ++i; |
|
109 if ( i != iend ) |
|
110 out << ", "; |
|
111 } |
|
112 } |
|
113 |
|
114 template<typename Attributes> |
|
115 inline void write_all_attributes(Attributes attributes, |
|
116 const std::string& name, |
|
117 std::ostream& out) |
|
118 { |
|
119 typename Attributes::const_iterator i = attributes.begin(), |
|
120 end = attributes.end(); |
|
121 if (i != end) { |
|
122 out << name << " [\n"; |
|
123 write_attributes(attributes, out); |
|
124 out << "];\n"; |
|
125 } |
|
126 } |
|
127 |
|
128 inline void write_all_attributes(detail::error_property_not_found, |
|
129 const std::string&, |
|
130 std::ostream&) |
|
131 { |
|
132 // Do nothing - no attributes exist |
|
133 } |
|
134 |
|
135 |
|
136 |
|
137 |
|
138 template <typename GraphGraphAttributes, |
|
139 typename GraphNodeAttributes, |
|
140 typename GraphEdgeAttributes> |
|
141 struct graph_attributes_writer |
|
142 { |
|
143 graph_attributes_writer(GraphGraphAttributes gg, |
|
144 GraphNodeAttributes gn, |
|
145 GraphEdgeAttributes ge) |
|
146 : g_attributes(gg), n_attributes(gn), e_attributes(ge) { } |
|
147 |
|
148 void operator()(std::ostream& out) const { |
|
149 write_all_attributes(g_attributes, "graph", out); |
|
150 write_all_attributes(n_attributes, "node", out); |
|
151 write_all_attributes(e_attributes, "edge", out); |
|
152 } |
|
153 GraphGraphAttributes g_attributes; |
|
154 GraphNodeAttributes n_attributes; |
|
155 GraphEdgeAttributes e_attributes; |
|
156 }; |
|
157 |
|
158 template <typename GAttrMap, typename NAttrMap, typename EAttrMap> |
|
159 graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> |
|
160 make_graph_attributes_writer(const GAttrMap& g_attr, const NAttrMap& n_attr, |
|
161 const EAttrMap& e_attr) { |
|
162 return graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> |
|
163 (g_attr, n_attr, e_attr); |
|
164 } |
|
165 |
|
166 |
|
167 template <typename Graph> |
|
168 graph_attributes_writer |
|
169 <typename graph_property<Graph, graph_graph_attribute_t>::type, |
|
170 typename graph_property<Graph, graph_vertex_attribute_t>::type, |
|
171 typename graph_property<Graph, graph_edge_attribute_t>::type> |
|
172 make_graph_attributes_writer(const Graph& g) |
|
173 { |
|
174 typedef typename graph_property<Graph, graph_graph_attribute_t>::type |
|
175 GAttrMap; |
|
176 typedef typename graph_property<Graph, graph_vertex_attribute_t>::type |
|
177 NAttrMap; |
|
178 typedef typename graph_property<Graph, graph_edge_attribute_t>::type |
|
179 EAttrMap; |
|
180 GAttrMap gam = get_property(g, graph_graph_attribute); |
|
181 NAttrMap nam = get_property(g, graph_vertex_attribute); |
|
182 EAttrMap eam = get_property(g, graph_edge_attribute); |
|
183 graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam); |
|
184 return writer; |
|
185 } |
|
186 |
|
187 template <typename AttributeMap> |
|
188 struct attributes_writer { |
|
189 attributes_writer(AttributeMap attr) |
|
190 : attributes(attr) { } |
|
191 |
|
192 template <class VorE> |
|
193 void operator()(std::ostream& out, const VorE& e) const { |
|
194 this->write_attribute(out, attributes[e]); |
|
195 } |
|
196 |
|
197 private: |
|
198 template<typename AttributeSequence> |
|
199 void write_attribute(std::ostream& out, |
|
200 const AttributeSequence& seq) const |
|
201 { |
|
202 if (!seq.empty()) { |
|
203 out << "["; |
|
204 write_attributes(seq, out); |
|
205 out << "]"; |
|
206 } |
|
207 } |
|
208 |
|
209 void write_attribute(std::ostream&, |
|
210 detail::error_property_not_found) const |
|
211 { |
|
212 } |
|
213 AttributeMap attributes; |
|
214 }; |
|
215 |
|
216 template <typename Graph> |
|
217 attributes_writer |
|
218 <typename property_map<Graph, edge_attribute_t>::const_type> |
|
219 make_edge_attributes_writer(const Graph& g) |
|
220 { |
|
221 typedef typename property_map<Graph, edge_attribute_t>::const_type |
|
222 EdgeAttributeMap; |
|
223 return attributes_writer<EdgeAttributeMap>(get(edge_attribute, g)); |
|
224 } |
|
225 |
|
226 template <typename Graph> |
|
227 attributes_writer |
|
228 <typename property_map<Graph, vertex_attribute_t>::const_type> |
|
229 make_vertex_attributes_writer(const Graph& g) |
|
230 { |
|
231 typedef typename property_map<Graph, vertex_attribute_t>::const_type |
|
232 VertexAttributeMap; |
|
233 return attributes_writer<VertexAttributeMap>(get(vertex_attribute, g)); |
|
234 } |
|
235 |
|
236 template <typename Graph, typename VertexPropertiesWriter, |
|
237 typename EdgePropertiesWriter, typename GraphPropertiesWriter, |
|
238 typename VertexID> |
|
239 inline void write_graphviz(std::ostream& out, const Graph& g, |
|
240 VertexPropertiesWriter vpw, |
|
241 EdgePropertiesWriter epw, |
|
242 GraphPropertiesWriter gpw, |
|
243 VertexID vertex_id) |
|
244 { |
|
245 typedef typename graph_traits<Graph>::directed_category cat_type; |
|
246 typedef graphviz_io_traits<cat_type> Traits; |
|
247 std::string name = "G"; |
|
248 out << Traits::name() << " " << name << " {" << std::endl; |
|
249 |
|
250 gpw(out); //print graph properties |
|
251 |
|
252 typename graph_traits<Graph>::vertex_iterator i, end; |
|
253 |
|
254 for(tie(i,end) = vertices(g); i != end; ++i) { |
|
255 out << get(vertex_id, *i); |
|
256 vpw(out, *i); //print vertex attributes |
|
257 out << ";" << std::endl; |
|
258 } |
|
259 typename graph_traits<Graph>::edge_iterator ei, edge_end; |
|
260 for(tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) { |
|
261 out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " "; |
|
262 epw(out, *ei); //print edge attributes |
|
263 out << ";" << std::endl; |
|
264 } |
|
265 out << "}" << std::endl; |
|
266 } |
|
267 |
|
268 template <typename Graph, typename VertexPropertiesWriter, |
|
269 typename EdgePropertiesWriter, typename GraphPropertiesWriter> |
|
270 inline void write_graphviz(std::ostream& out, const Graph& g, |
|
271 VertexPropertiesWriter vpw, |
|
272 EdgePropertiesWriter epw, |
|
273 GraphPropertiesWriter gpw) |
|
274 { write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g)); } |
|
275 |
|
276 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 |
|
277 // ambiguous overload problem with VC++ |
|
278 template <typename Graph> |
|
279 inline void |
|
280 write_graphviz(std::ostream& out, const Graph& g) { |
|
281 default_writer dw; |
|
282 default_writer gw; |
|
283 write_graphviz(out, g, dw, dw, gw); |
|
284 } |
|
285 #endif |
|
286 |
|
287 template <typename Graph, typename VertexWriter> |
|
288 inline void |
|
289 write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw) { |
|
290 default_writer dw; |
|
291 default_writer gw; |
|
292 write_graphviz(out, g, vw, dw, gw); |
|
293 } |
|
294 |
|
295 template <typename Graph, typename VertexWriter, typename EdgeWriter> |
|
296 inline void |
|
297 write_graphviz(std::ostream& out, const Graph& g, |
|
298 VertexWriter vw, EdgeWriter ew) { |
|
299 default_writer gw; |
|
300 write_graphviz(out, g, vw, ew, gw); |
|
301 } |
|
302 |
|
303 namespace detail { |
|
304 |
|
305 template <class Graph_, class RandomAccessIterator, class VertexID> |
|
306 void write_graphviz_subgraph (std::ostream& out, |
|
307 const subgraph<Graph_>& g, |
|
308 RandomAccessIterator vertex_marker, |
|
309 RandomAccessIterator edge_marker, |
|
310 VertexID vertex_id) |
|
311 { |
|
312 typedef subgraph<Graph_> Graph; |
|
313 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
|
314 typedef typename graph_traits<Graph>::directed_category cat_type; |
|
315 typedef graphviz_io_traits<cat_type> Traits; |
|
316 |
|
317 typedef typename graph_property<Graph, graph_name_t>::type NameType; |
|
318 const NameType& g_name = get_property(g, graph_name); |
|
319 |
|
320 if ( g.is_root() ) |
|
321 out << Traits::name() ; |
|
322 else |
|
323 out << "subgraph"; |
|
324 |
|
325 out << " " << g_name << " {" << std::endl; |
|
326 |
|
327 typename Graph::const_children_iterator i_child, j_child; |
|
328 |
|
329 //print graph/node/edge attributes |
|
330 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
|
331 typedef typename graph_property<Graph, graph_graph_attribute_t>::type |
|
332 GAttrMap; |
|
333 typedef typename graph_property<Graph, graph_vertex_attribute_t>::type |
|
334 NAttrMap; |
|
335 typedef typename graph_property<Graph, graph_edge_attribute_t>::type |
|
336 EAttrMap; |
|
337 GAttrMap gam = get_property(g, graph_graph_attribute); |
|
338 NAttrMap nam = get_property(g, graph_vertex_attribute); |
|
339 EAttrMap eam = get_property(g, graph_edge_attribute); |
|
340 graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam); |
|
341 writer(out); |
|
342 #else |
|
343 make_graph_attributes_writer(g)(out); |
|
344 #endif |
|
345 |
|
346 //print subgraph |
|
347 for ( tie(i_child,j_child) = g.children(); |
|
348 i_child != j_child; ++i_child ) |
|
349 write_graphviz_subgraph(out, *i_child, vertex_marker, edge_marker, |
|
350 vertex_id); |
|
351 |
|
352 // Print out vertices and edges not in the subgraphs. |
|
353 |
|
354 typename graph_traits<Graph>::vertex_iterator i, end; |
|
355 typename graph_traits<Graph>::edge_iterator ei, edge_end; |
|
356 |
|
357 for(tie(i,end) = vertices(g); i != end; ++i) { |
|
358 Vertex v = g.local_to_global(*i); |
|
359 int pos = get(vertex_id, v); |
|
360 if ( vertex_marker[pos] ) { |
|
361 vertex_marker[pos] = false; |
|
362 out << pos; |
|
363 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
|
364 typedef typename property_map<Graph, vertex_attribute_t>::const_type |
|
365 VertexAttributeMap; |
|
366 attributes_writer<VertexAttributeMap> vawriter(get(vertex_attribute, |
|
367 g.root())); |
|
368 vawriter(out, v); |
|
369 #else |
|
370 make_vertex_attributes_writer(g.root())(out, v); |
|
371 #endif |
|
372 out << ";" << std::endl; |
|
373 } |
|
374 } |
|
375 |
|
376 for (tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) { |
|
377 Vertex u = g.local_to_global(source(*ei,g)), |
|
378 v = g.local_to_global(target(*ei, g)); |
|
379 int pos = get(get(edge_index, g.root()), g.local_to_global(*ei)); |
|
380 if ( edge_marker[pos] ) { |
|
381 edge_marker[pos] = false; |
|
382 out << get(vertex_id, u) << " " << Traits::delimiter() |
|
383 << " " << get(vertex_id, v); |
|
384 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 |
|
385 typedef typename property_map<Graph, edge_attribute_t>::const_type |
|
386 EdgeAttributeMap; |
|
387 attributes_writer<EdgeAttributeMap> eawriter(get(edge_attribute, g)); |
|
388 eawriter(out, *ei); |
|
389 #else |
|
390 make_edge_attributes_writer(g)(out, *ei); //print edge properties |
|
391 #endif |
|
392 out << ";" << std::endl; |
|
393 } |
|
394 } |
|
395 out << "}" << std::endl; |
|
396 } |
|
397 } // namespace detail |
|
398 |
|
399 // requires graph_name graph property |
|
400 template <typename Graph> |
|
401 void write_graphviz(std::ostream& out, const subgraph<Graph>& g) { |
|
402 std::vector<bool> edge_marker(num_edges(g), true); |
|
403 std::vector<bool> vertex_marker(num_vertices(g), true); |
|
404 |
|
405 detail::write_graphviz_subgraph(out, g, |
|
406 vertex_marker.begin(), |
|
407 edge_marker.begin(), |
|
408 get(vertex_index, g)); |
|
409 } |
|
410 |
|
411 template <typename Graph> |
|
412 void write_graphviz(const std::string& filename, const subgraph<Graph>& g) { |
|
413 std::ofstream out(filename.c_str()); |
|
414 std::vector<bool> edge_marker(num_edges(g), true); |
|
415 std::vector<bool> vertex_marker(num_vertices(g), true); |
|
416 |
|
417 detail::write_graphviz_subgraph(out, g, |
|
418 vertex_marker.begin(), |
|
419 edge_marker.begin(), |
|
420 get(vertex_index, g)); |
|
421 } |
|
422 |
|
423 template <typename Graph, typename VertexID> |
|
424 void write_graphviz(std::ostream& out, const subgraph<Graph>& g, |
|
425 VertexID vertex_id) |
|
426 { |
|
427 std::vector<bool> edge_marker(num_edges(g), true); |
|
428 std::vector<bool> vertex_marker(num_vertices(g), true); |
|
429 |
|
430 detail::write_graphviz_subgraph(out, g, |
|
431 vertex_marker.begin(), |
|
432 edge_marker.begin(), |
|
433 vertex_id); |
|
434 } |
|
435 |
|
436 template <typename Graph, typename VertexID> |
|
437 void write_graphviz(const std::string& filename, const subgraph<Graph>& g, |
|
438 VertexID vertex_id) |
|
439 { |
|
440 std::ofstream out(filename.c_str()); |
|
441 std::vector<bool> edge_marker(num_edges(g), true); |
|
442 std::vector<bool> vertex_marker(num_vertices(g), true); |
|
443 |
|
444 detail::write_graphviz_subgraph(out, g, |
|
445 vertex_marker.begin(), |
|
446 edge_marker.begin(), |
|
447 vertex_id); |
|
448 } |
|
449 |
|
450 typedef std::map<std::string, std::string> GraphvizAttrList; |
|
451 |
|
452 typedef property<vertex_attribute_t, GraphvizAttrList> |
|
453 GraphvizVertexProperty; |
|
454 |
|
455 typedef property<edge_attribute_t, GraphvizAttrList, |
|
456 property<edge_index_t, int> > |
|
457 GraphvizEdgeProperty; |
|
458 |
|
459 typedef property<graph_graph_attribute_t, GraphvizAttrList, |
|
460 property<graph_vertex_attribute_t, GraphvizAttrList, |
|
461 property<graph_edge_attribute_t, GraphvizAttrList, |
|
462 property<graph_name_t, std::string> > > > |
|
463 GraphvizGraphProperty; |
|
464 |
|
465 typedef subgraph<adjacency_list<vecS, |
|
466 vecS, directedS, |
|
467 GraphvizVertexProperty, |
|
468 GraphvizEdgeProperty, |
|
469 GraphvizGraphProperty> > |
|
470 GraphvizDigraph; |
|
471 |
|
472 typedef subgraph<adjacency_list<vecS, |
|
473 vecS, undirectedS, |
|
474 GraphvizVertexProperty, |
|
475 GraphvizEdgeProperty, |
|
476 GraphvizGraphProperty> > |
|
477 GraphvizGraph; |
|
478 |
|
479 |
|
480 // These four require linking the BGL-Graphviz library: libbgl-viz.a |
|
481 // from the /src directory. |
|
482 extern void read_graphviz(const std::string& file, GraphvizDigraph& g); |
|
483 extern void read_graphviz(FILE* file, GraphvizDigraph& g); |
|
484 |
|
485 extern void read_graphviz(const std::string& file, GraphvizGraph& g); |
|
486 extern void read_graphviz(FILE* file, GraphvizGraph& g); |
|
487 |
|
488 class dynamic_properties_writer |
|
489 { |
|
490 public: |
|
491 dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) { } |
|
492 |
|
493 template<typename Descriptor> |
|
494 void operator()(std::ostream& out, Descriptor key) const |
|
495 { |
|
496 bool first = true; |
|
497 for (dynamic_properties::const_iterator i = dp->begin(); |
|
498 i != dp->end(); ++i) { |
|
499 if (typeid(key) == i->second->key()) { |
|
500 if (first) out << " ["; |
|
501 else out << ", "; |
|
502 first = false; |
|
503 |
|
504 out << i->first << "=\"" << i->second->get_string(key) << "\""; |
|
505 } |
|
506 } |
|
507 |
|
508 if (!first) out << "]"; |
|
509 } |
|
510 |
|
511 private: |
|
512 const dynamic_properties* dp; |
|
513 }; |
|
514 |
|
515 class dynamic_vertex_properties_writer |
|
516 { |
|
517 public: |
|
518 dynamic_vertex_properties_writer(const dynamic_properties& dp, |
|
519 const std::string& node_id) |
|
520 : dp(&dp), node_id(&node_id) { } |
|
521 |
|
522 template<typename Descriptor> |
|
523 void operator()(std::ostream& out, Descriptor key) const |
|
524 { |
|
525 bool first = true; |
|
526 for (dynamic_properties::const_iterator i = dp->begin(); |
|
527 i != dp->end(); ++i) { |
|
528 if (typeid(key) == i->second->key() |
|
529 && i->first != *node_id) { |
|
530 if (first) out << " ["; |
|
531 else out << ", "; |
|
532 first = false; |
|
533 |
|
534 out << i->first << "=\"" << i->second->get_string(key) << "\""; |
|
535 } |
|
536 } |
|
537 |
|
538 if (!first) out << "]"; |
|
539 } |
|
540 |
|
541 private: |
|
542 const dynamic_properties* dp; |
|
543 const std::string* node_id; |
|
544 }; |
|
545 |
|
546 namespace graph { namespace detail { |
|
547 |
|
548 template<typename Vertex> |
|
549 struct node_id_property_map |
|
550 { |
|
551 typedef std::string value_type; |
|
552 typedef value_type reference; |
|
553 typedef Vertex key_type; |
|
554 typedef readable_property_map_tag category; |
|
555 |
|
556 node_id_property_map() {} |
|
557 |
|
558 node_id_property_map(const dynamic_properties& dp, |
|
559 const std::string& node_id) |
|
560 : dp(&dp), node_id(&node_id) { } |
|
561 |
|
562 const dynamic_properties* dp; |
|
563 const std::string* node_id; |
|
564 }; |
|
565 |
|
566 template<typename Vertex> |
|
567 inline std::string |
|
568 get(node_id_property_map<Vertex> pm, |
|
569 typename node_id_property_map<Vertex>::key_type v) |
|
570 { return get(*pm.node_id, *pm.dp, v); } |
|
571 |
|
572 } } // end namespace graph::detail |
|
573 |
|
574 template<typename Graph> |
|
575 inline void |
|
576 write_graphviz(std::ostream& out, const Graph& g, |
|
577 const dynamic_properties& dp, |
|
578 const std::string& node_id = "node_id") |
|
579 { |
|
580 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
|
581 write_graphviz(out, g, dp, node_id, |
|
582 graph::detail::node_id_property_map<Vertex>(dp, node_id)); |
|
583 } |
|
584 |
|
585 template<typename Graph, typename VertexID> |
|
586 void |
|
587 write_graphviz(std::ostream& out, const Graph& g, |
|
588 const dynamic_properties& dp, const std::string& node_id, |
|
589 VertexID id) |
|
590 { |
|
591 write_graphviz |
|
592 (out, g, |
|
593 /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id), |
|
594 /*edge_writer=*/dynamic_properties_writer(dp), |
|
595 /*graph_writer=*/default_writer(), |
|
596 id); |
|
597 } |
|
598 |
|
599 ///////////////////////////////////////////////////////////////////////////// |
|
600 // Graph reader exceptions |
|
601 ///////////////////////////////////////////////////////////////////////////// |
|
602 struct graph_exception : public std::exception { |
|
603 virtual ~graph_exception() throw() {} |
|
604 virtual const char* what() const throw() = 0; |
|
605 }; |
|
606 |
|
607 struct bad_parallel_edge : public graph_exception { |
|
608 std::string from; |
|
609 std::string to; |
|
610 mutable std::string statement; |
|
611 bad_parallel_edge(const std::string& i, const std::string& j) : |
|
612 from(i), to(j) {} |
|
613 |
|
614 virtual ~bad_parallel_edge() throw() {} |
|
615 const char* what() const throw() { |
|
616 if(statement.empty()) |
|
617 statement = |
|
618 std::string("Failed to add parallel edge: (") |
|
619 + from + "," + to + ")\n"; |
|
620 |
|
621 return statement.c_str(); |
|
622 } |
|
623 }; |
|
624 |
|
625 struct directed_graph_error : public graph_exception { |
|
626 virtual ~directed_graph_error() throw() {} |
|
627 virtual const char* what() const throw() { |
|
628 return |
|
629 "read_graphviz: " |
|
630 "Tried to read a directed graph into an undirected graph."; |
|
631 } |
|
632 }; |
|
633 |
|
634 struct undirected_graph_error : public graph_exception { |
|
635 virtual ~undirected_graph_error() throw() {} |
|
636 virtual const char* what() const throw() { |
|
637 return |
|
638 "read_graphviz: " |
|
639 "Tried to read an undirected graph into a directed graph."; |
|
640 } |
|
641 }; |
|
642 |
|
643 namespace detail { namespace graph { |
|
644 |
|
645 typedef std::string id_t; |
|
646 typedef id_t node_t; |
|
647 |
|
648 // edges are not uniquely determined by adjacent nodes |
|
649 class edge_t { |
|
650 int idx_; |
|
651 explicit edge_t(int i) : idx_(i) {} |
|
652 public: |
|
653 static edge_t new_edge() { |
|
654 static int idx = 0; |
|
655 return edge_t(idx++); |
|
656 }; |
|
657 |
|
658 bool operator==(const edge_t& rhs) const { |
|
659 return idx_ == rhs.idx_; |
|
660 } |
|
661 bool operator<(const edge_t& rhs) const { |
|
662 return idx_ < rhs.idx_; |
|
663 } |
|
664 }; |
|
665 |
|
666 class mutate_graph |
|
667 { |
|
668 public: |
|
669 virtual ~mutate_graph() {} |
|
670 virtual bool is_directed() const = 0; |
|
671 virtual void do_add_vertex(const node_t& node) = 0; |
|
672 |
|
673 virtual void |
|
674 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target) |
|
675 = 0; |
|
676 |
|
677 virtual void |
|
678 set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0; |
|
679 |
|
680 virtual void |
|
681 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0; |
|
682 }; |
|
683 |
|
684 template<typename MutableGraph> |
|
685 class mutate_graph_impl : public mutate_graph |
|
686 { |
|
687 typedef typename graph_traits<MutableGraph>::vertex_descriptor bgl_vertex_t; |
|
688 typedef typename graph_traits<MutableGraph>::edge_descriptor bgl_edge_t; |
|
689 |
|
690 public: |
|
691 mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp, |
|
692 std::string node_id_prop) |
|
693 : graph_(graph), dp_(dp), node_id_prop_(node_id_prop) { } |
|
694 |
|
695 ~mutate_graph_impl() {} |
|
696 |
|
697 bool is_directed() const |
|
698 { |
|
699 return |
|
700 boost::is_convertible< |
|
701 typename boost::graph_traits<MutableGraph>::directed_category, |
|
702 boost::directed_tag>::value; |
|
703 } |
|
704 |
|
705 virtual void do_add_vertex(const node_t& node) |
|
706 { |
|
707 // Add the node to the graph. |
|
708 bgl_vertex_t v = add_vertex(graph_); |
|
709 |
|
710 // Set up a mapping from name to BGL vertex. |
|
711 bgl_nodes.insert(std::make_pair(node, v)); |
|
712 |
|
713 // node_id_prop_ allows the caller to see the real id names for nodes. |
|
714 put(node_id_prop_, dp_, v, node); |
|
715 } |
|
716 |
|
717 void |
|
718 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target) |
|
719 { |
|
720 std::pair<bgl_edge_t, bool> result = |
|
721 add_edge(bgl_nodes[source], bgl_nodes[target], graph_); |
|
722 |
|
723 if(!result.second) { |
|
724 // In the case of no parallel edges allowed |
|
725 throw bad_parallel_edge(source, target); |
|
726 } else { |
|
727 bgl_edges.insert(std::make_pair(edge, result.first)); |
|
728 } |
|
729 } |
|
730 |
|
731 void |
|
732 set_node_property(const id_t& key, const node_t& node, const id_t& value) |
|
733 { |
|
734 put(key, dp_, bgl_nodes[node], value); |
|
735 } |
|
736 |
|
737 void |
|
738 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) |
|
739 { |
|
740 put(key, dp_, bgl_edges[edge], value); |
|
741 } |
|
742 |
|
743 protected: |
|
744 MutableGraph& graph_; |
|
745 dynamic_properties& dp_; |
|
746 std::string node_id_prop_; |
|
747 std::map<node_t, bgl_vertex_t> bgl_nodes; |
|
748 std::map<edge_t, bgl_edge_t> bgl_edges; |
|
749 }; |
|
750 |
|
751 BOOST_GRAPH_DECL |
|
752 bool read_graphviz(std::istream& in, mutate_graph& graph); |
|
753 |
|
754 } } // end namespace detail::graph |
|
755 |
|
756 // Parse the passed stream as a GraphViz dot file. |
|
757 template <typename MutableGraph> |
|
758 bool read_graphviz(std::istream& in, MutableGraph& graph, |
|
759 dynamic_properties& dp, |
|
760 std::string const& node_id = "node_id") |
|
761 { |
|
762 detail::graph::mutate_graph_impl<MutableGraph> m_graph(graph, dp, node_id); |
|
763 return detail::graph::read_graphviz(in, m_graph); |
|
764 } |
|
765 |
|
766 } // namespace boost |
|
767 |
|
768 #ifdef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS |
|
769 # include <boost/graph/detail/read_graphviz_spirit.hpp> |
|
770 #endif // BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS |
|
771 |
|
772 #endif // BOOST_GRAPHVIZ_HPP |