//=======================================================================

// Copyright 2001 University of Notre Dame.

// Copyright 2003 Jeremy Siek

// Authors: Lie-Quan Lee and Jeremy Siek

//

// Distributed under the Boost Software License, Version 1.0. (See

// accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//=======================================================================

#ifndef BOOST_GRAPHVIZ_HPP

#define BOOST_GRAPHVIZ_HPP

#include <boost/config.hpp>

#include <string>

#include <map>

#include <iostream>

#include <fstream>

#include <stdio.h> // for FILE

#include <boost/property_map.hpp>

#include <boost/tuple/tuple.hpp>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/properties.hpp>

#include <boost/graph/subgraph.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/dynamic_property_map.hpp>

#ifdef BOOST_HAS_DECLSPEC

#  if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_GRAPH_DYN_LINK)

#    ifdef BOOST_GRAPH_SOURCE

#      define BOOST_GRAPH_DECL __declspec(dllexport)

#    else

#      define BOOST_GRAPH_DECL __declspec(dllimport)

#    endif  // BOOST_GRAPH_SOURCE

#  endif  // DYN_LINK

#endif  // BOOST_HAS_DECLSPEC

#ifndef BOOST_GRAPH_DECL

#  define BOOST_GRAPH_DECL

#endif

namespace boost {

  template <typename directed_category>

  struct graphviz_io_traits {

    static std::string name() {

      return "digraph";

    }

    static std::string delimiter() {

      return "->";

    }  };

  template <>

  struct graphviz_io_traits <undirected_tag> {

    static std::string name() {

      return "graph";

    }

    static std::string delimiter() {

      return "--";

    }

  };

  struct default_writer {

    void operator()(std::ostream&) const {

    }

    template <class VorE>

    void operator()(std::ostream&, const VorE&) const {

    }

  };

  template <class Name>

  class label_writer {

  public:

    label_writer(Name _name) : name(_name) {}

    template <class VertexOrEdge>

    void operator()(std::ostream& out, const VertexOrEdge& v) const {

      out << "[label=\"" << get(name, v) << "\"]";

    }

  private:

    Name name;

  };

  template <class Name>

  inline label_writer<Name>

  make_label_writer(Name n) {

    return label_writer<Name>(n);

  }

  enum edge_attribute_t        { edge_attribute        = 1111 };

  enum vertex_attribute_t      { vertex_attribute      = 2222 };

  enum graph_graph_attribute_t { graph_graph_attribute = 3333 };

  enum graph_vertex_attribute_t  { graph_vertex_attribute  = 4444 };

  enum graph_edge_attribute_t  { graph_edge_attribute  = 5555 };

  BOOST_INSTALL_PROPERTY(edge, attribute);

  BOOST_INSTALL_PROPERTY(vertex, attribute);

  BOOST_INSTALL_PROPERTY(graph, graph_attribute);

  BOOST_INSTALL_PROPERTY(graph, vertex_attribute);

  BOOST_INSTALL_PROPERTY(graph, edge_attribute);

  template <class Attribute>

  inline void write_attributes(const Attribute& attr, std::ostream& out) {

    typename Attribute::const_iterator i, iend;

    i    = attr.begin();

    iend = attr.end();

    while ( i != iend ) {

      out << i->first << "=\"" << i->second << "\"";

      ++i;

      if ( i != iend )

        out << ", ";

    }

  }

  template<typename Attributes>

  inline void write_all_attributes(Attributes attributes,

                                   const std::string& name,

                                   std::ostream& out)

  {

    typename Attributes::const_iterator i = attributes.begin(),

                                        end = attributes.end();

    if (i != end) {

      out << name << " [\n";

      write_attributes(attributes, out);

      out << "];\n";

    }

  }

  inline void write_all_attributes(detail::error_property_not_found,

                                   const std::string&,

                                   std::ostream&)

  {

    // Do nothing - no attributes exist

  }

  template <typename GraphGraphAttributes,

            typename GraphNodeAttributes,

            typename GraphEdgeAttributes>

  struct graph_attributes_writer

  {

    graph_attributes_writer(GraphGraphAttributes gg,

                            GraphNodeAttributes gn,

                            GraphEdgeAttributes ge)

      : g_attributes(gg), n_attributes(gn), e_attributes(ge) { }

    void operator()(std::ostream& out) const {

      write_all_attributes(g_attributes, "graph", out);

      write_all_attributes(n_attributes, "node", out);

      write_all_attributes(e_attributes, "edge", out);

    }

