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

// Copyright 2001 University of Notre Dame.

// Copyright 2003 Jeremy Siek

// Authors: Lie-Quan Lee, Jeremy Siek, and Douglas Gregor

//

// 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 <cstdio> // for FILE

#include <fstream>

#include <iostream>

#include <map>

#include <string>

#include <boost/property_map/property_map.hpp>

#include <boost/tuple/tuple.hpp>

#include <boost/graph/exception.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/property_map/dynamic_property_map.hpp>

#include <boost/graph/overloading.hpp>

#include <boost/graph/dll_import_export.hpp>

#include <boost/graph/compressed_sparse_row_graph.hpp>

#include <boost/graph/iteration_macros.hpp>

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

#include <boost/spirit/include/classic_multi_pass.hpp>

#include <boost/lexical_cast.hpp>

#include <boost/static_assert.hpp>

#include <boost/algorithm/string/replace.hpp>

#include <boost/xpressive/xpressive_static.hpp>

#include <boost/foreach.hpp>

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 < typename T > inline std::string escape_dot_string(const T& obj)

{

    using namespace boost::xpressive;

    static sregex valid_unquoted_id = (((alpha | '_') >> *_w)

        | (!as_xpr('-') >> (('.' >> *_d) | (+_d >> !('.' >> *_d)))));

    std::string s(boost::lexical_cast< std::string >(obj));

    if (regex_match(s, valid_unquoted_id))

    {

        return s;

    }

    else

    {

        boost::algorithm::replace_all(s, "\"", "\\\"");

        return "\"" + s + "\"";

    }

}

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=" << escape_dot_string(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 << "=" << escape_dot_string(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 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(

        Graph, vertex_list_graph_tag))

{

    BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< Graph >));

    typedef typename graph_traits< Graph >::directed_category cat_type;

    typedef graphviz_io_traits< cat_type > Traits;

    std::string name = "G";

    out << Traits::name() << " " << escape_dot_string(name) << " {"

        << std::endl;

    gpw(out); // print graph properties

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

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

    {

        out << escape_dot_string(get(vertex_id, *i));

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

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

    }

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

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

    {

        out << escape_dot_string(get(vertex_id, source(*ei, g)))

            << Traits::delimiter()

            << escape_dot_string(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 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(

        Graph, vertex_list_graph_tag))

{

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

}

template < typename Graph >

inline void write_graphviz(std::ostream& out,

    const Graph& g BOOST_GRAPH_ENABLE_IF_MODELS_PARM(

        Graph, vertex_list_graph_tag))

{

    default_writer dw;

    default_writer gw;

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

}

template < typename Graph, typename VertexWriter >

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

    VertexWriter vw BOOST_GRAPH_ENABLE_IF_MODELS_PARM(

        Graph, vertex_list_graph_tag))

{

    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 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(

        Graph, vertex_list_graph_tag))

{

    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 << " " << escape_dot_string(g_name) << " {" << std::endl;

        typename Graph::const_children_iterator i_child, j_child;

        // print graph/node/edge attributes

        make_graph_attributes_writer(g)(out);

        // print subgraph

        for (boost::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 (boost::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 << escape_dot_string(pos);

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

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

            }

        }

        for (boost::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 << escape_dot_string(get(vertex_id, u)) << " "

                    << Traits::delimiter() << " "

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

                make_edge_attributes_writer(g)(

                    out, *ei); // print edge properties

                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);

}

#if 0

  // This interface has not worked for a long time

  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.

  // Library has not existed for a while

  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);

#endif

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 << "="

                    << escape_dot_string(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 << "="

                    << escape_dot_string(i->second->get_string(key));

            }

        }

        if (!first)

            out << "]";

    }

private:

    const dynamic_properties* dp;

    const std::string* node_id;

};

template < typename Graph > class dynamic_graph_properties_writer

{

public:

    dynamic_graph_properties_writer(

        const dynamic_properties& dp, const Graph& g)

    : g(&g), dp(&dp)

    {

    }

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

    {

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

             ++i)

        {

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

            {

                // const_cast here is to match interface used in read_graphviz

                out << i->first << "="

                    << escape_dot_string(

                           i->second->get_string(const_cast< Graph* >(g)))

                    << ";\n";

            }

        }

    }

