epoc32/include/stdapis/boost/graph/graphviz.hpp
branchSymbian2
changeset 2 2fe1408b6811
     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