1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/graphviz.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,772 @@
1.4 +//=======================================================================
1.5 +// Copyright 2001 University of Notre Dame.
1.6 +// Copyright 2003 Jeremy Siek
1.7 +// Authors: Lie-Quan Lee and Jeremy Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +#ifndef BOOST_GRAPHVIZ_HPP
1.14 +#define BOOST_GRAPHVIZ_HPP
1.15 +
1.16 +#include <boost/config.hpp>
1.17 +#include <string>
1.18 +#include <map>
1.19 +#include <iostream>
1.20 +#include <fstream>
1.21 +#include <stdio.h> // for FILE
1.22 +#include <boost/property_map.hpp>
1.23 +#include <boost/tuple/tuple.hpp>
1.24 +#include <boost/graph/graph_traits.hpp>
1.25 +#include <boost/graph/properties.hpp>
1.26 +#include <boost/graph/subgraph.hpp>
1.27 +#include <boost/graph/adjacency_list.hpp>
1.28 +#include <boost/dynamic_property_map.hpp>
1.29 +
1.30 +#ifdef BOOST_HAS_DECLSPEC
1.31 +# if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_GRAPH_DYN_LINK)
1.32 +# ifdef BOOST_GRAPH_SOURCE
1.33 +# define BOOST_GRAPH_DECL __declspec(dllexport)
1.34 +# else
1.35 +# define BOOST_GRAPH_DECL __declspec(dllimport)
1.36 +# endif // BOOST_GRAPH_SOURCE
1.37 +# endif // DYN_LINK
1.38 +#endif // BOOST_HAS_DECLSPEC
1.39 +
1.40 +#ifndef BOOST_GRAPH_DECL
1.41 +# define BOOST_GRAPH_DECL
1.42 +#endif
1.43 +
1.44 +namespace boost {
1.45 +
1.46 + template <typename directed_category>
1.47 + struct graphviz_io_traits {
1.48 + static std::string name() {
1.49 + return "digraph";
1.50 + }
1.51 + static std::string delimiter() {
1.52 + return "->";
1.53 + } };
1.54 +
1.55 + template <>
1.56 + struct graphviz_io_traits <undirected_tag> {
1.57 + static std::string name() {
1.58 + return "graph";
1.59 + }
1.60 + static std::string delimiter() {
1.61 + return "--";
1.62 + }
1.63 + };
1.64 +
1.65 + struct default_writer {
1.66 + void operator()(std::ostream&) const {
1.67 + }
1.68 + template <class VorE>
1.69 + void operator()(std::ostream&, const VorE&) const {
1.70 + }
1.71 + };
1.72 +
1.73 + template <class Name>
1.74 + class label_writer {
1.75 + public:
1.76 + label_writer(Name _name) : name(_name) {}
1.77 + template <class VertexOrEdge>
1.78 + void operator()(std::ostream& out, const VertexOrEdge& v) const {
1.79 + out << "[label=\"" << get(name, v) << "\"]";
1.80 + }
1.81 + private:
1.82 + Name name;
1.83 + };
1.84 + template <class Name>
1.85 + inline label_writer<Name>
1.86 + make_label_writer(Name n) {
1.87 + return label_writer<Name>(n);
1.88 + }
1.89 +
1.90 + enum edge_attribute_t { edge_attribute = 1111 };
1.91 + enum vertex_attribute_t { vertex_attribute = 2222 };
1.92 + enum graph_graph_attribute_t { graph_graph_attribute = 3333 };
1.93 + enum graph_vertex_attribute_t { graph_vertex_attribute = 4444 };
1.94 + enum graph_edge_attribute_t { graph_edge_attribute = 5555 };
1.95 +
1.96 + BOOST_INSTALL_PROPERTY(edge, attribute);
1.97 + BOOST_INSTALL_PROPERTY(vertex, attribute);
1.98 + BOOST_INSTALL_PROPERTY(graph, graph_attribute);
1.99 + BOOST_INSTALL_PROPERTY(graph, vertex_attribute);
1.100 + BOOST_INSTALL_PROPERTY(graph, edge_attribute);
1.101 +
1.102 +
1.103 + template <class Attribute>
1.104 + inline void write_attributes(const Attribute& attr, std::ostream& out) {
1.105 + typename Attribute::const_iterator i, iend;
1.106 + i = attr.begin();
1.107 + iend = attr.end();
1.108 +
1.109 + while ( i != iend ) {
1.110 + out << i->first << "=\"" << i->second << "\"";
1.111 + ++i;
1.112 + if ( i != iend )
1.113 + out << ", ";
1.114 + }
1.115 + }
1.116 +
1.117 + template<typename Attributes>
1.118 + inline void write_all_attributes(Attributes attributes,
1.119 + const std::string& name,
1.120 + std::ostream& out)
1.121 + {
1.122 + typename Attributes::const_iterator i = attributes.begin(),
1.123 + end = attributes.end();
1.124 + if (i != end) {
1.125 + out << name << " [\n";
1.126 + write_attributes(attributes, out);
1.127 + out << "];\n";
1.128 + }
1.129 + }
1.130 +
1.131 + inline void write_all_attributes(detail::error_property_not_found,
1.132 + const std::string&,
1.133 + std::ostream&)
1.134 + {
1.135 + // Do nothing - no attributes exist
1.136 + }
1.137 +
1.138 +
1.139 +
1.140 +
1.141 + template <typename GraphGraphAttributes,
1.142 + typename GraphNodeAttributes,
1.143 + typename GraphEdgeAttributes>
1.144 + struct graph_attributes_writer
1.145 + {
1.146 + graph_attributes_writer(GraphGraphAttributes gg,
1.147 + GraphNodeAttributes gn,
1.148 + GraphEdgeAttributes ge)
1.149 + : g_attributes(gg), n_attributes(gn), e_attributes(ge) { }
1.150 +
1.151 + void operator()(std::ostream& out) const {
1.152 + write_all_attributes(g_attributes, "graph", out);
1.153 + write_all_attributes(n_attributes, "node", out);
1.154 + write_all_attributes(e_attributes, "edge", out);
1.155 + }
1.156 + GraphGraphAttributes g_attributes;
1.157 + GraphNodeAttributes n_attributes;
1.158 + GraphEdgeAttributes e_attributes;
1.159 + };
1.160 +
1.161 + template <typename GAttrMap, typename NAttrMap, typename EAttrMap>
1.162 + graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
1.163 + make_graph_attributes_writer(const GAttrMap& g_attr, const NAttrMap& n_attr,
1.164 + const EAttrMap& e_attr) {
1.165 + return graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>
1.166 + (g_attr, n_attr, e_attr);
1.167 + }
1.168 +
1.169 +
1.170 + template <typename Graph>
1.171 + graph_attributes_writer
1.172 + <typename graph_property<Graph, graph_graph_attribute_t>::type,
1.173 + typename graph_property<Graph, graph_vertex_attribute_t>::type,
1.174 + typename graph_property<Graph, graph_edge_attribute_t>::type>
1.175 + make_graph_attributes_writer(const Graph& g)
1.176 + {
1.177 + typedef typename graph_property<Graph, graph_graph_attribute_t>::type
1.178 + GAttrMap;
1.179 + typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
1.180 + NAttrMap;
1.181 + typedef typename graph_property<Graph, graph_edge_attribute_t>::type
1.182 + EAttrMap;
1.183 + GAttrMap gam = get_property(g, graph_graph_attribute);
1.184 + NAttrMap nam = get_property(g, graph_vertex_attribute);
1.185 + EAttrMap eam = get_property(g, graph_edge_attribute);
1.186 + graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
1.187 + return writer;
1.188 + }
1.189 +
1.190 + template <typename AttributeMap>
1.191 + struct attributes_writer {
1.192 + attributes_writer(AttributeMap attr)
1.193 + : attributes(attr) { }
1.194 +
1.195 + template <class VorE>
1.196 + void operator()(std::ostream& out, const VorE& e) const {
1.197 + this->write_attribute(out, attributes[e]);
1.198 + }
1.199 +
1.200 + private:
1.201 + template<typename AttributeSequence>
1.202 + void write_attribute(std::ostream& out,
1.203 + const AttributeSequence& seq) const
1.204 + {
1.205 + if (!seq.empty()) {
1.206 + out << "[";
1.207 + write_attributes(seq, out);
1.208 + out << "]";
1.209 + }
1.210 + }
1.211 +
1.212 + void write_attribute(std::ostream&,
1.213 + detail::error_property_not_found) const
1.214 + {
1.215 + }
1.216 + AttributeMap attributes;
1.217 + };
1.218 +
1.219 + template <typename Graph>
1.220 + attributes_writer
1.221 + <typename property_map<Graph, edge_attribute_t>::const_type>
1.222 + make_edge_attributes_writer(const Graph& g)
1.223 + {
1.224 + typedef typename property_map<Graph, edge_attribute_t>::const_type
1.225 + EdgeAttributeMap;
1.226 + return attributes_writer<EdgeAttributeMap>(get(edge_attribute, g));
1.227 + }
1.228 +
1.229 + template <typename Graph>
1.230 + attributes_writer
1.231 + <typename property_map<Graph, vertex_attribute_t>::const_type>
1.232 + make_vertex_attributes_writer(const Graph& g)
1.233 + {
1.234 + typedef typename property_map<Graph, vertex_attribute_t>::const_type
1.235 + VertexAttributeMap;
1.236 + return attributes_writer<VertexAttributeMap>(get(vertex_attribute, g));
1.237 + }
1.238 +
1.239 + template <typename Graph, typename VertexPropertiesWriter,
1.240 + typename EdgePropertiesWriter, typename GraphPropertiesWriter,
1.241 + typename VertexID>
1.242 + inline void write_graphviz(std::ostream& out, const Graph& g,
1.243 + VertexPropertiesWriter vpw,
1.244 + EdgePropertiesWriter epw,
1.245 + GraphPropertiesWriter gpw,
1.246 + VertexID vertex_id)
1.247 + {
1.248 + typedef typename graph_traits<Graph>::directed_category cat_type;
1.249 + typedef graphviz_io_traits<cat_type> Traits;
1.250 + std::string name = "G";
1.251 + out << Traits::name() << " " << name << " {" << std::endl;
1.252 +
1.253 + gpw(out); //print graph properties
1.254 +
1.255 + typename graph_traits<Graph>::vertex_iterator i, end;
1.256 +
1.257 + for(tie(i,end) = vertices(g); i != end; ++i) {
1.258 + out << get(vertex_id, *i);
1.259 + vpw(out, *i); //print vertex attributes
1.260 + out << ";" << std::endl;
1.261 + }
1.262 + typename graph_traits<Graph>::edge_iterator ei, edge_end;
1.263 + for(tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
1.264 + out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " ";
1.265 + epw(out, *ei); //print edge attributes
1.266 + out << ";" << std::endl;
1.267 + }
1.268 + out << "}" << std::endl;
1.269 + }
1.270 +
1.271 + template <typename Graph, typename VertexPropertiesWriter,
1.272 + typename EdgePropertiesWriter, typename GraphPropertiesWriter>
1.273 + inline void write_graphviz(std::ostream& out, const Graph& g,
1.274 + VertexPropertiesWriter vpw,
1.275 + EdgePropertiesWriter epw,
1.276 + GraphPropertiesWriter gpw)
1.277 + { write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g)); }
1.278 +
1.279 +#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1.280 + // ambiguous overload problem with VC++
1.281 + template <typename Graph>
1.282 + inline void
1.283 + write_graphviz(std::ostream& out, const Graph& g) {
1.284 + default_writer dw;
1.285 + default_writer gw;
1.286 + write_graphviz(out, g, dw, dw, gw);
1.287 + }
1.288 +#endif
1.289 +
1.290 + template <typename Graph, typename VertexWriter>
1.291 + inline void
1.292 + write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw) {
1.293 + default_writer dw;
1.294 + default_writer gw;
1.295 + write_graphviz(out, g, vw, dw, gw);
1.296 + }
1.297 +
1.298 + template <typename Graph, typename VertexWriter, typename EdgeWriter>
1.299 + inline void
1.300 + write_graphviz(std::ostream& out, const Graph& g,
1.301 + VertexWriter vw, EdgeWriter ew) {
1.302 + default_writer gw;
1.303 + write_graphviz(out, g, vw, ew, gw);
1.304 + }
1.305 +
1.306 + namespace detail {
1.307 +
1.308 + template <class Graph_, class RandomAccessIterator, class VertexID>
1.309 + void write_graphviz_subgraph (std::ostream& out,
1.310 + const subgraph<Graph_>& g,
1.311 + RandomAccessIterator vertex_marker,
1.312 + RandomAccessIterator edge_marker,
1.313 + VertexID vertex_id)
1.314 + {
1.315 + typedef subgraph<Graph_> Graph;
1.316 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.317 + typedef typename graph_traits<Graph>::directed_category cat_type;
1.318 + typedef graphviz_io_traits<cat_type> Traits;
1.319 +
1.320 + typedef typename graph_property<Graph, graph_name_t>::type NameType;
1.321 + const NameType& g_name = get_property(g, graph_name);
1.322 +
1.323 + if ( g.is_root() )
1.324 + out << Traits::name() ;
1.325 + else
1.326 + out << "subgraph";
1.327 +
1.328 + out << " " << g_name << " {" << std::endl;
1.329 +
1.330 + typename Graph::const_children_iterator i_child, j_child;
1.331 +
1.332 + //print graph/node/edge attributes
1.333 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
1.334 + typedef typename graph_property<Graph, graph_graph_attribute_t>::type
1.335 + GAttrMap;
1.336 + typedef typename graph_property<Graph, graph_vertex_attribute_t>::type
1.337 + NAttrMap;
1.338 + typedef typename graph_property<Graph, graph_edge_attribute_t>::type
1.339 + EAttrMap;
1.340 + GAttrMap gam = get_property(g, graph_graph_attribute);
1.341 + NAttrMap nam = get_property(g, graph_vertex_attribute);
1.342 + EAttrMap eam = get_property(g, graph_edge_attribute);
1.343 + graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);
1.344 + writer(out);
1.345 +#else
1.346 + make_graph_attributes_writer(g)(out);
1.347 +#endif
1.348 +
1.349 + //print subgraph
1.350 + for ( tie(i_child,j_child) = g.children();
1.351 + i_child != j_child; ++i_child )
1.352 + write_graphviz_subgraph(out, *i_child, vertex_marker, edge_marker,
1.353 + vertex_id);
1.354 +
1.355 + // Print out vertices and edges not in the subgraphs.
1.356 +
1.357 + typename graph_traits<Graph>::vertex_iterator i, end;
1.358 + typename graph_traits<Graph>::edge_iterator ei, edge_end;
1.359 +
1.360 + for(tie(i,end) = vertices(g); i != end; ++i) {
1.361 + Vertex v = g.local_to_global(*i);
1.362 + int pos = get(vertex_id, v);
1.363 + if ( vertex_marker[pos] ) {
1.364 + vertex_marker[pos] = false;
1.365 + out << pos;
1.366 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
1.367 + typedef typename property_map<Graph, vertex_attribute_t>::const_type
1.368 + VertexAttributeMap;
1.369 + attributes_writer<VertexAttributeMap> vawriter(get(vertex_attribute,
1.370 + g.root()));
1.371 + vawriter(out, v);
1.372 +#else
1.373 + make_vertex_attributes_writer(g.root())(out, v);
1.374 +#endif
1.375 + out << ";" << std::endl;
1.376 + }
1.377 + }
1.378 +
1.379 + for (tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {
1.380 + Vertex u = g.local_to_global(source(*ei,g)),
1.381 + v = g.local_to_global(target(*ei, g));
1.382 + int pos = get(get(edge_index, g.root()), g.local_to_global(*ei));
1.383 + if ( edge_marker[pos] ) {
1.384 + edge_marker[pos] = false;
1.385 + out << get(vertex_id, u) << " " << Traits::delimiter()
1.386 + << " " << get(vertex_id, v);
1.387 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
1.388 + typedef typename property_map<Graph, edge_attribute_t>::const_type
1.389 + EdgeAttributeMap;
1.390 + attributes_writer<EdgeAttributeMap> eawriter(get(edge_attribute, g));
1.391 + eawriter(out, *ei);
1.392 +#else
1.393 + make_edge_attributes_writer(g)(out, *ei); //print edge properties
1.394 +#endif
1.395 + out << ";" << std::endl;
1.396 + }
1.397 + }
1.398 + out << "}" << std::endl;
1.399 + }
1.400 + } // namespace detail
1.401 +
1.402 + // requires graph_name graph property
1.403 + template <typename Graph>
1.404 + void write_graphviz(std::ostream& out, const subgraph<Graph>& g) {
1.405 + std::vector<bool> edge_marker(num_edges(g), true);
1.406 + std::vector<bool> vertex_marker(num_vertices(g), true);
1.407 +
1.408 + detail::write_graphviz_subgraph(out, g,
1.409 + vertex_marker.begin(),
1.410 + edge_marker.begin(),
1.411 + get(vertex_index, g));
1.412 + }
1.413 +
1.414 + template <typename Graph>
1.415 + void write_graphviz(const std::string& filename, const subgraph<Graph>& g) {
1.416 + std::ofstream out(filename.c_str());
1.417 + std::vector<bool> edge_marker(num_edges(g), true);
1.418 + std::vector<bool> vertex_marker(num_vertices(g), true);
1.419 +
1.420 + detail::write_graphviz_subgraph(out, g,
1.421 + vertex_marker.begin(),
1.422 + edge_marker.begin(),
1.423 + get(vertex_index, g));
1.424 + }
1.425 +
1.426 + template <typename Graph, typename VertexID>
1.427 + void write_graphviz(std::ostream& out, const subgraph<Graph>& g,
1.428 + VertexID vertex_id)
1.429 + {
1.430 + std::vector<bool> edge_marker(num_edges(g), true);
1.431 + std::vector<bool> vertex_marker(num_vertices(g), true);
1.432 +
1.433 + detail::write_graphviz_subgraph(out, g,
1.434 + vertex_marker.begin(),
1.435 + edge_marker.begin(),
1.436 + vertex_id);
1.437 + }
1.438 +
1.439 + template <typename Graph, typename VertexID>
1.440 + void write_graphviz(const std::string& filename, const subgraph<Graph>& g,
1.441 + VertexID vertex_id)
1.442 + {
1.443 + std::ofstream out(filename.c_str());
1.444 + std::vector<bool> edge_marker(num_edges(g), true);
1.445 + std::vector<bool> vertex_marker(num_vertices(g), true);
1.446 +
1.447 + detail::write_graphviz_subgraph(out, g,
1.448 + vertex_marker.begin(),
1.449 + edge_marker.begin(),
1.450 + vertex_id);
1.451 + }
1.452 +
1.453 + typedef std::map<std::string, std::string> GraphvizAttrList;
1.454 +
1.455 + typedef property<vertex_attribute_t, GraphvizAttrList>
1.456 + GraphvizVertexProperty;
1.457 +
1.458 + typedef property<edge_attribute_t, GraphvizAttrList,
1.459 + property<edge_index_t, int> >
1.460 + GraphvizEdgeProperty;
1.461 +
1.462 + typedef property<graph_graph_attribute_t, GraphvizAttrList,
1.463 + property<graph_vertex_attribute_t, GraphvizAttrList,
1.464 + property<graph_edge_attribute_t, GraphvizAttrList,
1.465 + property<graph_name_t, std::string> > > >
1.466 + GraphvizGraphProperty;
1.467 +
1.468 + typedef subgraph<adjacency_list<vecS,
1.469 + vecS, directedS,
1.470 + GraphvizVertexProperty,
1.471 + GraphvizEdgeProperty,
1.472 + GraphvizGraphProperty> >
1.473 + GraphvizDigraph;
1.474 +
1.475 + typedef subgraph<adjacency_list<vecS,
1.476 + vecS, undirectedS,
1.477 + GraphvizVertexProperty,
1.478 + GraphvizEdgeProperty,
1.479 + GraphvizGraphProperty> >
1.480 + GraphvizGraph;
1.481 +
1.482 +
1.483 + // These four require linking the BGL-Graphviz library: libbgl-viz.a
1.484 + // from the /src directory.
1.485 + extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
1.486 + extern void read_graphviz(FILE* file, GraphvizDigraph& g);
1.487 +
1.488 + extern void read_graphviz(const std::string& file, GraphvizGraph& g);
1.489 + extern void read_graphviz(FILE* file, GraphvizGraph& g);
1.490 +
1.491 + class dynamic_properties_writer
1.492 + {
1.493 + public:
1.494 + dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) { }
1.495 +
1.496 + template<typename Descriptor>
1.497 + void operator()(std::ostream& out, Descriptor key) const
1.498 + {
1.499 + bool first = true;
1.500 + for (dynamic_properties::const_iterator i = dp->begin();
1.501 + i != dp->end(); ++i) {
1.502 + if (typeid(key) == i->second->key()) {
1.503 + if (first) out << " [";
1.504 + else out << ", ";
1.505 + first = false;
1.506 +
1.507 + out << i->first << "=\"" << i->second->get_string(key) << "\"";
1.508 + }
1.509 + }
1.510 +
1.511 + if (!first) out << "]";
1.512 + }
1.513 +
1.514 + private:
1.515 + const dynamic_properties* dp;
1.516 + };
1.517 +
1.518 + class dynamic_vertex_properties_writer
1.519 + {
1.520 + public:
1.521 + dynamic_vertex_properties_writer(const dynamic_properties& dp,
1.522 + const std::string& node_id)
1.523 + : dp(&dp), node_id(&node_id) { }
1.524 +
1.525 + template<typename Descriptor>
1.526 + void operator()(std::ostream& out, Descriptor key) const
1.527 + {
1.528 + bool first = true;
1.529 + for (dynamic_properties::const_iterator i = dp->begin();
1.530 + i != dp->end(); ++i) {
1.531 + if (typeid(key) == i->second->key()
1.532 + && i->first != *node_id) {
1.533 + if (first) out << " [";
1.534 + else out << ", ";
1.535 + first = false;
1.536 +
1.537 + out << i->first << "=\"" << i->second->get_string(key) << "\"";
1.538 + }
1.539 + }
1.540 +
1.541 + if (!first) out << "]";
1.542 + }
1.543 +
1.544 + private:
1.545 + const dynamic_properties* dp;
1.546 + const std::string* node_id;
1.547 + };
1.548 +
1.549 + namespace graph { namespace detail {
1.550 +
1.551 + template<typename Vertex>
1.552 + struct node_id_property_map
1.553 + {
1.554 + typedef std::string value_type;
1.555 + typedef value_type reference;
1.556 + typedef Vertex key_type;
1.557 + typedef readable_property_map_tag category;
1.558 +
1.559 + node_id_property_map() {}
1.560 +
1.561 + node_id_property_map(const dynamic_properties& dp,
1.562 + const std::string& node_id)
1.563 + : dp(&dp), node_id(&node_id) { }
1.564 +
1.565 + const dynamic_properties* dp;
1.566 + const std::string* node_id;
1.567 + };
1.568 +
1.569 + template<typename Vertex>
1.570 + inline std::string
1.571 + get(node_id_property_map<Vertex> pm,
1.572 + typename node_id_property_map<Vertex>::key_type v)
1.573 + { return get(*pm.node_id, *pm.dp, v); }
1.574 +
1.575 + } } // end namespace graph::detail
1.576 +
1.577 + template<typename Graph>
1.578 + inline void
1.579 + write_graphviz(std::ostream& out, const Graph& g,
1.580 + const dynamic_properties& dp,
1.581 + const std::string& node_id = "node_id")
1.582 + {
1.583 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.584 + write_graphviz(out, g, dp, node_id,
1.585 + graph::detail::node_id_property_map<Vertex>(dp, node_id));
1.586 + }
1.587 +
1.588 + template<typename Graph, typename VertexID>
1.589 + void
1.590 + write_graphviz(std::ostream& out, const Graph& g,
1.591 + const dynamic_properties& dp, const std::string& node_id,
1.592 + VertexID id)
1.593 + {
1.594 + write_graphviz
1.595 + (out, g,
1.596 + /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),
1.597 + /*edge_writer=*/dynamic_properties_writer(dp),
1.598 + /*graph_writer=*/default_writer(),
1.599 + id);
1.600 + }
1.601 +
1.602 +/////////////////////////////////////////////////////////////////////////////
1.603 +// Graph reader exceptions
1.604 +/////////////////////////////////////////////////////////////////////////////
1.605 +struct graph_exception : public std::exception {
1.606 + virtual ~graph_exception() throw() {}
1.607 + virtual const char* what() const throw() = 0;
1.608 +};
1.609 +
1.610 +struct bad_parallel_edge : public graph_exception {
1.611 + std::string from;
1.612 + std::string to;
1.613 + mutable std::string statement;
1.614 + bad_parallel_edge(const std::string& i, const std::string& j) :
1.615 + from(i), to(j) {}
1.616 +
1.617 + virtual ~bad_parallel_edge() throw() {}
1.618 + const char* what() const throw() {
1.619 + if(statement.empty())
1.620 + statement =
1.621 + std::string("Failed to add parallel edge: (")
1.622 + + from + "," + to + ")\n";
1.623 +
1.624 + return statement.c_str();
1.625 + }
1.626 +};
1.627 +
1.628 +struct directed_graph_error : public graph_exception {
1.629 + virtual ~directed_graph_error() throw() {}
1.630 + virtual const char* what() const throw() {
1.631 + return
1.632 + "read_graphviz: "
1.633 + "Tried to read a directed graph into an undirected graph.";
1.634 + }
1.635 +};
1.636 +
1.637 +struct undirected_graph_error : public graph_exception {
1.638 + virtual ~undirected_graph_error() throw() {}
1.639 + virtual const char* what() const throw() {
1.640 + return
1.641 + "read_graphviz: "
1.642 + "Tried to read an undirected graph into a directed graph.";
1.643 + }
1.644 +};
1.645 +
1.646 +namespace detail { namespace graph {
1.647 +
1.648 +typedef std::string id_t;
1.649 +typedef id_t node_t;
1.650 +
1.651 +// edges are not uniquely determined by adjacent nodes
1.652 +class edge_t {
1.653 + int idx_;
1.654 + explicit edge_t(int i) : idx_(i) {}
1.655 +public:
1.656 + static edge_t new_edge() {
1.657 + static int idx = 0;
1.658 + return edge_t(idx++);
1.659 + };
1.660 +
1.661 + bool operator==(const edge_t& rhs) const {
1.662 + return idx_ == rhs.idx_;
1.663 + }
1.664 + bool operator<(const edge_t& rhs) const {
1.665 + return idx_ < rhs.idx_;
1.666 + }
1.667 +};
1.668 +
1.669 +class mutate_graph
1.670 +{
1.671 + public:
1.672 + virtual ~mutate_graph() {}
1.673 + virtual bool is_directed() const = 0;
1.674 + virtual void do_add_vertex(const node_t& node) = 0;
1.675 +
1.676 + virtual void
1.677 + do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
1.678 + = 0;
1.679 +
1.680 + virtual void
1.681 + set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0;
1.682 +
1.683 + virtual void
1.684 + set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0;
1.685 +};
1.686 +
1.687 +template<typename MutableGraph>
1.688 +class mutate_graph_impl : public mutate_graph
1.689 +{
1.690 + typedef typename graph_traits<MutableGraph>::vertex_descriptor bgl_vertex_t;
1.691 + typedef typename graph_traits<MutableGraph>::edge_descriptor bgl_edge_t;
1.692 +
1.693 + public:
1.694 + mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp,
1.695 + std::string node_id_prop)
1.696 + : graph_(graph), dp_(dp), node_id_prop_(node_id_prop) { }
1.697 +
1.698 + ~mutate_graph_impl() {}
1.699 +
1.700 + bool is_directed() const
1.701 + {
1.702 + return
1.703 + boost::is_convertible<
1.704 + typename boost::graph_traits<MutableGraph>::directed_category,
1.705 + boost::directed_tag>::value;
1.706 + }
1.707 +
1.708 + virtual void do_add_vertex(const node_t& node)
1.709 + {
1.710 + // Add the node to the graph.
1.711 + bgl_vertex_t v = add_vertex(graph_);
1.712 +
1.713 + // Set up a mapping from name to BGL vertex.
1.714 + bgl_nodes.insert(std::make_pair(node, v));
1.715 +
1.716 + // node_id_prop_ allows the caller to see the real id names for nodes.
1.717 + put(node_id_prop_, dp_, v, node);
1.718 + }
1.719 +
1.720 + void
1.721 + do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
1.722 + {
1.723 + std::pair<bgl_edge_t, bool> result =
1.724 + add_edge(bgl_nodes[source], bgl_nodes[target], graph_);
1.725 +
1.726 + if(!result.second) {
1.727 + // In the case of no parallel edges allowed
1.728 + throw bad_parallel_edge(source, target);
1.729 + } else {
1.730 + bgl_edges.insert(std::make_pair(edge, result.first));
1.731 + }
1.732 + }
1.733 +
1.734 + void
1.735 + set_node_property(const id_t& key, const node_t& node, const id_t& value)
1.736 + {
1.737 + put(key, dp_, bgl_nodes[node], value);
1.738 + }
1.739 +
1.740 + void
1.741 + set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)
1.742 + {
1.743 + put(key, dp_, bgl_edges[edge], value);
1.744 + }
1.745 +
1.746 + protected:
1.747 + MutableGraph& graph_;
1.748 + dynamic_properties& dp_;
1.749 + std::string node_id_prop_;
1.750 + std::map<node_t, bgl_vertex_t> bgl_nodes;
1.751 + std::map<edge_t, bgl_edge_t> bgl_edges;
1.752 +};
1.753 +
1.754 +BOOST_GRAPH_DECL
1.755 +bool read_graphviz(std::istream& in, mutate_graph& graph);
1.756 +
1.757 +} } // end namespace detail::graph
1.758 +
1.759 +// Parse the passed stream as a GraphViz dot file.
1.760 +template <typename MutableGraph>
1.761 +bool read_graphviz(std::istream& in, MutableGraph& graph,
1.762 + dynamic_properties& dp,
1.763 + std::string const& node_id = "node_id")
1.764 +{
1.765 + detail::graph::mutate_graph_impl<MutableGraph> m_graph(graph, dp, node_id);
1.766 + return detail::graph::read_graphviz(in, m_graph);
1.767 +}
1.768 +
1.769 +} // namespace boost
1.770 +
1.771 +#ifdef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
1.772 +# include <boost/graph/detail/read_graphviz_spirit.hpp>
1.773 +#endif // BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
1.774 +
1.775 +#endif // BOOST_GRAPHVIZ_HPP