private:

    const Graph* g;

    const dynamic_properties* dp;

};

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_dp(std::ostream& out, const Graph& g,

    const dynamic_properties& dp,

    const std::string& node_id

    = "node_id" BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))

{

    typedef typename graph_traits< Graph >::vertex_descriptor Vertex;

    write_graphviz_dp(out, g, dp, node_id,

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

}

template < typename Graph, typename VertexID >

void write_graphviz_dp(std::ostream& out, const Graph& g,

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

    VertexID id BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))

{

    write_graphviz(out, g,

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

        /*edge_writer=*/dynamic_properties_writer(dp),

        /*graph_writer=*/dynamic_graph_properties_writer< Graph >(dp, g), id);

}

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

// Graph reader exceptions

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

struct BOOST_SYMBOL_VISIBLE bad_graphviz_syntax : public graph_exception

{

    std::string errmsg;

    bad_graphviz_syntax(const std::string& errmsg) : errmsg(errmsg) {}

    const char* what() const throw() BOOST_OVERRIDE { return errmsg.c_str(); }

    ~bad_graphviz_syntax() throw() BOOST_OVERRIDE {}

};

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;

            virtual void // RG: need new second parameter to support BGL

                         // subgraphs

            set_graph_property(const id_t& key, const id_t& value)

                = 0;

            virtual void finish_building_graph() = 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() BOOST_OVERRIDE {}

            bool is_directed() const BOOST_OVERRIDE

            {

                return boost::is_convertible<

                    typename boost::graph_traits<

                        MutableGraph >::directed_category,

                    boost::directed_tag >::value;

            }

            void do_add_vertex(const node_t& node) BOOST_OVERRIDE

            {

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

            {

                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

                    boost::throw_exception(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) BOOST_OVERRIDE

            {

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

            }

            void set_edge_property(const id_t& key, const edge_t& edge,

                const id_t& value) BOOST_OVERRIDE

            {

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

            }

            void set_graph_property(const id_t& key,

                const id_t& value) BOOST_OVERRIDE

            {

                /* RG: pointer to graph prevents copying */

                put(key, dp_, &graph_, value);

            }

            void finish_building_graph() BOOST_OVERRIDE {}

        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;

        };

        template < typename Directed, typename VertexProperty,

            typename EdgeProperty, typename GraphProperty, typename Vertex,

            typename EdgeIndex >

        class mutate_graph_impl< compressed_sparse_row_graph< Directed,

            VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex > >

        : public mutate_graph

        {

            typedef compressed_sparse_row_graph< Directed, VertexProperty,

                EdgeProperty, GraphProperty, Vertex, EdgeIndex >

                CSRGraph;

            typedef typename graph_traits< CSRGraph >::vertices_size_type

                bgl_vertex_t;

            typedef

                typename graph_traits< CSRGraph >::edges_size_type bgl_edge_t;

            typedef typename graph_traits< CSRGraph >::edge_descriptor

                edge_descriptor;

        public:

            mutate_graph_impl(CSRGraph& graph, dynamic_properties& dp,

                std::string node_id_prop)

            : graph_(graph)

            , dp_(dp)

            , vertex_count(0)

            , node_id_prop_(node_id_prop)

            {

            }

            ~mutate_graph_impl() BOOST_OVERRIDE {}

            void finish_building_graph() BOOST_OVERRIDE

            {

                typedef compressed_sparse_row_graph< directedS, no_property,

                    bgl_edge_t, GraphProperty, Vertex, EdgeIndex >

                    TempCSRGraph;

                TempCSRGraph temp(edges_are_unsorted_multi_pass,

                    edges_to_add.begin(), edges_to_add.end(),

                    counting_iterator< bgl_edge_t >(0), vertex_count);

                set_property(temp, graph_all, get_property(graph_, graph_all));

                graph_.assign(temp); // Copies structure, not properties

                std::vector< edge_descriptor > edge_permutation_from_sorting(

                    num_edges(temp));

                BGL_FORALL_EDGES_T(e, temp, TempCSRGraph)

                {

                    edge_permutation_from_sorting[temp[e]] = e;

                }

                typedef boost::tuple< id_t, bgl_vertex_t, id_t > v_prop;

                BOOST_FOREACH (const v_prop& t, vertex_props)

                {

                    put(boost::get< 0 >(t), dp_, boost::get< 1 >(t),

                        boost::get< 2 >(t));

                }

                typedef boost::tuple< id_t, bgl_edge_t, id_t > e_prop;

                BOOST_FOREACH (const e_prop& t, edge_props)

                {

                    put(boost::get< 0 >(t), dp_,

                        edge_permutation_from_sorting[boost::get< 1 >(t)],

                        boost::get< 2 >(t));

                }

            }

            bool is_directed() const BOOST_OVERRIDE

            {

                return boost::is_convertible<

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

                    boost::directed_tag >::value;

            }

            void do_add_vertex(const node_t& node) BOOST_OVERRIDE

            {

                // Add the node to the graph.

                bgl_vertex_t v = vertex_count++;

                // 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.

                vertex_props.push_back(

                    boost::make_tuple(node_id_prop_, v, node));

            }

            void do_add_edge(const edge_t& edge, const node_t& source,

                const node_t& target) BOOST_OVERRIDE

            {

                bgl_edge_t result = edges_to_add.size();

                edges_to_add.push_back(

                    std::make_pair(bgl_nodes[source], bgl_nodes[target]));

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

            }

            void set_node_property(const id_t& key, const node_t& node,

                const id_t& value) BOOST_OVERRIDE

            {

                vertex_props.push_back(

                    boost::make_tuple(key, bgl_nodes[node], value));

            }

            void set_edge_property(const id_t& key, const edge_t& edge,

                const id_t& value) BOOST_OVERRIDE

            {

                edge_props.push_back(

                    boost::make_tuple(key, bgl_edges[edge], value));

            }

            void set_graph_property(const id_t& key,

                const id_t& value) BOOST_OVERRIDE

            {

                /* RG: pointer to graph prevents copying */

                put(key, dp_, &graph_, value);

            }

        protected:

            CSRGraph& graph_;

            dynamic_properties& dp_;

            bgl_vertex_t vertex_count;

            std::string node_id_prop_;

            std::vector< boost::tuple< id_t, bgl_vertex_t, id_t > >

                vertex_props;

            std::vector< boost::tuple< id_t, bgl_edge_t, id_t > > edge_props;

            std::vector< std::pair< bgl_vertex_t, bgl_vertex_t > > edges_to_add;

            std::map< node_t, bgl_vertex_t > bgl_nodes;

            std::map< edge_t, bgl_edge_t > bgl_edges;

        };

    }

}

} // end namespace boost::detail::graph

