#include <boost/xpressive/xpressive_static.hpp>
#include <boost/foreach.hpp>
-namespace boost {
+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 "--";
- }
- };
+template < typename directed_category > struct graphviz_io_traits
+{
+ static std::string name() { return "digraph"; }
+ static std::string delimiter() { return "->"; }
+};
- struct default_writer {
- void operator()(std::ostream&) const {
- }
- template <class VorE>
- void operator()(std::ostream&, const VorE&) const {
- }
- };
+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) {
+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 + "\"";
+ 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:
+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)) << "]";
+ template < class VertexOrEdge >
+ void operator()(std::ostream& out, const VertexOrEdge& v) const
+ {
+ out << "[label=" << escape_dot_string(get(name, v)) << "]";
}
- private:
+
+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) {
+};
+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();
+ i = attr.begin();
iend = attr.end();
- while ( i != iend ) {
- out << i->first << "=" << escape_dot_string(i->second);
- ++i;
- if ( i != iend )
- out << ", ";
+ 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)
- {
+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";
+ 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&)
- {
+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) { }
+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);
+ 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;
+};
+
+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);
+ 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 < 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]);
+ 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 << "]";
+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
- {
- }
+ 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;
+};
+
+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;
+ out << Traits::name() << " " << escape_dot_string(name) << " {"
+ << std::endl;
- gpw(out); //print graph properties
+ gpw(out); // print graph properties
- typename graph_traits<Graph>::vertex_iterator i, end;
+ 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;
+ 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;
+ 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))
- {
+}
+
+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))
- {
+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))
- {
+}
+
+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 {
+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)
+ 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);
+ 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;
+ }
+ }
- if ( g.is_root() )
- out << Traits::name() ;
- else
- out << "subgraph";
+ 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
- out << " " << escape_dot_string(g_name) << " {" << std::endl;
+// 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);
- typename Graph::const_children_iterator i_child, j_child;
+ detail::write_graphviz_subgraph(out, g, vertex_marker.begin(),
+ edge_marker.begin(), get(vertex_index, g));
+}
- //print graph/node/edge attributes
- make_graph_attributes_writer(g)(out);
+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);
- //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);
+ detail::write_graphviz_subgraph(out, g, vertex_marker.begin(),
+ edge_marker.begin(), get(vertex_index, g));
+}
- // Print out vertices and edges not in the subgraphs.
+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);
- typename graph_traits<Graph>::vertex_iterator i, end;
- typename graph_traits<Graph>::edge_iterator ei, edge_end;
+ detail::write_graphviz_subgraph(
+ out, g, vertex_marker.begin(), edge_marker.begin(), vertex_id);
+}
- 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)
- {
+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);
+ 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);
- }
+ 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
// 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) { }
+class dynamic_properties_writer
+{
+public:
+ dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) {}
- template<typename Descriptor>
+ 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));
+ 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 << "]";
+ if (!first)
+ out << "]";
}
- private:
+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) { }
+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>
+ 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));
+ 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 << "]";
+ if (!first)
+ out << "]";
}
- private:
+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) { }
+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";
+ 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:
+private:
const Graph* g;
const dynamic_properties* dp;
- };
-
- namespace graph { namespace detail {
+};
- template<typename Vertex>
- struct node_id_property_map
+namespace graph
+{
+ namespace detail
{
- 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;
+
+ 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::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 graph_exception : public std::exception {
- virtual ~graph_exception() throw() {}
- virtual const char* what() const throw() = 0;
+struct BOOST_SYMBOL_VISIBLE graph_exception : public std::exception
+{
+ virtual ~graph_exception() throw() {}
+ virtual const char* what() const throw() = 0;
};
-struct BOOST_SYMBOL_VISIBLE 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 BOOST_SYMBOL_VISIBLE 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)
+ {
+ }
-struct BOOST_SYMBOL_VISIBLE 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.";
- }
-};
+ virtual ~bad_parallel_edge() throw() {}
+ const char* what() const throw()
+ {
+ if (statement.empty())
+ statement = std::string("Failed to add parallel edge: (") + from
+ + "," + to + ")\n";
-struct BOOST_SYMBOL_VISIBLE 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.";
- }
+ return statement.c_str();
+ }
};
-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 () {return errmsg.c_str();}
- ~bad_graphviz_syntax() throw () {};
+struct BOOST_SYMBOL_VISIBLE 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.";
+ }
};
-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_;
- }
+struct BOOST_SYMBOL_VISIBLE 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.";
+ }
};
-class mutate_graph
+struct BOOST_SYMBOL_VISIBLE bad_graphviz_syntax : public graph_exception
{
- 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;
+ std::string errmsg;
+ bad_graphviz_syntax(const std::string& errmsg) : errmsg(errmsg) {}
+ const char* what() const throw() { return errmsg.c_str(); }
+ ~bad_graphviz_syntax() throw() {};
};
-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
- 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)
- {
- 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);
- }
-
- void
- set_graph_property(const id_t& key, const id_t& value)
- {
- /* RG: pointer to graph prevents copying */
- put(key, dp_, &graph_, value);
- }
-
- void finish_building_graph() {}
-
-
- 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;
-};
+namespace detail
+{
+ namespace graph
+ {
-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() {}
-
- void finish_building_graph() {
- 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
- {
- return
- boost::is_convertible<
- typename boost::graph_traits<CSRGraph>::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 = 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)
- {
- 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)
- {
- 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)
- {
- edge_props.push_back(boost::make_tuple(key, bgl_edges[edge], value));
- }
-
- void
- set_graph_property(const id_t& key, const id_t& value)
- {
- /* 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;
-};
+ 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() {}
+
+ 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
+ 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)
+ {
+ 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);
+ }
+
+ void set_graph_property(const id_t& key, const id_t& value)
+ {
+ /* RG: pointer to graph prevents copying */
+ put(key, dp_, &graph_, value);
+ }
+
+ void finish_building_graph() {}
+
+ 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() {}
+
+ void finish_building_graph()
+ {
+ 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
+ {
+ return boost::is_convertible<
+ typename boost::graph_traits< CSRGraph >::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 = 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)
+ {
+ 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)
+ {
+ 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)
+ {
+ edge_props.push_back(
+ boost::make_tuple(key, bgl_edges[edge], value));
+ }
+
+ void set_graph_property(const id_t& key, const id_t& value)
+ {
+ /* 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
+ }
+}
+} // 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>
+#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>
+#include <boost/graph/detail/read_graphviz_new.hpp>
#endif // BOOST_GRAPH_USE_SPIRIT_PARSER
-namespace boost {
+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") {
+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);
+ 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);
+ 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") {
+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;
+ 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));
+ 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);
+ 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);
+ 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>
+template < typename MutableGraph >
bool read_graphviz(std::istream& in, MutableGraph& graph,
- dynamic_properties& dp,
- std::string const& node_id = "node_id")
+ 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);
+ 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>)
+#include BOOST_GRAPH_MPI_INCLUDE(< boost / graph / distributed / graphviz.hpp >)
#endif // BOOST_GRAPHVIZ_HPP
projects / ceph.git / blobdiff