On 10/03/2006 03:28 PM, Doug Gregor wrote:

Uh oh. It looks like we're not handling namespaces correctly at all. Expat does have namespace support, we're just not using it.

Tiago, perhaps you have some interest in adding namespace support to the GraphML parser?

Yes, sure. I'll take a stab at it... BTW, the newest version from the reader can always be obtained from: https://projects.forked.de/graph-tool/browser/trunk/src/graph/graphml.hpp https://projects.forked.de/graph-tool/browser/trunk/src/graph/graphml.cpp (the above version has a GPL header, but I'll take it off when it's to be included in boost) Take care. -- Tiago de Paula Peixoto <tiago@forked.de>

Hi Rui. On 10/03/2006 06:51 PM, Rui Carvalho wrote:

I just had a look at graph-tool and it looks really interesting. You're computing several measures that are standard in Network Science these days and I wonder if these could be integrated in the next BGL distribution -they're very, very useful.

Thanks! graph-tool uses BGL extensively, but it was really not designed as a library. This means that the code would have to be changed somewhat to be included in a library such as boost. Not to mention that a lot of the algorithms included in graph-tool either come already from BGL or are relatively trivial (degree distribution, degree correlation, etc). There may be some code, however, such as arbitrary random graph generation, which could be of a more general interest... If there is any interest from the BGL people in having any part of graph-tool inserted into boost, I'd be happy to make it happen (by making it more BGL-like, properly parameterized, etc.) Take care. -- Tiago de Paula Peixoto <tiago@forked.de>

Rui Carvalho schrieb:

Hi Tiago,

Yes, you're right, some of the algorithms are trivial (but then, isn't BFS trivial?), but I saw that you're planning to include community structure detection in the near future. Although there isn't just one single algorithm for community structure, having an implementation of those in BGL would help others not reinvent the wheel ;)

Detecting community structure? What do you mean by that? Graph clustering?

Rui Carvalho schrieb:

Jens Müller wrote:

...

Detecting community structure? What do you mean by that? Graph clustering?

Hi Jens,

Have a look at: http://arxiv.org/abs/cond-mat/0603718

:-) I've implemented a Newman-style clusterer (in Java).

Rui Carvalho schrieb:

...

...

Have a look at: http://arxiv.org/abs/cond-mat/0603718

:-)

I've implemented a Newman-style clusterer (in Java).

Ah! Wouldn't it be nice to do it with the BGL! ;)

If Universität Karlsruhe pays me for it, sure ;-)

Doug Gregor schrieb:

On Oct 1, 2006, at 10:18 AM, Jens Müller wrote:

...

I tried to read a GraphML file using Douglas' code and the following:

Tiago de Paula Peixoto has made some big improvements to that code. Are you using the newest version?

Probably not - I just found a posting of your's with Google on Gmane and tried it out. I'll take a look at graph-tools, this is very useful, thanks! I'll report if the problems persist there ...

On Fri, 2006-12-22 at 12:59 -0200, Tiago de Paula Peixoto wrote:

On 10/03/2006 03:28 PM, Doug Gregor wrote:

...

Tiago, perhaps you have some interest in adding namespace support to the GraphML parser?

I finally added this. It turned out to be quite simple...

Wonderful, thank you!

The new code is, as always, at:

https://projects.forked.de/graph-tool/browser/trunk/src/graph/graphml.hpp https://projects.forked.de/graph-tool/browser/trunk/src/graph/graphml.cpp

I would really like to get this into Boost CVS for the 1.35.0 release. Have you perchance written up any HTML documentation and/or do you have a self-contained test case? Once we have both of those, we can put your GraphML parser into the Boost tree. Cheers, Doug

On Dec 22, 2006, at 9:59 AM, Tiago de Paula Peixoto wrote:

On 10/03/2006 03:28 PM, Doug Gregor wrote:

...

Tiago, perhaps you have some interest in adding namespace support to the GraphML parser?

I finally added this. It turned out to be quite simple...

Great! I've integrated your latest GraphML parser, including your tests and documentation, into Boost CVS HEAD. I imagine we'll want to monkey around with the build system a little bit until we get it to build everywhere easily. The GraphML reader is now a part of the "boost_graph" library. Thanks again for your contribution, and I apologize for the long delay in integrating this code. Cheers, Doug

On 03/23/2007 09:49 AM, Tiago de Paula Peixoto wrote:

...

