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