Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 09:42:59 

0001 //=======================================================================
0002 // Copyright 2001 University of Notre Dame.
0003 // Copyright 2003 Jeremy Siek
0004 // Authors: Lie-Quan Lee, Jeremy Siek, and Douglas Gregor
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 #ifndef BOOST_GRAPHVIZ_HPP
0011 #define BOOST_GRAPHVIZ_HPP
0012 
0013 #include <boost/config.hpp>
0014 #include <cstdio> // for FILE
0015 #include <fstream>
0016 #include <iostream>
0017 #include <map>
0018 #include <string>
0019 #include <boost/property_map/property_map.hpp>
0020 #include <boost/tuple/tuple.hpp>
0021 #include <boost/graph/graph_traits.hpp>
0022 #include <boost/graph/properties.hpp>
0023 #include <boost/graph/subgraph.hpp>
0024 #include <boost/graph/adjacency_list.hpp>
0025 #include <boost/property_map/dynamic_property_map.hpp>
0026 #include <boost/graph/overloading.hpp>
0027 #include <boost/graph/dll_import_export.hpp>
0028 #include <boost/graph/compressed_sparse_row_graph.hpp>
0029 #include <boost/graph/iteration_macros.hpp>
0030 #include <boost/graph/detail/mpi_include.hpp>
0031 #include <boost/spirit/include/classic_multi_pass.hpp>
0032 #include <boost/lexical_cast.hpp>
0033 #include <boost/static_assert.hpp>
0034 #include <boost/algorithm/string/replace.hpp>
0035 #include <boost/xpressive/xpressive_static.hpp>
0036 #include <boost/foreach.hpp>
0037 
0038 namespace boost
0039 {
0040 
0041 template < typename directed_category > struct graphviz_io_traits
0042 {
0043     static std::string name() { return "digraph"; }
0044     static std::string delimiter() { return "->"; }
0045 };
0046 
0047 template <> struct graphviz_io_traits< undirected_tag >
0048 {
0049     static std::string name() { return "graph"; }
0050     static std::string delimiter() { return "--"; }
0051 };
0052 
0053 struct default_writer
0054 {
0055     void operator()(std::ostream&) const {}
0056     template < class VorE > void operator()(std::ostream&, const VorE&) const {}
0057 };
0058 
0059 template < typename T > inline std::string escape_dot_string(const T& obj)
0060 {
0061     using namespace boost::xpressive;
0062     static sregex valid_unquoted_id = (((alpha | '_') >> *_w)
0063         | (!as_xpr('-') >> (('.' >> *_d) | (+_d >> !('.' >> *_d)))));
0064     std::string s(boost::lexical_cast< std::string >(obj));
0065     if (regex_match(s, valid_unquoted_id))
0066     {
0067         return s;
0068     }
0069     else
0070     {
0071         boost::algorithm::replace_all(s, "\"", "\\\"");
0072         return "\"" + s + "\"";
0073     }
0074 }
0075 
0076 template < class Name > class label_writer
0077 {
0078 public:
0079     label_writer(Name _name) : name(_name) {}
0080     template < class VertexOrEdge >
0081     void operator()(std::ostream& out, const VertexOrEdge& v) const
0082     {
0083         out << "[label=" << escape_dot_string(get(name, v)) << "]";
0084     }
0085 
0086 private:
0087     Name name;
0088 };
0089 template < class Name > inline label_writer< Name > make_label_writer(Name n)
0090 {
0091     return label_writer< Name >(n);
0092 }
0093 
0094 enum edge_attribute_t
0095 {
0096     edge_attribute = 1111
0097 };
0098 enum vertex_attribute_t
0099 {
0100     vertex_attribute = 2222
0101 };
0102 enum graph_graph_attribute_t
0103 {
0104     graph_graph_attribute = 3333
0105 };
0106 enum graph_vertex_attribute_t
0107 {
0108     graph_vertex_attribute = 4444
0109 };
0110 enum graph_edge_attribute_t
0111 {
0112     graph_edge_attribute = 5555
0113 };
0114 
0115 BOOST_INSTALL_PROPERTY(edge, attribute);
0116 BOOST_INSTALL_PROPERTY(vertex, attribute);
0117 BOOST_INSTALL_PROPERTY(graph, graph_attribute);
0118 BOOST_INSTALL_PROPERTY(graph, vertex_attribute);
0119 BOOST_INSTALL_PROPERTY(graph, edge_attribute);
0120 
0121 template < class Attribute >
0122 inline void write_attributes(const Attribute& attr, std::ostream& out)
0123 {
0124     typename Attribute::const_iterator i, iend;
0125     i = attr.begin();
0126     iend = attr.end();
0127 
0128     while (i != iend)
0129     {
0130         out << i->first << "=" << escape_dot_string(i->second);
0131         ++i;
0132         if (i != iend)
0133             out << ", ";
0134     }
0135 }
0136 
0137 template < typename Attributes >
0138 inline void write_all_attributes(
0139     Attributes attributes, const std::string& name, std::ostream& out)
0140 {
0141     typename Attributes::const_iterator i = attributes.begin(),
0142                                         end = attributes.end();
0143     if (i != end)
0144     {
0145         out << name << " [\n";
0146         write_attributes(attributes, out);
0147         out << "];\n";
0148     }
0149 }
0150 
0151 inline void write_all_attributes(
0152     detail::error_property_not_found, const std::string&, std::ostream&)
0153 {
0154     // Do nothing - no attributes exist
0155 }
0156 
0157 template < typename GraphGraphAttributes, typename GraphNodeAttributes,
0158     typename GraphEdgeAttributes >
0159 struct graph_attributes_writer
0160 {
0161     graph_attributes_writer(
0162         GraphGraphAttributes gg, GraphNodeAttributes gn, GraphEdgeAttributes ge)
0163     : g_attributes(gg), n_attributes(gn), e_attributes(ge)
0164     {
0165     }
0166 
0167     void operator()(std::ostream& out) const
0168     {
0169         write_all_attributes(g_attributes, "graph", out);
0170         write_all_attributes(n_attributes, "node", out);
0171         write_all_attributes(e_attributes, "edge", out);
0172     }
0173     GraphGraphAttributes g_attributes;
0174     GraphNodeAttributes n_attributes;
0175     GraphEdgeAttributes e_attributes;
0176 };
0177 
0178 template < typename GAttrMap, typename NAttrMap, typename EAttrMap >
0179 graph_attributes_writer< GAttrMap, NAttrMap, EAttrMap >
0180 make_graph_attributes_writer(
0181     const GAttrMap& g_attr, const NAttrMap& n_attr, const EAttrMap& e_attr)
0182 {
0183     return graph_attributes_writer< GAttrMap, NAttrMap, EAttrMap >(
0184         g_attr, n_attr, e_attr);
0185 }
0186 
0187 template < typename Graph >
0188 graph_attributes_writer<
0189     typename graph_property< Graph, graph_graph_attribute_t >::type,
0190     typename graph_property< Graph, graph_vertex_attribute_t >::type,
0191     typename graph_property< Graph, graph_edge_attribute_t >::type >
0192 make_graph_attributes_writer(const Graph& g)
0193 {
0194     typedef typename graph_property< Graph, graph_graph_attribute_t >::type
0195         GAttrMap;
0196     typedef typename graph_property< Graph, graph_vertex_attribute_t >::type
0197         NAttrMap;
0198     typedef
0199         typename graph_property< Graph, graph_edge_attribute_t >::type EAttrMap;
0200     GAttrMap gam = get_property(g, graph_graph_attribute);
0201     NAttrMap nam = get_property(g, graph_vertex_attribute);
0202     EAttrMap eam = get_property(g, graph_edge_attribute);
0203     graph_attributes_writer< GAttrMap, NAttrMap, EAttrMap > writer(
0204         gam, nam, eam);
0205     return writer;
0206 }
0207 
0208 template < typename AttributeMap > struct attributes_writer
0209 {
0210     attributes_writer(AttributeMap attr) : attributes(attr) {}
0211 
0212     template < class VorE >
0213     void operator()(std::ostream& out, const VorE& e) const
0214     {
0215         this->write_attribute(out, attributes[e]);
0216     }
0217 
0218 private:
0219     template < typename AttributeSequence >
0220     void write_attribute(std::ostream& out, const AttributeSequence& seq) const
0221     {
0222         if (!seq.empty())
0223         {
0224             out << "[";
0225             write_attributes(seq, out);
0226             out << "]";
0227         }
0228     }
0229 
0230     void write_attribute(std::ostream&, detail::error_property_not_found) const
0231     {
0232     }
0233     AttributeMap attributes;
0234 };
0235 
0236 template < typename Graph >
0237 attributes_writer<
0238     typename property_map< Graph, edge_attribute_t >::const_type >
0239 make_edge_attributes_writer(const Graph& g)
0240 {
0241     typedef typename property_map< Graph, edge_attribute_t >::const_type
0242         EdgeAttributeMap;
0243     return attributes_writer< EdgeAttributeMap >(get(edge_attribute, g));
0244 }
0245 
0246 template < typename Graph >
0247 attributes_writer<
0248     typename property_map< Graph, vertex_attribute_t >::const_type >
0249 make_vertex_attributes_writer(const Graph& g)
0250 {
0251     typedef typename property_map< Graph, vertex_attribute_t >::const_type
0252         VertexAttributeMap;
0253     return attributes_writer< VertexAttributeMap >(get(vertex_attribute, g));
0254 }
0255 
0256 template < typename Graph, typename VertexPropertiesWriter,
0257     typename EdgePropertiesWriter, typename GraphPropertiesWriter,
0258     typename VertexID >
0259 inline void write_graphviz(std::ostream& out, const Graph& g,
0260     VertexPropertiesWriter vpw, EdgePropertiesWriter epw,
0261     GraphPropertiesWriter gpw,
0262     VertexID vertex_id BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0263         Graph, vertex_list_graph_tag))
0264 {
0265     BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< Graph >));
0266 
0267     typedef typename graph_traits< Graph >::directed_category cat_type;
0268     typedef graphviz_io_traits< cat_type > Traits;
0269     std::string name = "G";
0270     out << Traits::name() << " " << escape_dot_string(name) << " {"
0271         << std::endl;
0272 
0273     gpw(out); // print graph properties
0274 
0275     typename graph_traits< Graph >::vertex_iterator i, end;
0276 
0277     for (boost::tie(i, end) = vertices(g); i != end; ++i)
0278     {
0279         out << escape_dot_string(get(vertex_id, *i));
0280         vpw(out, *i); // print vertex attributes
0281         out << ";" << std::endl;
0282     }
0283     typename graph_traits< Graph >::edge_iterator ei, edge_end;
0284     for (boost::tie(ei, edge_end) = edges(g); ei != edge_end; ++ei)
0285     {
0286         out << escape_dot_string(get(vertex_id, source(*ei, g)))
0287             << Traits::delimiter()
0288             << escape_dot_string(get(vertex_id, target(*ei, g))) << " ";
0289         epw(out, *ei); // print edge attributes
0290         out << ";" << std::endl;
0291     }
0292     out << "}" << std::endl;
0293 }
0294 
0295 template < typename Graph, typename VertexPropertiesWriter,
0296     typename EdgePropertiesWriter, typename GraphPropertiesWriter >
0297 inline void write_graphviz(std::ostream& out, const Graph& g,
0298     VertexPropertiesWriter vpw, EdgePropertiesWriter epw,
0299     GraphPropertiesWriter gpw BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0300         Graph, vertex_list_graph_tag))
0301 {
0302     write_graphviz(out, g, vpw, epw, gpw, get(vertex_index, g));
0303 }
0304 
0305 template < typename Graph >
0306 inline void write_graphviz(std::ostream& out,
0307     const Graph& g BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0308         Graph, vertex_list_graph_tag))
0309 {
0310     default_writer dw;
0311     default_writer gw;
0312     write_graphviz(out, g, dw, dw, gw);
0313 }
0314 
0315 template < typename Graph, typename VertexWriter >
0316 inline void write_graphviz(std::ostream& out, const Graph& g,
0317     VertexWriter vw BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0318         Graph, vertex_list_graph_tag))
0319 {
0320     default_writer dw;
0321     default_writer gw;
0322     write_graphviz(out, g, vw, dw, gw);
0323 }
0324 
0325 template < typename Graph, typename VertexWriter, typename EdgeWriter >
0326 inline void write_graphviz(std::ostream& out, const Graph& g, VertexWriter vw,
0327     EdgeWriter ew BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0328         Graph, vertex_list_graph_tag))
0329 {
0330     default_writer gw;
0331     write_graphviz(out, g, vw, ew, gw);
0332 }
0333 
0334 namespace detail
0335 {
0336 
0337     template < class Graph_, class RandomAccessIterator, class VertexID >
0338     void write_graphviz_subgraph(std::ostream& out, const subgraph< Graph_ >& g,
0339         RandomAccessIterator vertex_marker, RandomAccessIterator edge_marker,
0340         VertexID vertex_id)
0341     {
0342         typedef subgraph< Graph_ > Graph;
0343         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0344         typedef typename graph_traits< Graph >::directed_category cat_type;
0345         typedef graphviz_io_traits< cat_type > Traits;
0346 
0347         typedef typename graph_property< Graph, graph_name_t >::type NameType;
0348         const NameType& g_name = get_property(g, graph_name);
0349 
0350         if (g.is_root())
0351             out << Traits::name();
0352         else
0353             out << "subgraph";
0354 
0355         out << " " << escape_dot_string(g_name) << " {" << std::endl;
0356 
0357         typename Graph::const_children_iterator i_child, j_child;
0358 
0359         // print graph/node/edge attributes
0360         make_graph_attributes_writer(g)(out);
0361 
0362         // print subgraph
0363         for (boost::tie(i_child, j_child) = g.children(); i_child != j_child;
0364              ++i_child)
0365             write_graphviz_subgraph(
0366                 out, *i_child, vertex_marker, edge_marker, vertex_id);
0367 
0368         // Print out vertices and edges not in the subgraphs.
0369 
0370         typename graph_traits< Graph >::vertex_iterator i, end;
0371         typename graph_traits< Graph >::edge_iterator ei, edge_end;
0372 
0373         for (boost::tie(i, end) = vertices(g); i != end; ++i)
0374         {
0375             Vertex v = g.local_to_global(*i);
0376             int pos = get(vertex_id, v);
0377             if (vertex_marker[pos])
0378             {
0379                 vertex_marker[pos] = false;
0380                 out << escape_dot_string(pos);
0381                 make_vertex_attributes_writer(g.root())(out, v);
0382                 out << ";" << std::endl;
0383             }
0384         }
0385 
0386         for (boost::tie(ei, edge_end) = edges(g); ei != edge_end; ++ei)
0387         {
0388             Vertex u = g.local_to_global(source(*ei, g)),
0389                    v = g.local_to_global(target(*ei, g));
0390             int pos = get(get(edge_index, g.root()), g.local_to_global(*ei));
0391             if (edge_marker[pos])
0392             {
0393                 edge_marker[pos] = false;
0394                 out << escape_dot_string(get(vertex_id, u)) << " "
0395                     << Traits::delimiter() << " "
0396                     << escape_dot_string(get(vertex_id, v));
0397                 make_edge_attributes_writer(g)(
0398                     out, *ei); // print edge properties
0399                 out << ";" << std::endl;
0400             }
0401         }
0402         out << "}" << std::endl;
0403     }
0404 } // namespace detail
0405 
0406 // requires graph_name graph property
0407 template < typename Graph >
0408 void write_graphviz(std::ostream& out, const subgraph< Graph >& g)
0409 {
0410     std::vector< bool > edge_marker(num_edges(g), true);
0411     std::vector< bool > vertex_marker(num_vertices(g), true);
0412 
0413     detail::write_graphviz_subgraph(out, g, vertex_marker.begin(),
0414         edge_marker.begin(), get(vertex_index, g));
0415 }
0416 
0417 template < typename Graph >
0418 void write_graphviz(const std::string& filename, const subgraph< Graph >& g)
0419 {
0420     std::ofstream out(filename.c_str());
0421     std::vector< bool > edge_marker(num_edges(g), true);
0422     std::vector< bool > vertex_marker(num_vertices(g), true);
0423 
0424     detail::write_graphviz_subgraph(out, g, vertex_marker.begin(),
0425         edge_marker.begin(), get(vertex_index, g));
0426 }
0427 
0428 template < typename Graph, typename VertexID >
0429 void write_graphviz(
0430     std::ostream& out, const subgraph< Graph >& g, VertexID vertex_id)
0431 {
0432     std::vector< bool > edge_marker(num_edges(g), true);
0433     std::vector< bool > vertex_marker(num_vertices(g), true);
0434 
0435     detail::write_graphviz_subgraph(
0436         out, g, vertex_marker.begin(), edge_marker.begin(), vertex_id);
0437 }
0438 
0439 template < typename Graph, typename VertexID >
0440 void write_graphviz(
0441     const std::string& filename, const subgraph< Graph >& g, VertexID vertex_id)
0442 {
0443     std::ofstream out(filename.c_str());
0444     std::vector< bool > edge_marker(num_edges(g), true);
0445     std::vector< bool > vertex_marker(num_vertices(g), true);
0446 
0447     detail::write_graphviz_subgraph(
0448         out, g, vertex_marker.begin(), edge_marker.begin(), vertex_id);
0449 }
0450 
0451 #if 0
0452   // This interface has not worked for a long time
0453   typedef std::map<std::string, std::string> GraphvizAttrList;
0454 
0455   typedef property<vertex_attribute_t, GraphvizAttrList>
0456           GraphvizVertexProperty;
0457 
0458   typedef property<edge_attribute_t, GraphvizAttrList,
0459                    property<edge_index_t, int> >
0460           GraphvizEdgeProperty;
0461 
0462   typedef property<graph_graph_attribute_t, GraphvizAttrList,
0463                    property<graph_vertex_attribute_t, GraphvizAttrList,
0464                    property<graph_edge_attribute_t, GraphvizAttrList,
0465                    property<graph_name_t, std::string> > > >
0466           GraphvizGraphProperty;
0467 
0468   typedef subgraph<adjacency_list<vecS,
0469                    vecS, directedS,
0470                    GraphvizVertexProperty,
0471                    GraphvizEdgeProperty,
0472                    GraphvizGraphProperty> >
0473           GraphvizDigraph;
0474 
0475   typedef subgraph<adjacency_list<vecS,
0476                    vecS, undirectedS,
0477                    GraphvizVertexProperty,
0478                    GraphvizEdgeProperty,
0479                    GraphvizGraphProperty> >
0480           GraphvizGraph;
0481 
0482   // These four require linking the BGL-Graphviz library: libbgl-viz.a
0483   // from the /src directory.
0484   // Library has not existed for a while
0485   extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
0486   extern void read_graphviz(FILE* file, GraphvizDigraph& g);
0487 
0488   extern void read_graphviz(const std::string& file, GraphvizGraph& g);
0489   extern void read_graphviz(FILE* file, GraphvizGraph& g);
0490 #endif
0491 
0492 class dynamic_properties_writer
0493 {
0494 public:
0495     dynamic_properties_writer(const dynamic_properties& dp) : dp(&dp) {}
0496 
0497     template < typename Descriptor >
0498     void operator()(std::ostream& out, Descriptor key) const
0499     {
0500         bool first = true;
0501         for (dynamic_properties::const_iterator i = dp->begin(); i != dp->end();
0502              ++i)
0503         {
0504             if (typeid(key) == i->second->key())
0505             {
0506                 if (first)
0507                     out << " [";
0508                 else
0509                     out << ", ";
0510                 first = false;
0511 
0512                 out << i->first << "="
0513                     << escape_dot_string(i->second->get_string(key));
0514             }
0515         }
0516 
0517         if (!first)
0518             out << "]";
0519     }
0520 
0521 private:
0522     const dynamic_properties* dp;
0523 };
0524 
0525 class dynamic_vertex_properties_writer
0526 {
0527 public:
0528     dynamic_vertex_properties_writer(
0529         const dynamic_properties& dp, const std::string& node_id)
0530     : dp(&dp), node_id(&node_id)
0531     {
0532     }
0533 
0534     template < typename Descriptor >
0535     void operator()(std::ostream& out, Descriptor key) const
0536     {
0537         bool first = true;
0538         for (dynamic_properties::const_iterator i = dp->begin(); i != dp->end();
0539              ++i)
0540         {
0541             if (typeid(key) == i->second->key() && i->first != *node_id)
0542             {
0543                 if (first)
0544                     out << " [";
0545                 else
0546                     out << ", ";
0547                 first = false;
0548 
0549                 out << i->first << "="
0550                     << escape_dot_string(i->second->get_string(key));
0551             }
0552         }
0553 
0554         if (!first)
0555             out << "]";
0556     }
0557 
0558 private:
0559     const dynamic_properties* dp;
0560     const std::string* node_id;
0561 };
0562 
0563 template < typename Graph > class dynamic_graph_properties_writer
0564 {
0565 public:
0566     dynamic_graph_properties_writer(
0567         const dynamic_properties& dp, const Graph& g)
0568     : g(&g), dp(&dp)
0569     {
0570     }
0571 
0572     void operator()(std::ostream& out) const
0573     {
0574         for (dynamic_properties::const_iterator i = dp->begin(); i != dp->end();
0575              ++i)
0576         {
0577             if (typeid(Graph*) == i->second->key())
0578             {
0579                 // const_cast here is to match interface used in read_graphviz
0580                 out << i->first << "="
0581                     << escape_dot_string(
0582                            i->second->get_string(const_cast< Graph* >(g)))
0583                     << ";\n";
0584             }
0585         }
0586     }
0587 
0588 private:
0589     const Graph* g;
0590     const dynamic_properties* dp;
0591 };
0592 
0593 namespace graph
0594 {
0595     namespace detail
0596     {
0597 
0598         template < typename Vertex > struct node_id_property_map
0599         {
0600             typedef std::string value_type;
0601             typedef value_type reference;
0602             typedef Vertex key_type;
0603             typedef readable_property_map_tag category;
0604 
0605             node_id_property_map() {}
0606 
0607             node_id_property_map(
0608                 const dynamic_properties& dp, const std::string& node_id)
0609             : dp(&dp), node_id(&node_id)
0610             {
0611             }
0612 
0613             const dynamic_properties* dp;
0614             const std::string* node_id;
0615         };
0616 
0617         template < typename Vertex >
0618         inline std::string get(node_id_property_map< Vertex > pm,
0619             typename node_id_property_map< Vertex >::key_type v)
0620         {
0621             return get(*pm.node_id, *pm.dp, v);
0622         }
0623 
0624     }
0625 } // end namespace graph::detail
0626 
0627 template < typename Graph >
0628 inline void write_graphviz_dp(std::ostream& out, const Graph& g,
0629     const dynamic_properties& dp,
0630     const std::string& node_id
0631     = "node_id" BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
0632 {
0633     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0634     write_graphviz_dp(out, g, dp, node_id,
0635         graph::detail::node_id_property_map< Vertex >(dp, node_id));
0636 }
0637 
0638 template < typename Graph, typename VertexID >
0639 void write_graphviz_dp(std::ostream& out, const Graph& g,
0640     const dynamic_properties& dp, const std::string& node_id,
0641     VertexID id BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
0642 {
0643     write_graphviz(out, g,
0644         /*vertex_writer=*/dynamic_vertex_properties_writer(dp, node_id),
0645         /*edge_writer=*/dynamic_properties_writer(dp),
0646         /*graph_writer=*/dynamic_graph_properties_writer< Graph >(dp, g), id);
0647 }
0648 
0649 /////////////////////////////////////////////////////////////////////////////
0650 // Graph reader exceptions
0651 /////////////////////////////////////////////////////////////////////////////
0652 struct BOOST_SYMBOL_VISIBLE graph_exception : public std::exception
0653 {
0654     ~graph_exception() throw() BOOST_OVERRIDE {}
0655     const char* what() const throw() BOOST_OVERRIDE = 0;
0656 };
0657 
0658 struct BOOST_SYMBOL_VISIBLE bad_parallel_edge : public graph_exception
0659 {
0660     std::string from;
0661     std::string to;
0662     mutable std::string statement;
0663     bad_parallel_edge(const std::string& i, const std::string& j)
0664     : from(i), to(j)
0665     {
0666     }
0667 
0668     ~bad_parallel_edge() throw() BOOST_OVERRIDE {}
0669     const char* what() const throw() BOOST_OVERRIDE
0670     {
0671         if (statement.empty())
0672             statement = std::string("Failed to add parallel edge: (") + from
0673                 + "," + to + ")\n";
0674 
0675         return statement.c_str();
0676     }
0677 };
0678 
0679 struct BOOST_SYMBOL_VISIBLE directed_graph_error : public graph_exception
0680 {
0681     ~directed_graph_error() throw() BOOST_OVERRIDE {}
0682     const char* what() const throw() BOOST_OVERRIDE
0683     {
0684         return "read_graphviz: "
0685                "Tried to read a directed graph into an undirected graph.";
0686     }
0687 };
0688 
0689 struct BOOST_SYMBOL_VISIBLE undirected_graph_error : public graph_exception
0690 {
0691     ~undirected_graph_error() throw() BOOST_OVERRIDE {}
0692     const char* what() const throw() BOOST_OVERRIDE
0693     {
0694         return "read_graphviz: "
0695                "Tried to read an undirected graph into a directed graph.";
0696     }
0697 };
0698 
0699 struct BOOST_SYMBOL_VISIBLE bad_graphviz_syntax : public graph_exception
0700 {
0701     std::string errmsg;
0702     bad_graphviz_syntax(const std::string& errmsg) : errmsg(errmsg) {}
0703     const char* what() const throw() BOOST_OVERRIDE { return errmsg.c_str(); }
0704     ~bad_graphviz_syntax() throw() BOOST_OVERRIDE {}
0705 };
0706 
0707 namespace detail
0708 {
0709     namespace graph
0710     {
0711 
0712         typedef std::string id_t;
0713         typedef id_t node_t;
0714 
0715         // edges are not uniquely determined by adjacent nodes
0716         class edge_t
0717         {
0718             int idx_;
0719             explicit edge_t(int i) : idx_(i) {}
0720 
0721         public:
0722             static edge_t new_edge()
0723             {
0724                 static int idx = 0;
0725                 return edge_t(idx++);
0726             }
0727 
0728             bool operator==(const edge_t& rhs) const
0729             {
0730                 return idx_ == rhs.idx_;
0731             }
0732             bool operator<(const edge_t& rhs) const { return idx_ < rhs.idx_; }
0733         };
0734 
0735         class mutate_graph
0736         {
0737         public:
0738             virtual ~mutate_graph() {}
0739             virtual bool is_directed() const = 0;
0740             virtual void do_add_vertex(const node_t& node) = 0;
0741 
0742             virtual void do_add_edge(
0743                 const edge_t& edge, const node_t& source, const node_t& target)
0744                 = 0;
0745 
0746             virtual void set_node_property(
0747                 const id_t& key, const node_t& node, const id_t& value)
0748                 = 0;
0749 
0750             virtual void set_edge_property(
0751                 const id_t& key, const edge_t& edge, const id_t& value)
0752                 = 0;
0753 
0754             virtual void // RG: need new second parameter to support BGL
0755                          // subgraphs
0756             set_graph_property(const id_t& key, const id_t& value)
0757                 = 0;
0758 
0759             virtual void finish_building_graph() = 0;
0760         };
0761 
0762         template < typename MutableGraph >
0763         class mutate_graph_impl : public mutate_graph
0764         {
0765             typedef typename graph_traits< MutableGraph >::vertex_descriptor
0766                 bgl_vertex_t;
0767             typedef typename graph_traits< MutableGraph >::edge_descriptor
0768                 bgl_edge_t;
0769 
0770         public:
0771             mutate_graph_impl(MutableGraph& graph, dynamic_properties& dp,
0772                 std::string node_id_prop)
0773             : graph_(graph), dp_(dp), node_id_prop_(node_id_prop)
0774             {
0775             }
0776 
0777             ~mutate_graph_impl() BOOST_OVERRIDE {}
0778 
0779             bool is_directed() const BOOST_OVERRIDE
0780             {
0781                 return boost::is_convertible<
0782                     typename boost::graph_traits<
0783                         MutableGraph >::directed_category,
0784                     boost::directed_tag >::value;
0785             }
0786 
0787             void do_add_vertex(const node_t& node) BOOST_OVERRIDE
0788             {
0789                 // Add the node to the graph.
0790                 bgl_vertex_t v = add_vertex(graph_);
0791 
0792                 // Set up a mapping from name to BGL vertex.
0793                 bgl_nodes.insert(std::make_pair(node, v));
0794 
0795                 // node_id_prop_ allows the caller to see the real id names for
0796                 // nodes.
0797                 put(node_id_prop_, dp_, v, node);
0798             }
0799 
0800             void do_add_edge(const edge_t& edge, const node_t& source,
0801                 const node_t& target) BOOST_OVERRIDE
0802             {
0803                 std::pair< bgl_edge_t, bool > result
0804                     = add_edge(bgl_nodes[source], bgl_nodes[target], graph_);
0805 
0806                 if (!result.second)
0807                 {
0808                     // In the case of no parallel edges allowed
0809                     boost::throw_exception(bad_parallel_edge(source, target));
0810                 }
0811                 else
0812                 {
0813                     bgl_edges.insert(std::make_pair(edge, result.first));
0814                 }
0815             }
0816 
0817             void set_node_property(const id_t& key, const node_t& node,
0818                 const id_t& value) BOOST_OVERRIDE
0819             {
0820                 put(key, dp_, bgl_nodes[node], value);
0821             }
0822 
0823             void set_edge_property(const id_t& key, const edge_t& edge,
0824                 const id_t& value) BOOST_OVERRIDE
0825             {
0826                 put(key, dp_, bgl_edges[edge], value);
0827             }
0828 
0829             void set_graph_property(const id_t& key,
0830                 const id_t& value) BOOST_OVERRIDE
0831             {
0832                 /* RG: pointer to graph prevents copying */
0833                 put(key, dp_, &graph_, value);
0834             }
0835 
0836             void finish_building_graph() BOOST_OVERRIDE {}
0837 
0838         protected:
0839             MutableGraph& graph_;
0840             dynamic_properties& dp_;
0841             std::string node_id_prop_;
0842             std::map< node_t, bgl_vertex_t > bgl_nodes;
0843             std::map< edge_t, bgl_edge_t > bgl_edges;
0844         };
0845 
0846         template < typename Directed, typename VertexProperty,
0847             typename EdgeProperty, typename GraphProperty, typename Vertex,
0848             typename EdgeIndex >
0849         class mutate_graph_impl< compressed_sparse_row_graph< Directed,
0850             VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex > >
0851         : public mutate_graph
0852         {
0853             typedef compressed_sparse_row_graph< Directed, VertexProperty,
0854                 EdgeProperty, GraphProperty, Vertex, EdgeIndex >
0855                 CSRGraph;
0856             typedef typename graph_traits< CSRGraph >::vertices_size_type
0857                 bgl_vertex_t;
0858             typedef
0859                 typename graph_traits< CSRGraph >::edges_size_type bgl_edge_t;
0860             typedef typename graph_traits< CSRGraph >::edge_descriptor
0861                 edge_descriptor;
0862 
0863         public:
0864             mutate_graph_impl(CSRGraph& graph, dynamic_properties& dp,
0865                 std::string node_id_prop)
0866             : graph_(graph)
0867             , dp_(dp)
0868             , vertex_count(0)
0869             , node_id_prop_(node_id_prop)
0870             {
0871             }
0872 
0873             ~mutate_graph_impl() BOOST_OVERRIDE {}
0874 
0875             void finish_building_graph() BOOST_OVERRIDE
0876             {
0877                 typedef compressed_sparse_row_graph< directedS, no_property,
0878                     bgl_edge_t, GraphProperty, Vertex, EdgeIndex >
0879                     TempCSRGraph;
0880                 TempCSRGraph temp(edges_are_unsorted_multi_pass,
0881                     edges_to_add.begin(), edges_to_add.end(),
0882                     counting_iterator< bgl_edge_t >(0), vertex_count);
0883                 set_property(temp, graph_all, get_property(graph_, graph_all));
0884                 graph_.assign(temp); // Copies structure, not properties
0885                 std::vector< edge_descriptor > edge_permutation_from_sorting(
0886                     num_edges(temp));
0887                 BGL_FORALL_EDGES_T(e, temp, TempCSRGraph)
0888                 {
0889                     edge_permutation_from_sorting[temp[e]] = e;
0890                 }
0891                 typedef boost::tuple< id_t, bgl_vertex_t, id_t > v_prop;
0892                 BOOST_FOREACH (const v_prop& t, vertex_props)
0893                 {
0894                     put(boost::get< 0 >(t), dp_, boost::get< 1 >(t),
0895                         boost::get< 2 >(t));
0896                 }
0897                 typedef boost::tuple< id_t, bgl_edge_t, id_t > e_prop;
0898                 BOOST_FOREACH (const e_prop& t, edge_props)
0899                 {
0900                     put(boost::get< 0 >(t), dp_,
0901                         edge_permutation_from_sorting[boost::get< 1 >(t)],
0902                         boost::get< 2 >(t));
0903                 }
0904             }
0905 
0906             bool is_directed() const BOOST_OVERRIDE
0907             {
0908                 return boost::is_convertible<
0909                     typename boost::graph_traits< CSRGraph >::directed_category,
0910                     boost::directed_tag >::value;
0911             }
0912 
0913             void do_add_vertex(const node_t& node) BOOST_OVERRIDE
0914             {
0915                 // Add the node to the graph.
0916                 bgl_vertex_t v = vertex_count++;
0917 
0918                 // Set up a mapping from name to BGL vertex.
0919                 bgl_nodes.insert(std::make_pair(node, v));
0920 
0921                 // node_id_prop_ allows the caller to see the real id names for
0922                 // nodes.
0923                 vertex_props.push_back(
0924                     boost::make_tuple(node_id_prop_, v, node));
0925             }
0926 
0927             void do_add_edge(const edge_t& edge, const node_t& source,
0928                 const node_t& target) BOOST_OVERRIDE
0929             {
0930                 bgl_edge_t result = edges_to_add.size();
0931                 edges_to_add.push_back(
0932                     std::make_pair(bgl_nodes[source], bgl_nodes[target]));
0933                 bgl_edges.insert(std::make_pair(edge, result));
0934             }
0935 
0936             void set_node_property(const id_t& key, const node_t& node,
0937                 const id_t& value) BOOST_OVERRIDE
0938             {
0939                 vertex_props.push_back(
0940                     boost::make_tuple(key, bgl_nodes[node], value));
0941             }
0942 
0943             void set_edge_property(const id_t& key, const edge_t& edge,
0944                 const id_t& value) BOOST_OVERRIDE
0945             {
0946                 edge_props.push_back(
0947                     boost::make_tuple(key, bgl_edges[edge], value));
0948             }
0949 
0950             void set_graph_property(const id_t& key,
0951                 const id_t& value) BOOST_OVERRIDE
0952             {
0953                 /* RG: pointer to graph prevents copying */
0954                 put(key, dp_, &graph_, value);
0955             }
0956 
0957         protected:
0958             CSRGraph& graph_;
0959             dynamic_properties& dp_;
0960             bgl_vertex_t vertex_count;
0961             std::string node_id_prop_;
0962             std::vector< boost::tuple< id_t, bgl_vertex_t, id_t > >
0963                 vertex_props;
0964             std::vector< boost::tuple< id_t, bgl_edge_t, id_t > > edge_props;
0965             std::vector< std::pair< bgl_vertex_t, bgl_vertex_t > > edges_to_add;
0966             std::map< node_t, bgl_vertex_t > bgl_nodes;
0967             std::map< edge_t, bgl_edge_t > bgl_edges;
0968         };
0969 
0970     }
0971 }
0972 } // end namespace boost::detail::graph
0973 
0974 #ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
0975 #ifndef BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
0976 #define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
0977 #endif
0978 #include <boost/graph/detail/read_graphviz_spirit.hpp>
0979 #else // New default parser
0980 #include <boost/graph/detail/read_graphviz_new.hpp>
0981 #endif // BOOST_GRAPH_USE_SPIRIT_PARSER
0982 
0983 namespace boost
0984 {
0985 
0986 // Parse the passed string as a GraphViz dot file.
0987 template < typename MutableGraph >
0988 bool read_graphviz(const std::string& data, MutableGraph& graph,
0989     dynamic_properties& dp, std::string const& node_id = "node_id")
0990 {
0991 #ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
0992     return read_graphviz_spirit(data.begin(), data.end(), graph, dp, node_id);
0993 #else // Non-Spirit parser
0994     return read_graphviz_new(data, graph, dp, node_id);
0995 #endif
0996 }
0997 
0998 // Parse the passed iterator range as a GraphViz dot file.
0999 template < typename InputIterator, typename MutableGraph >
1000 bool read_graphviz(InputIterator user_first, InputIterator user_last,
1001     MutableGraph& graph, dynamic_properties& dp,
1002     std::string const& node_id = "node_id")
1003 {
1004 #ifdef BOOST_GRAPH_USE_SPIRIT_PARSER
1005     typedef InputIterator is_t;
1006     typedef boost::spirit::classic::multi_pass< is_t > iterator_t;
1007 
1008     iterator_t first(boost::spirit::classic::make_multi_pass(user_first));
1009     iterator_t last(boost::spirit::classic::make_multi_pass(user_last));
1010 
1011     return read_graphviz_spirit(first, last, graph, dp, node_id);
1012 #else // Non-Spirit parser
1013     return read_graphviz_new(
1014         std::string(user_first, user_last), graph, dp, node_id);
1015 #endif
1016 }
1017 
1018 // Parse the passed stream as a GraphViz dot file.
1019 template < typename MutableGraph >
1020 bool read_graphviz(std::istream& in, MutableGraph& graph,
1021     dynamic_properties& dp, std::string const& node_id = "node_id")
1022 {
1023     typedef std::istream_iterator< char > is_t;
1024     in >> std::noskipws;
1025     return read_graphviz(is_t(in), is_t(), graph, dp, node_id);
1026 }
1027 
1028 } // namespace boost
1029 
1030 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/graphviz.hpp>)
1031 
1032 #endif // BOOST_GRAPHVIZ_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!