    GraphGraphAttributes g_attributes;

    GraphNodeAttributes n_attributes;

    GraphEdgeAttributes e_attributes;

  };

  template <typename GAttrMap, typename NAttrMap, typename EAttrMap>

  graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>

  make_graph_attributes_writer(const GAttrMap& g_attr, const NAttrMap& n_attr,

                              const EAttrMap& e_attr) {

    return graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap>

      (g_attr, n_attr, e_attr);

  }

  template <typename Graph>

  graph_attributes_writer

    <typename graph_property<Graph, graph_graph_attribute_t>::type,

     typename graph_property<Graph, graph_vertex_attribute_t>::type,

     typename graph_property<Graph, graph_edge_attribute_t>::type>

  make_graph_attributes_writer(const Graph& g)

  {

    typedef typename graph_property<Graph, graph_graph_attribute_t>::type

      GAttrMap;

    typedef typename graph_property<Graph, graph_vertex_attribute_t>::type

      NAttrMap;

    typedef typename graph_property<Graph, graph_edge_attribute_t>::type

      EAttrMap;

    GAttrMap gam = get_property(g, graph_graph_attribute);

    NAttrMap nam = get_property(g, graph_vertex_attribute);

    EAttrMap eam = get_property(g, graph_edge_attribute);

    graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);

    return writer;

  }

  template <typename AttributeMap>

  struct attributes_writer {

    attributes_writer(AttributeMap attr)

      : attributes(attr) { }

    template <class VorE>

    void operator()(std::ostream& out, const VorE& e) const {

      this->write_attribute(out, attributes[e]);

    }

    private:

      template<typename AttributeSequence>

      void write_attribute(std::ostream& out,

                           const AttributeSequence& seq) const

      {

        if (!seq.empty()) {

          out << "[";

          write_attributes(seq, out);

          out << "]";

        }

      }

      void write_attribute(std::ostream&,

                           detail::error_property_not_found) const

      {

      }

    AttributeMap attributes;

  };

  template <typename Graph>

  attributes_writer

    <typename property_map<Graph, edge_attribute_t>::const_type>

  make_edge_attributes_writer(const Graph& g)

  {

    typedef typename property_map<Graph, edge_attribute_t>::const_type

      EdgeAttributeMap;

    return attributes_writer<EdgeAttributeMap>(get(edge_attribute, g));

  }

  template <typename Graph>

  attributes_writer

    <typename property_map<Graph, vertex_attribute_t>::const_type>

  make_vertex_attributes_writer(const Graph& g)

  {

    typedef typename property_map<Graph, vertex_attribute_t>::const_type

      VertexAttributeMap;

    return attributes_writer<VertexAttributeMap>(get(vertex_attribute, g));

  }

  template <typename Graph, typename VertexPropertiesWriter,

            typename EdgePropertiesWriter, typename GraphPropertiesWriter,

            typename VertexID>

  inline void write_graphviz(std::ostream& out, const Graph& g,

                             VertexPropertiesWriter vpw,

                             EdgePropertiesWriter epw,

                             GraphPropertiesWriter gpw,

                             VertexID vertex_id)

  {

    typedef typename graph_traits<Graph>::directed_category cat_type;

    typedef graphviz_io_traits<cat_type> Traits;

    std::string name = "G";

    out << Traits::name() << " " << name << " {" << std::endl;

    gpw(out); //print graph properties

    typename graph_traits<Graph>::vertex_iterator i, end;

    for(tie(i,end) = vertices(g); i != end; ++i) {

      out << get(vertex_id, *i);

      vpw(out, *i); //print vertex attributes

      out << ";" << std::endl;

    }

    typename graph_traits<Graph>::edge_iterator ei, edge_end;

    for(tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {

      out << get(vertex_id, source(*ei, g)) << Traits::delimiter() << get(vertex_id, target(*ei, g)) << " ";

      epw(out, *ei); //print edge attributes

      out << ";" << std::endl;

    }

    out << "}" << std::endl;

  }

  template <typename Graph, typename VertexPropertiesWriter,

            typename EdgePropertiesWriter, typename GraphPropertiesWriter>

  inline void write_graphviz(std::ostream& out, const Graph& g,

                             VertexPropertiesWriter vpw,

                             EdgePropertiesWriter epw,

                             GraphPropertiesWriter gpw)

  { write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g)); }