#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER

#ifndef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS

#define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS

#endif

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

#else // New default parser

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

#endif // BOOST_GRAPH_USE_SPIRIT_PARSER

namespace boost

{

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

template < typename MutableGraph >

bool read_graphviz(const std::string& data, MutableGraph& graph,

    dynamic_properties& dp, std::string const& node_id = "node_id")

{

#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER

    return read_graphviz_spirit(data.begin(), data.end(), graph, dp, node_id);

#else // Non-Spirit parser

    return read_graphviz_new(data, graph, dp, node_id);

#endif

}

// Parse the passed iterator range as a GraphViz dot file.

template < typename InputIterator, typename MutableGraph >

bool read_graphviz(InputIterator user_first, InputIterator user_last,

    MutableGraph& graph, dynamic_properties& dp,

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

{

#ifdef BOOST_GRAPH_USE_SPIRIT_PARSER

    typedef InputIterator is_t;

    typedef boost::spirit::classic::multi_pass< is_t > iterator_t;

    iterator_t first(boost::spirit::classic::make_multi_pass(user_first));

    iterator_t last(boost::spirit::classic::make_multi_pass(user_last));

    return read_graphviz_spirit(first, last, graph, dp, node_id);

#else // Non-Spirit parser

    return read_graphviz_new(

        std::string(user_first, user_last), graph, dp, node_id);

#endif

}

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

{

    typedef std::istream_iterator< char > is_t;

    in >> std::noskipws;

    return read_graphviz(is_t(in), is_t(), graph, dp, node_id);

}

} // namespace boost

#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/graphviz.hpp>)

#endif // BOOST_GRAPHVIZ_HPP