Great! I've integrated your latest GraphML parser, including your tests and documentation, into Boost CVS HEAD. I imagine we'll want to monkey around with the build system a little bit until we get it to build everywhere easily. The GraphML reader is now a part of the "boost_graph" library.

Thanks again for your contribution, and I apologize for the long delay in integrating this code.

Only now I've read this. Great! It may be that the documentation needs a little update. I'll take a look at it this weekend and send you any changes which may be needed.

I've made some modifications to the documentation, the tests, and more importantly, the code itself. The newer versions are attached. The new reader has correct and detaild error reporting from expat, and informs the line and column of the file where the error occurred, but besides that it's the same. The new test is still a bit simple, but it is a little more detailed now. I have a couple of questions: 1- How should graph properties be handled? I did include support for it, using dynamic_properties map with a key type equal to the graph type, but I don't know if that's the proper way to do it. 2- Some of the exceptions are shared with the graphviz reader, but those exceptions have the name "graphviz" in their error strings, and thus create confusing messages when used with the graphml reader. Perhaps those strings should be edited in the graphviz code? Thanks, and let me know if there's anything else I can do. -- Tiago de Paula Peixoto <tiago@forked.de> ============================ |(logo)|__ ``write_graphml`` ============================ .. |(logo)| image:: ../../../boost.png :align: middle :alt: Boost __ ../../../index.htm :: template<typename Graph> void write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp, bool ordered_vertices=false); template<typename Graph, typename VertexIndexMap> void write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index, const dynamic_properties& dp, bool ordered_vertices=false); This is to write a BGL graph object into an output stream in the graphml_ format. Both overloads of ``write_graphml`` will emit all of the properties stored in the dynamic_properties_ object, thereby retaining the properties that have been read in through the dual function read_graphml_. The second overload must be used when the graph doesn't have an internal vertex index map, which must then be supplied with the appropriate parameter. .. contents:: Where Defined ------------- ``<boost/graph/graphml.hpp>`` Parameters ---------- OUT: ``std::ostream& out`` A standard ``std::ostream`` object. IN: ``VertexListGraph& g`` A directed or undirected graph. The graph's type must be a model of VertexListGraph_. If the graph doesn't have an internal ``vertex_index`` property map, one must be supplied with the vertex_index parameter. IN: ``VertexIndexMap vertex_index``> A vertex property map containing the indexes in the range [0,num_vertices(g)]. IN: ``dynamic_properties& dp`` Contains all of the vertex, edge and graph properties that should be emitted by the graphml writer. IN: ``bool ordered_vertices`` This tells whether or not the order of the vertices from vertices(g) matches the order of the indexes. If ``true``, the ``parse.nodeids`` graph attribute will be set to ``canonical``. Otherwise it will be set to ``free``. Example ------- This example demonstrates using BGL-graphml interface to write a BGL graph into a graphml format file. :: enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp, foo_o, bar_cpp, bar_o, libfoobar_a, zig_cpp, zig_o, zag_cpp, zag_o, libzigzag_a, killerapp, N }; const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp", "foo.o", "bar.cpp", "bar.o", "libfoobar.a", "zig.cpp", "zig.o", "zag.cpp", "zag.o", "libzigzag.a", "killerapp" }; int main(int,char*[]) { typedef pair<int,int> Edge; Edge used_by[] = { Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h), Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp), Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp), Edge(zow_h, foo_cpp), Edge(foo_cpp, foo_o), Edge(foo_o, libfoobar_a), Edge(bar_cpp, bar_o), Edge(bar_o, libfoobar_a), Edge(libfoobar_a, libzigzag_a), Edge(zig_cpp, zig_o), Edge(zig_o, libzigzag_a), Edge(zag_cpp, zag_o), Edge(zag_o, libzigzag_a), Edge(libzigzag_a, killerapp) }; const int nedges = sizeof(used_by)/sizeof(Edge); typedef adjacency_list< vecS, vecS, directedS, property< vertex_color_t, string >, property< edge_weight_t, int > > Graph; Graph g(used_by, used_by + nedges, N); graph_traits<Graph>::vertex_iterator v, v_end; for (tie(v,v_end) = vertices(g); v != v_end; ++v) put(vertex_color_t(), g, *v, name[*v]); graph_traits<Graph>::edge_iterator e, e_end; for (tie(e,e_end) = edges(g); e != e_end; ++e) put(edge_weight_t(), g, *e, 3); dynamic_properties dp; dp.property("name", get(vertex_color_t(), g)); dp.property("weight", get(edge_weight_t(), g)); write_graphml(std::cout, g, dp, true); } The output will be: :: <?xml version="1.0" encoding="UTF-8"?> <graphml xmlns="http://graphml.graphdrawing.org/xmlns/graphml" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/graphml http://graphml.graphdrawing.org/xmlns/graphml/graphml-attributes-1.0rc.xsd"> <key id="key0" for="node" attr.name="name" attr.type="string" /> <key id="key1" for="edge" attr.name="weight" attr.type="int" /> <graph id="G" edgedefault="directed" parse.nodeids="canonical" parse.edgeids="canonical" parse.order="nodesfirst"> <node id="n0"> <data key="key0">dax.h</data> </node> <node id="n1"> <data key="key0">yow.h</data> </node> <node id="n2"> <data key="key0">boz.h</data> </node> <node id="n3"> <data key="key0">zow.h</data> </node> <node id="n4"> <data key="key0">foo.cpp</data> </node> <node id="n5"> <data key="key0">foo.o</data> </node> <node id="n6"> <data key="key0">bar.cpp</data> </node> <node id="n7"> <data key="key0">bar.o</data> </node> <node id="n8"> <data key="key0">libfoobar.a</data> </node> <node id="n9"> <data key="key0">zig.cpp</data> </node> <node id="n10"> <data key="key0">zig.o</data> </node> <node id="n11"> <data key="key0">zag.cpp</data> </node> <node id="n12"> <data key="key0">zag.o</data> </node> <node id="n13"> <data key="key0">libzigzag.a</data> </node> <node id="n14"> <data key="key0">killerapp</data> </node> <edge id="e0" source="n0" target="n4"> <data key="key1">3</data> </edge> <edge id="e1" source="n0" target="n6"> <data key="key1">3</data> </edge> <edge id="e2" source="n0" target="n1"> <data key="key1">3</data> </edge> <edge id="e3" source="n1" target="n6"> <data key="key1">3</data> </edge> <edge id="e4" source="n1" target="n11"> <data key="key1">3</data> </edge> <edge id="e5" source="n2" target="n6"> <data key="key1">3</data> </edge> <edge id="e6" source="n2" target="n9"> <data key="key1">3</data> </edge> <edge id="e7" source="n2" target="n11"> <data key="key1">3</data> </edge> <edge id="e8" source="n3" target="n4"> <data key="key1">3</data> </edge> <edge id="e9" source="n4" target="n5"> <data key="key1">3</data> </edge> <edge id="e10" source="n5" target="n8"> <data key="key1">3</data> </edge> <edge id="e11" source="n6" target="n7"> <data key="key1">3</data> </edge> <edge id="e12" source="n7" target="n8"> <data key="key1">3</data> </edge> <edge id="e13" source="n8" target="n13"> <data key="key1">3</data> </edge> <edge id="e14" source="n9" target="n10"> <data key="key1">3</data> </edge> <edge id="e15" source="n10" target="n13"> <data key="key1">3</data> </edge> <edge id="e16" source="n11" target="n12"> <data key="key1">3</data> </edge> <edge id="e17" source="n12" target="n13"> <data key="key1">3</data> </edge> <edge id="e18" source="n13" target="n14"> <data key="key1">3</data> </edge> </graph> </graphml> See Also -------- _read_graphml Notes ----- - Note that you can use graphml file write facilities without the library ``libbglgraphml.a``. .. _graphml: http://graphml.graphdrawing.org/ .. _dynamic_properties: ../../property_map/doc/dynamic_property_map.html .. _read_graphml: read_graphml.html .. _VertexListGraph: VertexListGraph.html ============================ |(logo)|__ ``read_graphml`` ============================ .. |(logo)| image:: ../../../boost.png :align: middle :alt: Boost __ ../../../index.htm :: void read_graphml(std::istream& in, MutableGraph& graph, dynamic_properties& dp); The ``read_graphml`` function interprets a graph described using the graphml_ format and builds a BGL graph that captures that description. Using this function, you can initialize a graph using data stored as text. The graphml format can specify both directed and undirected graphs, and ``read_graphml`` differentiates between the two. One must pass ``read_graphml`` an undirected graph when reading an undirected graph; the same is true for directed graphs. Furthermore, ``read_graphml`` will throw an exception if it encounters parallel edges and cannot add them to the graph. To handle attributes expressed in the graphml format, ``read_graphml`` takes a dynamic_properties_ object and operates on its collection of property maps. The reader passes all the properties encountered to this object, using the graphml attribute names as the property names, and with the appropriate C++ value type based on the graphml attribute type definition. Graph properties are also set with the same dynamic_properties object, where the key type is the type of the graph itself. Requirements: - The type of the graph must model the `Mutable Graph`_ concept. - The type of the iterator must model the `Multi-Pass Iterator`_ concept. - The property map value types must be default-constructible. .. contents:: Where Defined ------------- ``<boost/graph/graphml.hpp>`` 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; bad_parallel_edge(const std::string&, const std::string&); virtual ~bad_parallel_edge() throw(); const char* what() const throw(); }; struct directed_graph_error : public graph_exception { virtual ~directed_graph_error() throw(); virtual const char* what() const throw(); }; struct undirected_graph_error : public graph_exception { virtual ~undirected_graph_error() throw(); virtual const char* what() const throw(); }; struct parse_error : public graph_exception { parse_error(const std::string&); virtual ~parse_error() throw() {} virtual const char* what() const throw(); std::string statement; std::string error; }; Under certain circumstances, ``read_graphml`` will throw one of the above exceptions. The three concrete exceptions can all be caught using the general ``graph_exception`` moniker when greater precision is not needed. In addition, all of the above exceptions derive from the standard ``std::exception`` for even more generalized error handling. The ``bad_parallel_edge`` exception is thrown when an attempt to add a parallel edge to the supplied MutableGraph fails. The graphml format supports parallel edges, but some BGL-compatible graph types do not. One example of such a graph is ``boost::adjacency_list<setS,vecS>``, which allows at most one edge can between any two vertices. The ``directed_graph_error`` exception occurs when an undirected graph type is passed to ``read_graph``, but the graph defined in the graphml file contains at least one directed edge. The ``undirected_graph_error`` exception occurs when a directed graph type is passed to ``read_graph``, but the graph defined in the graphml file contains at least one undirected edge. The ``parse_error`` exception occurs when a syntax error is encountered in the graphml file. The error string will contain the line and column where the error was encountered. Building the graphml reader ----------------------------- To use the graphml reader, you will need to build and link against the "bgl-graphml" library. The library can be built by following the `Boost Jam Build Instructions`_ for the subdirectory ``libs/graph/build``. Notes ----- - On successful reading of a graph, every vertex and edge will have an associated value for every respective edge and vertex property encountered while interpreting the graph. These values will be set using the ``dynamic_properties`` object. Some properties may be ``put`` multiple times during the course of reading in order to ensure the graphml semantics. Those edges and vertices that are not explicitly given a value for a property (and that property has no default) will be given the default constructed value of the value type. **Be sure that property map value types are default constructible.** - Nested graphs are supported as long as they are exactly of the same type as the root graph, i.e., are also directed or undirected. Note that since nested graphs are not directly supported by BGL, they are in fact completely ignored when building the graph, and the internal vertices or edges are interpreted as belonging to the root graph. - Hyperedges and Ports are not supported. See Also -------- write_graphml_ .. _Graphml: http://graphml.graphdrawing.org/ .. _`Mutable Graph`: MutableGraph.html .. _`Multi-Pass Iterator`: ../../iterator/index.html .. _dynamic_properties: ../../property_map/doc/dynamic_property_map.html .. _write_graphml: write_graphml.html .. _Boost Jam Build Instructions: ../../../more/getting_started.html#Build_Install // graph-tool -- a general graph modification and manipulation thingy // // Copyright (C) 2006 Tiago de Paula Peixoto <tiago@forked.de> // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation; either version 2 // of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. // Copyright (C) 2004 The Trustees of Indiana University. // // Boost Software License - Version 1.0 - August 17th, 2003 // // Permission is hereby granted, free of charge, to any person or organization // obtaining a copy of the software and accompanying documentation covered by // this license (the "Software") to use, reproduce, display, distribute, // execute, and transmit the Software, and to prepare derivative works of the // Software, and to permit third-parties to whom the Software is furnished to // do so, all subject to the following: // // The copyright notices in the Software and this entire statement, including // the above license grant, this restriction and the following disclaimer, // must be included in all copies of the Software, in whole or in part, and // all derivative works of the Software, unless such copies or derivative // works are solely in the form of machine-executable object code generated by // a source language processor. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT // SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE // FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER // DEALINGS IN THE SOFTWARE. // Authors: Douglas Gregor // Andrew Lumsdaine // Tiago de Paula Peixoto #ifndef GRAPHML_HPP #define GRAPHML_HPP #include <boost/config.hpp> #include <boost/lexical_cast.hpp> #include <boost/any.hpp> #include <boost/type_traits/is_convertible.hpp> #include <boost/graph/graphviz.hpp> // for exceptions #include <typeinfo> #include <boost/mpl/bool.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/find.hpp> #include <boost/mpl/for_each.hpp> #include <exception> #include <sstream> namespace boost { ///////////////////////////////////////////////////////////////////////////// // Graph reader exceptions ///////////////////////////////////////////////////////////////////////////// struct parse_error: public graph_exception { parse_error(const std::string& err) {error = err; statement = "parse error: " + error;} virtual ~parse_error() throw() {} virtual const char* what() const throw() {return statement.c_str();} std::string statement; std::string error; }; class mutate_graph { public: virtual ~mutate_graph() {} virtual bool is_directed() const = 0; virtual boost::any do_add_vertex() = 0; virtual std::pair<boost::any,bool> do_add_edge(boost::any source, boost::any target) = 0; virtual void set_graph_property(const std::string& name, const std::string& value, const std::string& value_type) = 0; virtual void set_vertex_property(const std::string& name, boost::any vertex, const std::string& value, const std::string& value_type) = 0; virtual void set_edge_property(const std::string& name, boost::any edge, const std::string& value, const std::string& value_type) = 0; }; template<typename MutableGraph> class mutate_graph_impl : public mutate_graph { typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_descriptor; typedef typename graph_traits<MutableGraph>::edge_descriptor edge_descriptor; public: mutate_graph_impl(MutableGraph& g, dynamic_properties& dp) : m_g(g), m_dp(dp) { } bool is_directed() const { return is_convertible<typename graph_traits<MutableGraph>::directed_category, directed_tag>::value; } virtual any do_add_vertex() { return any(add_vertex(m_g)); } virtual std::pair<any,bool> do_add_edge(any source, any target) { std::pair<edge_descriptor,bool> retval = add_edge(any_cast<vertex_descriptor>(source), any_cast<vertex_descriptor>(target), m_g); return std::make_pair(any(retval.first), retval.second); } virtual void set_graph_property(const std::string& name, const std::string& value, const std::string& value_type) { bool type_found = false; try { mpl::for_each<value_types>(put_property<MutableGraph,value_types> (name, m_dp, m_g, value, value_type, m_type_names, type_found)); } catch (bad_lexical_cast) { throw parse_error("invalid value \"" + value + "\" for key " + name + " of type " + value_type); } if (!type_found) throw parse_error("unrecognized type \"" + value_type + "\" for key " + name); } virtual void set_vertex_property(const std::string& name, any vertex, const std::string& value, const std::string& value_type) { bool type_found = false; try { mpl::for_each<value_types>(put_property<vertex_descriptor,value_types> (name, m_dp, any_cast<vertex_descriptor>(vertex), value, value_type, m_type_names, type_found)); } catch (bad_lexical_cast) { throw parse_error("invalid value \"" + value + "\" for key " + name + " of type " + value_type); } if (!type_found) throw parse_error("unrecognized type \"" + value_type + "\" for key " + name); } virtual void set_edge_property(const std::string& name, any edge, const std::string& value, const std::string& value_type) { bool type_found = false; try { mpl::for_each<value_types>(put_property<edge_descriptor,value_types> (name, m_dp, any_cast<edge_descriptor>(edge), value, value_type, m_type_names, type_found)); } catch (bad_lexical_cast) { throw parse_error("invalid value \"" + value + "\" for key " + name + " of type " + value_type); } if (!type_found) throw parse_error("unrecognized type \"" + value_type + "\" for key " + name); } template <typename Key, typename ValueVector> class put_property { public: put_property(const std::string& name, dynamic_properties& dp, const Key& key, const std::string& value, const std::string& value_type, char** type_names, bool& type_found) : m_name(name), m_dp(dp), m_key(key), m_value(value), m_value_type(value_type), m_type_names(type_names), m_type_found(type_found) {} template <class Value> void operator()(Value) { if (m_value_type == m_type_names[mpl::find<ValueVector,Value>::type::pos::value]) { put(m_name, m_dp, m_key, lexical_cast<Value>(m_value)); m_type_found = true; } } private: const std::string& m_name; dynamic_properties& m_dp; const Key& m_key; const std::string& m_value; const std::string& m_value_type; char** m_type_names; bool& m_type_found; }; protected: MutableGraph& m_g; dynamic_properties& m_dp; typedef mpl::vector<bool, int, long, float, double, std::string> value_types; static char* m_type_names[]; }; template<typename MutableGraph> char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean", "int", "long", "float", "double", "string"}; void read_graphml(std::istream& in, mutate_graph& g); template<typename MutableGraph> void read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp) { mutate_graph_impl<MutableGraph> mg(g,dp); read_graphml(in, mg); } template <typename Types> class get_type_name { public: get_type_name(const std::type_info& type, char** type_names, std::string& type_name) : m_type(type), m_type_names(type_names), m_type_name(type_name) {} template <typename Type> void operator()(Type) { if (typeid(Type) == m_type) m_type_name = m_type_names[mpl::find<Types,Type>::type::pos::value]; } private: const std::type_info &m_type; char** m_type_names; std::string &m_type_name; }; template <typename Graph, typename VertexIndexMap> void write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index, const dynamic_properties& dp, bool ordered_vertices=false) { typedef typename graph_traits<Graph>::directed_category directed_category; typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; BOOST_STATIC_CONSTANT(bool, graph_is_directed = (is_convertible<directed_category*, directed_tag*>::value)); out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n" << "<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd\">\n"; typedef mpl::vector<bool, short, unsigned short, int, unsigned int, long, unsigned long, long long, unsigned long long, float, double, long double, std::string> value_types; char* type_names[] = {"boolean", "int", "int", "int", "int", "long", "long", "long", "long", "float", "double", "double", "string"}; std::map<std::string, std::string> graph_key_ids; std::map<std::string, std::string> vertex_key_ids; std::map<std::string, std::string> edge_key_ids; int key_count = 0; // Output keys for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) { std::string key_id = "key" + lexical_cast<std::string>(key_count++); if (i->second->key() == typeid(Graph)) vertex_key_ids[i->first] = key_id; else if (i->second->key() == typeid(vertex_descriptor)) vertex_key_ids[i->first] = key_id; else if (i->second->key() == typeid(edge_descriptor)) edge_key_ids[i->first] = key_id; else continue; std::string type_name = "string"; mpl::for_each<value_types>(get_type_name<value_types>(i->second->value(), type_names, type_name)); out << " <key id=\"" << key_id << "\" for=\"" << (i->second->key() == typeid(Graph) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\"" << " attr.name=\"" << i->first << "\"" << " attr.type=\"" << type_name << "\"" << " />\n"; } out << " <graph id=\"G\" edgedefault=\"" << (graph_is_directed ? "directed" : "undirected") << "\"" << " parse.nodeids=\"" << (ordered_vertices ? "canonical" : "free") << "\"" << " parse.edgeids=\"canonical\" parse.order=\"nodesfirst\">\n"; // Output graph data for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) { if (i->second->key() == typeid(Graph)) { out << " <data key=\"" << graph_key_ids[i->first] << "\">" << i->second->get_string(g) << "</data>\n"; } } typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; vertex_iterator v, v_end; for (tie(v, v_end) = vertices(g); v != v_end; ++v) { out << " <node id=\"n" << get(vertex_index, *v) << "\">\n"; // Output data for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) { if (i->second->key() == typeid(vertex_descriptor)) { out << " <data key=\"" << vertex_key_ids[i->first] << "\">" << i->second->get_string(*v) << "</data>\n"; } } out << " </node>\n"; } typedef typename graph_traits<Graph>::edge_iterator edge_iterator; edge_iterator e, e_end; typename graph_traits<Graph>::edges_size_type edge_count = 0; for (tie(e, e_end) = edges(g); e != e_end; ++e) { out << " <edge id=\"e" << edge_count++ << "\" source=\"n" << get(vertex_index, source(*e, g)) << "\" target=\"n" << get(vertex_index, target(*e, g)) << "\">\n"; // Output data for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) { if (i->second->key() == typeid(edge_descriptor)) { out << " <data key=\"" << edge_key_ids[i->first] << "\">" << i->second->get_string(*e) << "</data>\n"; } } out << " </edge>\n"; } out << " </graph>\n" << "</graphml>\n"; } template <typename Graph> void write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp, bool ordered_vertices=false) { write_graphml(out, g, get(vertex_index, g), dp, ordered_vertices); } } // boost namespace #endif