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

// 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()

            && i->first != *node_id) {

          if (first) out << " [";

          else out << ", ";

          first = false;

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

        }

      }

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

    }

  private:

    const dynamic_properties* dp;

    const std::string* node_id;

  };

  namespace graph { namespace detail {

    template<typename Vertex>

    struct node_id_property_map

    {

      typedef std::string value_type;

      typedef value_type reference;

      typedef Vertex key_type;

      typedef readable_property_map_tag category;

      node_id_property_map() {}

      node_id_property_map(const dynamic_properties& dp,

                           const std::string& node_id)

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

      const dynamic_properties* dp;

      const std::string* node_id;

    };

    template<typename Vertex>

    inline std::string 

    get(node_id_property_map<Vertex> pm, 

        typename node_id_property_map<Vertex>::key_type v)

    { return get(*pm.node_id, *pm.dp, v); }

  } } // end namespace graph::detail

  template<typename Graph>

  inline void

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

                 const dynamic_properties& dp, 

                 const std::string& node_id = "node_id")

  {

    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    write_graphviz(out, g, dp, node_id,

                   graph::detail::node_id_property_map<Vertex>(dp, node_id));

  }

  template<typename Graph, typename VertexID>

  void

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

                 const dynamic_properties& dp, const std::string& node_id,

                 VertexID id)

  {

    write_graphviz

      (out, g,

       /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),

       /*edge_writer=*/dynamic_properties_writer(dp),

       /*graph_writer=*/default_writer(),

       id);

  }

/////////////////////////////////////////////////////////////////////////////

// Graph reader exceptions

/////////////////////////////////////////////////////////////////////////////

struct graph_exception : public std::exception {

  virtual ~graph_exception() throw() {}

  virtual const char* what() const throw() = 0;

};

struct bad_parallel_edge : public graph_exception {

  std::string from;

  std::string to;

  mutable std::string statement;

  bad_parallel_edge(const std::string& i, const std::string& j) :

    from(i), to(j) {}

  virtual ~bad_parallel_edge() throw() {}

  const char* what() const throw() {

    if(statement.empty())

      statement =

        std::string("Failed to add parallel edge: (")

        + from +  "," + to + ")\n";

    return statement.c_str();

  }

};

struct directed_graph_error : public graph_exception {

  virtual ~directed_graph_error() throw() {}

  virtual const char* what() const throw() {

    return

      "read_graphviz: "

      "Tried to read a directed graph into an undirected graph.";

  }

};

struct undirected_graph_error : public graph_exception {

  virtual ~undirected_graph_error() throw() {}

  virtual const char* what() const throw() {

    return

      "read_graphviz: "

      "Tried to read an undirected graph into a directed graph.";

  }

};

namespace detail { namespace graph {

typedef std::string id_t;

typedef id_t node_t;

// edges are not uniquely determined by adjacent nodes

class edge_t {

  int idx_;

  explicit edge_t(int i) : idx_(i) {}

public:

  static edge_t new_edge() {

    static int idx = 0;

    return edge_t(idx++);

  };

  bool operator==(const edge_t& rhs) const {

    return idx_ == rhs.idx_;

  }

  bool operator<(const edge_t& rhs) const {

    return idx_ < rhs.idx_;

  }

};

class mutate_graph

{

 public:

  virtual ~mutate_graph() {}

  virtual bool is_directed() const = 0;

  virtual void do_add_vertex(const node_t& node) = 0;

  virtual void 

  do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)

    = 0;

  virtual void 

  set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0;

  virtual void 

  set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0;

};

template<typename MutableGraph>

class mutate_graph_impl : public mutate_graph

{

  typedef typename graph_traits<MutableGraph>::vertex_descriptor bgl_vertex_t;

  typedef typename graph_traits<MutableGraph>::edge_descriptor   bgl_edge_t;

 public:

  mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp,

                    std::string node_id_prop)

    : graph_(graph), dp_(dp), node_id_prop_(node_id_prop) { }

  ~mutate_graph_impl() {}

  bool is_directed() const

  {

    return 

      boost::is_convertible<

        typename boost::graph_traits<MutableGraph>::directed_category,

        boost::directed_tag>::value;

  }

  virtual void do_add_vertex(const node_t& node)

  {

    // Add the node to the graph.

    bgl_vertex_t v = add_vertex(graph_);

    // Set up a mapping from name to BGL vertex.

    bgl_nodes.insert(std::make_pair(node, v));

    // node_id_prop_ allows the caller to see the real id names for nodes.

    put(node_id_prop_, dp_, v, node);

  }

  void 

  do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)

  {

    std::pair<bgl_edge_t, bool> result =

     add_edge(bgl_nodes[source], bgl_nodes[target], graph_);

    if(!result.second) {

      // In the case of no parallel edges allowed

      throw bad_parallel_edge(source, target);

    } else {

      bgl_edges.insert(std::make_pair(edge, result.first));

    }

  }

  void

  set_node_property(const id_t& key, const node_t& node, const id_t& value)

  {

    put(key, dp_, bgl_nodes[node], value);

  }

  void

  set_edge_property(const id_t& key, const edge_t& edge, const id_t& value)

  {

    put(key, dp_, bgl_edges[edge], value);

  }

 protected:

  MutableGraph& graph_;

  dynamic_properties& dp_;

  std::string node_id_prop_;

  std::map<node_t, bgl_vertex_t> bgl_nodes;

  std::map<edge_t, bgl_edge_t> bgl_edges;

};

BOOST_GRAPH_DECL

bool read_graphviz(std::istream& in, mutate_graph& graph);

} } // end namespace detail::graph

// Parse the passed stream as a GraphViz dot file.

template <typename MutableGraph>

bool read_graphviz(std::istream& in, MutableGraph& graph,

                   dynamic_properties& dp,

                   std::string const& node_id = "node_id") 

{

  detail::graph::mutate_graph_impl<MutableGraph> m_graph(graph, dp, node_id);

  return detail::graph::read_graphviz(in, m_graph);

}

} // namespace boost

#ifdef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS

#  include <boost/graph/detail/read_graphviz_spirit.hpp>

#endif // BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS

#endif // BOOST_GRAPHVIZ_HPP