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
============================
|(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
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
-------------
````
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 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
-------------
````
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``,
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
//
// 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
#include
#include
#include
#include // for exceptions
#include <typeinfo>
#include
#include
#include
#include
#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::pairboost::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::value;
}
virtual any do_add_vertex()
{
return any(add_vertex(m_g));
}
virtual std::pair do_add_edge(any source, any target)
{
std::pair retval = add_edge(any_cast(source),
any_cast(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(put_property
(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(put_property
(name, m_dp, any_cast(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(put_property
(name, m_dp, any_cast(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
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::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 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::type::pos::value];
}
private:
const std::type_info &m_type;
char** m_type_names;
std::string &m_type_name;
};
template
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::value));
out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"
<< "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 value_types;
char* type_names[] = {"boolean", "int", "int", "int", "int", "long", "long", "long", "long", "float", "double", "double", "string"};
std::map graph_key_ids;
std::map vertex_key_ids;
std::map 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_caststd::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(get_type_name(i->second->value(), type_names, type_name));
out << " second->key() == typeid(Graph) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\""
<< " attr.name=\"" << i->first << "\""
<< " attr.type=\"" << type_name << "\""
<< " />\n";
}
out << " \n";
// Output graph data
for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
{
if (i->second->key() == typeid(Graph))
{
out << " 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 << " \n";
// Output data
for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
{
if (i->second->key() == typeid(vertex_descriptor))
{
out << " 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 << " \n";
// Output data
for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
{
if (i->second->key() == typeid(edge_descriptor))
{
out << " 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
