ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
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
37namespace 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#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
293 // ambiguous overload problem with VC++
294 template <typename Graph>
295 inline void
296 write_graphviz(std::ostream& out, const Graph& g
297 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
298 {
299 default_writer dw;
300 default_writer gw;
301 write_graphviz(out, g, dw, dw, gw);
302 }
303#endif
304
305 template <typename Graph, typename VertexWriter>
306 inline void
307 write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw
308 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
309 {
310 default_writer dw;
311 default_writer gw;
312 write_graphviz(out, g, vw, dw, gw);
313 }
314
315 template <typename Graph, typename VertexWriter, typename EdgeWriter>
316 inline void
317 write_graphviz(std::ostream& out, const Graph& g,
318 VertexWriter vw, EdgeWriter ew
319 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
320 {
321 default_writer gw;
322 write_graphviz(out, g, vw, ew, gw);
323 }
324
325 namespace detail {
326
327 template <class Graph_, class RandomAccessIterator, class VertexID>
328 void write_graphviz_subgraph (std::ostream& out,
329 const subgraph<Graph_>& g,
330 RandomAccessIterator vertex_marker,
331 RandomAccessIterator edge_marker,
332 VertexID vertex_id)
333 {
334 typedef subgraph<Graph_> Graph;
335 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
336 typedef typename graph_traits<Graph>::directed_category cat_type;
337 typedef graphviz_io_traits<cat_type> Traits;
338
339 typedef typename graph_property<Graph, graph_name_t>::type NameType;
340 const NameType& g_name = get_property(g, graph_name);
341
342 if ( g.is_root() )
343 out << Traits::name() ;
344 else
345 out << "subgraph";
346
347 out << " " << escape_dot_string(g_name) << " {" << std::endl;
348
349 typename Graph::const_children_iterator i_child, j_child;
350
351 //print graph/node/edge attributes
352#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
353 typedef typename graph_property<Graph, graph_graph_attribute_t>::type
354 GAttrMap;
355 typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
356 NAttrMap;
357 typedef typename graph_property<Graph, graph_edge_attribute_t>::type
358 EAttrMap;
359 GAttrMap gam = get_property(g, graph_graph_attribute);
360 NAttrMap nam = get_property(g, graph_vertex_attribute);
361 EAttrMap eam = get_property(g, graph_edge_attribute);
362 graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
363 writer(out);
364#else
365 make_graph_attributes_writer(g)(out);
366#endif
367
368 //print subgraph
369 for ( boost::tie(i_child,j_child) = g.children();
370 i_child != j_child; ++i_child )
371 write_graphviz_subgraph(out, *i_child, vertex_marker, edge_marker,
372 vertex_id);
373
374 // Print out vertices and edges not in the subgraphs.
375
376 typename graph_traits<Graph>::vertex_iterator i, end;
377 typename graph_traits<Graph>::edge_iterator ei, edge_end;
378
379 for(boost::tie(i,end) = vertices(g); i != end; ++i) {
380 Vertex v = g.local_to_global(*i);
381 int pos = get(vertex_id, v);
382 if ( vertex_marker[pos] ) {
383 vertex_marker[pos] = false;
384 out << escape_dot_string(pos);
385#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
386 typedef typename property_map<Graph, vertex_attribute_t>::const_type
387 VertexAttributeMap;
388 attributes_writer<VertexAttributeMap> vawriter(get(vertex_attribute,
389 g.root()));
390 vawriter(out, v);
391#else
392 make_vertex_attributes_writer(g.root())(out, v);
393#endif
394 out << ";" << std::endl;
395 }
396 }
397
398 for (boost::tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
399 Vertex u = g.local_to_global(source(*ei,g)),
400 v = g.local_to_global(target(*ei, g));
401 int pos = get(get(edge_index, g.root()), g.local_to_global(*ei));
402 if ( edge_marker[pos] ) {
403 edge_marker[pos] = false;
404 out << escape_dot_string(get(vertex_id, u)) << " " << Traits::delimiter()
405 << " " << escape_dot_string(get(vertex_id, v));
406#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
407 typedef typename property_map<Graph, edge_attribute_t>::const_type
408 EdgeAttributeMap;
409 attributes_writer<EdgeAttributeMap> eawriter(get(edge_attribute, g));
410 eawriter(out, *ei);
411#else
412 make_edge_attributes_writer(g)(out, *ei); //print edge properties
413#endif
414 out << ";" << std::endl;
415 }
416 }
417 out << "}" << std::endl;
418 }
419 } // namespace detail
420
421 // requires graph_name graph property
422 template <typename Graph>
423 void write_graphviz(std::ostream& out, const subgraph<Graph>& g) {
424 std::vector<bool> edge_marker(num_edges(g), true);
425 std::vector<bool> vertex_marker(num_vertices(g), true);
426
427 detail::write_graphviz_subgraph(out, g,
428 vertex_marker.begin(),
429 edge_marker.begin(),
430 get(vertex_index, g));
431 }
432
433 template <typename Graph>
434 void write_graphviz(const std::string& filename, const subgraph<Graph>& g) {
435 std::ofstream out(filename.c_str());
436 std::vector<bool> edge_marker(num_edges(g), true);
437 std::vector<bool> vertex_marker(num_vertices(g), true);
438
439 detail::write_graphviz_subgraph(out, g,
440 vertex_marker.begin(),
441 edge_marker.begin(),
442 get(vertex_index, g));
443 }
444
445 template <typename Graph, typename VertexID>
446 void write_graphviz(std::ostream& out, const subgraph<Graph>& g,
447 VertexID vertex_id)
448 {
449 std::vector<bool> edge_marker(num_edges(g), true);
450 std::vector<bool> vertex_marker(num_vertices(g), true);
451
452 detail::write_graphviz_subgraph(out, g,
453 vertex_marker.begin(),
454 edge_marker.begin(),
455 vertex_id);
456 }
457
458 template <typename Graph, typename VertexID>
459 void write_graphviz(const std::string& filename, const subgraph<Graph>& g,
460 VertexID vertex_id)
461 {
462 std::ofstream out(filename.c_str());
463 std::vector<bool> edge_marker(num_edges(g), true);
464 std::vector<bool> vertex_marker(num_vertices(g), true);
465
466 detail::write_graphviz_subgraph(out, g,
467 vertex_marker.begin(),
468 edge_marker.begin(),
469 vertex_id);
470 }
471
472#if 0
473 // This interface has not worked for a long time
474 typedef std::map<std::string, std::string> GraphvizAttrList;
475
476 typedef property<vertex_attribute_t, GraphvizAttrList>
477 GraphvizVertexProperty;
478
479 typedef property<edge_attribute_t, GraphvizAttrList,
480 property<edge_index_t, int> >
481 GraphvizEdgeProperty;
482
483 typedef property<graph_graph_attribute_t, GraphvizAttrList,
484 property<graph_vertex_attribute_t, GraphvizAttrList,
485 property<graph_edge_attribute_t, GraphvizAttrList,
486 property<graph_name_t, std::string> > > >
487 GraphvizGraphProperty;
488
489 typedef subgraph<adjacency_list<vecS,
490 vecS, directedS,
491 GraphvizVertexProperty,
492 GraphvizEdgeProperty,
493 GraphvizGraphProperty> >
494 GraphvizDigraph;
495
496 typedef subgraph<adjacency_list<vecS,
497 vecS, undirectedS,
498 GraphvizVertexProperty,
499 GraphvizEdgeProperty,
500 GraphvizGraphProperty> >
501 GraphvizGraph;
502
503 // These four require linking the BGL-Graphviz library: libbgl-viz.a
504 // from the /src directory.
505 // Library has not existed for a while
506 extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
507 extern void read_graphviz(FILE* file, GraphvizDigraph& g);
508
509 extern void read_graphviz(const std::string& file, GraphvizGraph& g);
510 extern void read_graphviz(FILE* file, GraphvizGraph& g);
511#endif
512
513 class dynamic_properties_writer
514 {
515 public:
516 dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) { }
517
518 template<typename Descriptor>
519 void operator()(std::ostream& out, Descriptor key) const
520 {
521 bool first = true;
522 for (dynamic_properties::const_iterator i = dp->begin();
523 i != dp->end(); ++i) {
524 if (typeid(key) == i->second->key()) {
525 if (first) out << " [";
526 else out << ", ";
527 first = false;
528
529 out << i->first << "=" << escape_dot_string(i->second->get_string(key));
530 }
531 }
532
533 if (!first) out << "]";
534 }
535
536 private:
537 const dynamic_properties* dp;
538 };
539
540 class dynamic_vertex_properties_writer
541 {
542 public:
543 dynamic_vertex_properties_writer(const dynamic_properties& dp,
544 const std::string& node_id)
545 : dp(&dp), node_id(&node_id) { }
546
547 template<typename Descriptor>
548 void operator()(std::ostream& out, Descriptor key) const
549 {
550 bool first = true;
551 for (dynamic_properties::const_iterator i = dp->begin();
552 i != dp->end(); ++i) {
553 if (typeid(key) == i->second->key()
554 && i->first != *node_id) {
555 if (first) out << " [";
556 else out << ", ";
557 first = false;
558
559 out << i->first << "=" << escape_dot_string(i->second->get_string(key));
560 }
561 }
562
563 if (!first) out << "]";
564 }
565
566 private:
567 const dynamic_properties* dp;
568 const std::string* node_id;
569 };
570
571 namespace graph { namespace detail {
572
573 template<typename Vertex>
574 struct node_id_property_map
575 {
576 typedef std::string value_type;
577 typedef value_type reference;
578 typedef Vertex key_type;
579 typedef readable_property_map_tag category;
580
581 node_id_property_map() {}
582
583 node_id_property_map(const dynamic_properties& dp,
584 const std::string& node_id)
585 : dp(&dp), node_id(&node_id) { }
586
587 const dynamic_properties* dp;
588 const std::string* node_id;
589 };
590
591 template<typename Vertex>
592 inline std::string
593 get(node_id_property_map<Vertex> pm,
594 typename node_id_property_map<Vertex>::key_type v)
595 { return get(*pm.node_id, *pm.dp, v); }
596
597 } } // end namespace graph::detail
598
599 template<typename Graph>
600 inline void
601 write_graphviz_dp(std::ostream& out, const Graph& g,
602 const dynamic_properties& dp,
603 const std::string& node_id = "node_id"
604 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
605 {
606 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
607 write_graphviz_dp(out, g, dp, node_id,
608 graph::detail::node_id_property_map<Vertex>(dp, node_id));
609 }
610
611 template<typename Graph, typename VertexID>
612 void
613 write_graphviz_dp(std::ostream& out, const Graph& g,
614 const dynamic_properties& dp, const std::string& node_id,
615 VertexID id
616 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
617 {
618 write_graphviz
619 (out, g,
620 /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),
621 /*edge_writer=*/dynamic_properties_writer(dp),
622 /*graph_writer=*/default_writer(),
623 id);
624 }
625
626/////////////////////////////////////////////////////////////////////////////
627// Graph reader exceptions
628/////////////////////////////////////////////////////////////////////////////
629struct graph_exception : public std::exception {
630 virtual ~graph_exception() throw() {}
631 virtual const char* what() const throw() = 0;
632};
633
634struct bad_parallel_edge : public graph_exception {
635 std::string from;
636 std::string to;
637 mutable std::string statement;
638 bad_parallel_edge(const std::string& i, const std::string& j) :
639 from(i), to(j) {}
640
641 virtual ~bad_parallel_edge() throw() {}
642 const char* what() const throw() {
643 if(statement.empty())
644 statement =
645 std::string("Failed to add parallel edge: (")
646 + from + "," + to + ")\n";
647
648 return statement.c_str();
649 }
650};
651
652struct directed_graph_error : public graph_exception {
653 virtual ~directed_graph_error() throw() {}
654 virtual const char* what() const throw() {
655 return
656 "read_graphviz: "
657 "Tried to read a directed graph into an undirected graph.";
658 }
659};
660
661struct undirected_graph_error : public graph_exception {
662 virtual ~undirected_graph_error() throw() {}
663 virtual const char* what() const throw() {
664 return
665 "read_graphviz: "
666 "Tried to read an undirected graph into a directed graph.";
667 }
668};
669
670struct bad_graphviz_syntax: public graph_exception {
671 std::string errmsg;
672 bad_graphviz_syntax(const std::string& errmsg)
673 : errmsg(errmsg) {}
674 const char* what() const throw () {return errmsg.c_str();}
675 ~bad_graphviz_syntax() throw () {};
676};
677
678namespace detail { namespace graph {
679
680typedef std::string id_t;
681typedef id_t node_t;
682
683// edges are not uniquely determined by adjacent nodes
684class edge_t {
685 int idx_;
686 explicit edge_t(int i) : idx_(i) {}
687public:
688 static edge_t new_edge() {
689 static int idx = 0;
690 return edge_t(idx++);
691 };
692
693 bool operator==(const edge_t& rhs) const {
694 return idx_ == rhs.idx_;
695 }
696 bool operator<(const edge_t& rhs) const {
697 return idx_ < rhs.idx_;
698 }
699};
700
701class mutate_graph
702{
703 public:
704 virtual ~mutate_graph() {}
705 virtual bool is_directed() const = 0;
706 virtual void do_add_vertex(const node_t& node) = 0;
707
708 virtual void
709 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
710 = 0;
711
712 virtual void
713 set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0;
714
715 virtual void
716 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0;
717
718 virtual void // RG: need new second parameter to support BGL subgraphs
719 set_graph_property(const id_t& key, const id_t& value) = 0;
720
721 virtual void
722 finish_building_graph() = 0;
723};
724
725template<typename MutableGraph>
726class mutate_graph_impl : public mutate_graph
727{
728 typedef typename graph_traits<MutableGraph>::vertex_descriptor bgl_vertex_t;
729 typedef typename graph_traits<MutableGraph>::edge_descriptor bgl_edge_t;
730
731 public:
732 mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp,
733 std::string node_id_prop)
734 : graph_(graph), dp_(dp), node_id_prop_(node_id_prop) { }
735
736 ~mutate_graph_impl() {}
737
738 bool is_directed() const
739 {
740 return
741 boost::is_convertible<
742 typename boost::graph_traits<MutableGraph>::directed_category,
743 boost::directed_tag>::value;
744 }
745
746 virtual void do_add_vertex(const node_t& node)
747 {
748 // Add the node to the graph.
749 bgl_vertex_t v = add_vertex(graph_);
750
751 // Set up a mapping from name to BGL vertex.
752 bgl_nodes.insert(std::make_pair(node, v));
753
754 // node_id_prop_ allows the caller to see the real id names for nodes.
755 put(node_id_prop_, dp_, v, node);
756 }
757
758 void
759 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
760 {
761 std::pair<bgl_edge_t, bool> result =
762 add_edge(bgl_nodes[source], bgl_nodes[target], graph_);
763
764 if(!result.second) {
765 // In the case of no parallel edges allowed
766 boost::throw_exception(bad_parallel_edge(source, target));
767 } else {
768 bgl_edges.insert(std::make_pair(edge, result.first));
769 }
770 }
771
772 void
773 set_node_property(const id_t& key, const node_t& node, const id_t& value)
774 {
775 put(key, dp_, bgl_nodes[node], value);
776 }
777
778 void
779 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
780 {
781 put(key, dp_, bgl_edges[edge], value);
782 }
783
784 void
785 set_graph_property(const id_t& key, const id_t& value)
786 {
787 /* RG: pointer to graph prevents copying */
788 put(key, dp_, &graph_, value);
789 }
790
791 void finish_building_graph() {}
792
793
794 protected:
795 MutableGraph& graph_;
796 dynamic_properties& dp_;
797 std::string node_id_prop_;
798 std::map<node_t, bgl_vertex_t> bgl_nodes;
799 std::map<edge_t, bgl_edge_t> bgl_edges;
800};
801
802template<typename Directed,
803 typename VertexProperty,
804 typename EdgeProperty,
805 typename GraphProperty,
806 typename Vertex,
807 typename EdgeIndex>
808class mutate_graph_impl<compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> >
809 : public mutate_graph
810{
811 typedef compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> CSRGraph;
812 typedef typename graph_traits<CSRGraph>::vertices_size_type bgl_vertex_t;
813 typedef typename graph_traits<CSRGraph>::edges_size_type bgl_edge_t;
814 typedef typename graph_traits<CSRGraph>::edge_descriptor edge_descriptor;
815
816 public:
817 mutate_graph_impl(CSRGraph& graph, dynamic_properties& dp,
818 std::string node_id_prop)
819 : graph_(graph), dp_(dp), vertex_count(0), node_id_prop_(node_id_prop) { }
820
821 ~mutate_graph_impl() {}
822
823 void finish_building_graph() {
824 typedef compressed_sparse_row_graph<directedS, no_property, bgl_edge_t, GraphProperty, Vertex, EdgeIndex> TempCSRGraph;
825 TempCSRGraph temp(edges_are_unsorted_multi_pass,
826 edges_to_add.begin(), edges_to_add.end(),
827 counting_iterator<bgl_edge_t>(0),
828 vertex_count);
829 set_property(temp, graph_all, get_property(graph_, graph_all));
830 graph_.assign(temp); // Copies structure, not properties
831 std::vector<edge_descriptor> edge_permutation_from_sorting(num_edges(temp));
832 BGL_FORALL_EDGES_T(e, temp, TempCSRGraph) {
833 edge_permutation_from_sorting[temp[e]] = e;
834 }
835 typedef boost::tuple<id_t, bgl_vertex_t, id_t> v_prop;
836 BOOST_FOREACH(const v_prop& t, vertex_props) {
837 put(boost::get<0>(t), dp_, boost::get<1>(t), boost::get<2>(t));
838 }
839 typedef boost::tuple<id_t, bgl_edge_t, id_t> e_prop;
840 BOOST_FOREACH(const e_prop& t, edge_props) {
841 put(boost::get<0>(t), dp_, edge_permutation_from_sorting[boost::get<1>(t)], boost::get<2>(t));
842 }
843 }
844
845 bool is_directed() const
846 {
847 return
848 boost::is_convertible<
849 typename boost::graph_traits<CSRGraph>::directed_category,
850 boost::directed_tag>::value;
851 }
852
853 virtual void do_add_vertex(const node_t& node)
854 {
855 // Add the node to the graph.
856 bgl_vertex_t v = vertex_count++;
857
858 // Set up a mapping from name to BGL vertex.
859 bgl_nodes.insert(std::make_pair(node, v));
860
861 // node_id_prop_ allows the caller to see the real id names for nodes.
862 vertex_props.push_back(boost::make_tuple(node_id_prop_, v, node));
863 }
864
865 void
866 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
867 {
868 bgl_edge_t result = edges_to_add.size();
869 edges_to_add.push_back(std::make_pair(bgl_nodes[source], bgl_nodes[target]));
870 bgl_edges.insert(std::make_pair(edge, result));
871 }
872
873 void
874 set_node_property(const id_t& key, const node_t& node, const id_t& value)
875 {
876 vertex_props.push_back(boost::make_tuple(key, bgl_nodes[node], value));
877 }
878
879 void
880 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
881 {
882 edge_props.push_back(boost::make_tuple(key, bgl_edges[edge], value));
883 }
884
885 void
886 set_graph_property(const id_t& key, const id_t& value)
887 {
888 /* RG: pointer to graph prevents copying */
889 put(key, dp_, &graph_, value);
890 }
891
892
893 protected:
894 CSRGraph& graph_;
895 dynamic_properties& dp_;
896 bgl_vertex_t vertex_count;
897 std::string node_id_prop_;
898 std::vector<boost::tuple<id_t, bgl_vertex_t, id_t> > vertex_props;
899 std::vector<boost::tuple<id_t, bgl_edge_t, id_t> > edge_props;
900 std::vector<std::pair<bgl_vertex_t, bgl_vertex_t> > edges_to_add;
901 std::map<node_t, bgl_vertex_t> bgl_nodes;
902 std::map<edge_t, bgl_edge_t> bgl_edges;
903};
904
905} } } // end namespace boost::detail::graph
906
907#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
908# ifndef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
909# define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
910# endif
911# include <boost/graph/detail/read_graphviz_spirit.hpp>
912#else // New default parser
913# include <boost/graph/detail/read_graphviz_new.hpp>
914#endif // BOOST_GRAPH_USE_SPIRIT_PARSER
915
916namespace boost {
917
918// Parse the passed string as a GraphViz dot file.
919template <typename MutableGraph>
920bool read_graphviz(const std::string& data,
921 MutableGraph& graph,
922 dynamic_properties& dp,
923 std::string const& node_id = "node_id") {
924#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
925 return read_graphviz_spirit(data.begin(), data.end(), graph, dp, node_id);
926#else // Non-Spirit parser
927 return read_graphviz_new(data,graph,dp,node_id);
928#endif
929}
930
931// Parse the passed iterator range as a GraphViz dot file.
932template <typename InputIterator, typename MutableGraph>
933bool read_graphviz(InputIterator user_first,
934 InputIterator user_last,
935 MutableGraph& graph,
936 dynamic_properties& dp,
937 std::string const& node_id = "node_id") {
938#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
939 typedef InputIterator is_t;
940 typedef boost::spirit::classic::multi_pass<is_t> iterator_t;
941
942 iterator_t first(boost::spirit::classic::make_multi_pass(user_first));
943 iterator_t last(boost::spirit::classic::make_multi_pass(user_last));
944
945 return read_graphviz_spirit(first, last, graph, dp, node_id);
946#else // Non-Spirit parser
947 return read_graphviz_new(std::string(user_first, user_last), graph, dp, node_id);
948#endif
949}
950
951// Parse the passed stream as a GraphViz dot file.
952template <typename MutableGraph>
953bool read_graphviz(std::istream& in, MutableGraph& graph,
954 dynamic_properties& dp,
955 std::string const& node_id = "node_id")
956{
957 typedef std::istream_iterator<char> is_t;
958 in >> std::noskipws;
959 return read_graphviz(is_t(in), is_t(), graph, dp, node_id);
960}
961
962} // namespace boost
963
964#ifdef BOOST_GRAPH_USE_MPI
965# include <boost/graph/distributed/graphviz.hpp>
966#endif
967
968#endif // BOOST_GRAPHVIZ_HPP