#if !defined(BOOST_MSVC) || BOOST_MSVC > 1300

  // ambiguous overload problem with VC++

  template <typename Graph>

  inline void

  write_graphviz(std::ostream& out, const Graph& g) {

    default_writer dw;

    default_writer gw;

    write_graphviz(out, g, dw, dw, gw);

  }

#endif

  template <typename Graph, typename VertexWriter>

  inline void

  write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw) {

    default_writer dw;

    default_writer gw;

    write_graphviz(out, g, vw, dw, gw);

  }

  template <typename Graph, typename VertexWriter, typename EdgeWriter>

  inline void

  write_graphviz(std::ostream& out, const Graph& g,

                 VertexWriter vw, EdgeWriter ew) {

    default_writer gw;

    write_graphviz(out, g, vw, ew, gw);

  }

  namespace detail {

    template <class Graph_, class RandomAccessIterator, class VertexID>

    void write_graphviz_subgraph (std::ostream& out,

                                  const subgraph<Graph_>& g,

                                  RandomAccessIterator vertex_marker,

                                  RandomAccessIterator edge_marker,

                                  VertexID vertex_id)

    {

      typedef subgraph<Graph_> Graph;

      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

      typedef typename graph_traits<Graph>::directed_category cat_type;

      typedef graphviz_io_traits<cat_type> Traits;

      typedef typename graph_property<Graph, graph_name_t>::type NameType;

      const NameType& g_name = get_property(g, graph_name);

      if ( g.is_root() )

        out << Traits::name() ;

      else

        out << "subgraph";

      out << " " << g_name << " {" << std::endl;

      typename Graph::const_children_iterator i_child, j_child;

      //print graph/node/edge attributes

#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300

      typedef typename graph_property<Graph, graph_graph_attribute_t>::type

        GAttrMap;

      typedef typename graph_property<Graph, graph_vertex_attribute_t>::type

        NAttrMap;

      typedef typename graph_property<Graph, graph_edge_attribute_t>::type

        EAttrMap;

      GAttrMap gam = get_property(g, graph_graph_attribute);

      NAttrMap nam = get_property(g, graph_vertex_attribute);

      EAttrMap eam = get_property(g, graph_edge_attribute);

      graph_attributes_writer<GAttrMap, NAttrMap, EAttrMap> writer(gam, nam, eam);

      writer(out);

#else

      make_graph_attributes_writer(g)(out);

#endif

      //print subgraph

      for ( tie(i_child,j_child) = g.children();

            i_child != j_child; ++i_child )

        write_graphviz_subgraph(out, *i_child, vertex_marker, edge_marker,

                                vertex_id);

      // Print out vertices and edges not in the subgraphs.

      typename graph_traits<Graph>::vertex_iterator i, end;

      typename graph_traits<Graph>::edge_iterator ei, edge_end;

      for(tie(i,end) = vertices(g); i != end; ++i) {

        Vertex v = g.local_to_global(*i);

        int pos = get(vertex_id, v);

        if ( vertex_marker[pos] ) {

          vertex_marker[pos] = false;

          out << pos;

#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300

          typedef typename property_map<Graph, vertex_attribute_t>::const_type

            VertexAttributeMap;

          attributes_writer<VertexAttributeMap> vawriter(get(vertex_attribute,

                                                             g.root()));

          vawriter(out, v);

#else

          make_vertex_attributes_writer(g.root())(out, v);

#endif

          out << ";" << std::endl;

        }

      }

      for (tie(ei, edge_end) = edges(g); ei != edge_end; ++ei) {

        Vertex u = g.local_to_global(source(*ei,g)),

          v = g.local_to_global(target(*ei, g));

        int pos = get(get(edge_index, g.root()), g.local_to_global(*ei));

        if ( edge_marker[pos] ) {

          edge_marker[pos] = false;

          out << get(vertex_id, u) << " " << Traits::delimiter()

              << " " << get(vertex_id, v);

#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300

          typedef typename property_map<Graph, edge_attribute_t>::const_type

            EdgeAttributeMap;

          attributes_writer<EdgeAttributeMap> eawriter(get(edge_attribute, g));

          eawriter(out, *ei);

#else

          make_edge_attributes_writer(g)(out, *ei); //print edge properties

#endif

          out << ";" << std::endl;

        }

      }

      out << "}" << std::endl;

    }

  } // namespace detail

  // requires graph_name graph property

  template <typename Graph>

  void write_graphviz(std::ostream& out, const subgraph<Graph>& g) {

    std::vector<bool> edge_marker(num_edges(g), true);

    std::vector<bool> vertex_marker(num_vertices(g), true);

    detail::write_graphviz_subgraph(out, g,

                                    vertex_marker.begin(),

                                    edge_marker.begin(), 

                                    get(vertex_index, g));

  }

  template <typename Graph>

  void write_graphviz(const std::string& filename, const subgraph<Graph>& g) {

    std::ofstream out(filename.c_str());

    std::vector<bool> edge_marker(num_edges(g), true);

    std::vector<bool> vertex_marker(num_vertices(g), true);

    detail::write_graphviz_subgraph(out, g,

                                    vertex_marker.begin(),

                                    edge_marker.begin(),

                                    get(vertex_index, g));

  }

  template <typename Graph, typename VertexID>

  void write_graphviz(std::ostream& out, const subgraph<Graph>& g,

                      VertexID vertex_id) 

  {

    std::vector<bool> edge_marker(num_edges(g), true);

    std::vector<bool> vertex_marker(num_vertices(g), true);

    detail::write_graphviz_subgraph(out, g,

                                    vertex_marker.begin(),

                                    edge_marker.begin(), 

                                    vertex_id);

  }

  template <typename Graph, typename VertexID>

  void write_graphviz(const std::string& filename, const subgraph<Graph>& g,

                      VertexID vertex_id) 

  {

    std::ofstream out(filename.c_str());

    std::vector<bool> edge_marker(num_edges(g), true);

    std::vector<bool> vertex_marker(num_vertices(g), true);

    detail::write_graphviz_subgraph(out, g,

                                    vertex_marker.begin(),

                                    edge_marker.begin(),

                                    vertex_id);

  }

  typedef std::map<std::string, std::string> GraphvizAttrList;

  typedef property<vertex_attribute_t, GraphvizAttrList>

          GraphvizVertexProperty;

  typedef property<edge_attribute_t, GraphvizAttrList,

                   property<edge_index_t, int> >

          GraphvizEdgeProperty;

  typedef property<graph_graph_attribute_t, GraphvizAttrList,

                   property<graph_vertex_attribute_t, GraphvizAttrList,

                   property<graph_edge_attribute_t, GraphvizAttrList,

                   property<graph_name_t, std::string> > > >

          GraphvizGraphProperty;

  typedef subgraph<adjacency_list<vecS,

                   vecS, directedS,

                   GraphvizVertexProperty,

                   GraphvizEdgeProperty,

                   GraphvizGraphProperty> >

          GraphvizDigraph;

  typedef subgraph<adjacency_list<vecS,

                   vecS, undirectedS,

                   GraphvizVertexProperty,

                   GraphvizEdgeProperty,

                   GraphvizGraphProperty> >

          GraphvizGraph;

  // These four require linking the BGL-Graphviz library: libbgl-viz.a

  // from the /src directory.

  extern void read_graphviz(const std::string& file, GraphvizDigraph& g);

  extern void read_graphviz(FILE* file, GraphvizDigraph& g);

  extern void read_graphviz(const std::string& file, GraphvizGraph& g);

  extern void read_graphviz(FILE* file, GraphvizGraph& g);

  class dynamic_properties_writer

  {

  public:

    dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) { }

    template<typename Descriptor>

    void operator()(std::ostream& out, Descriptor key) const

    {

      bool first = true;

      for (dynamic_properties::const_iterator i = dp->begin(); 

           i != dp->end(); ++i) {

        if (typeid(key) == i->second->key()) {

          if (first) out << " [";

          else out << ", ";

          first = false;

          out << i->first << "=\"" << i->second->get_string(key) << "\"";

        }

      }

      if (!first) out << "]";

    }

  private:

    const dynamic_properties* dp;

  };

  class dynamic_vertex_properties_writer

  {

  public:

    dynamic_vertex_properties_writer(const dynamic_properties& dp,

                                     const std::string& node_id) 

      : dp(&dp), node_id(&node_id) { }

    template<typename Descriptor>

    void operator()(std::ostream& out, Descriptor key) const

    {

      bool first = true;

      for (dynamic_properties::const_iterator i = dp->begin(); 

           i != dp->end(); ++i) {

        if (typeid(key) == i->second->key()