http://www.ousob.com --- Legacy Redefined OuSob - File: /wwwroot/clipx/usr/include/boost/graph/graphviz.hpp

//======================================================================= // 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> 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; }; 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