1// Copyright (C) 2006 Tiago de Paula Peixoto <tiago@forked.de>
2// Copyright (C) 2004 The Trustees of Indiana University.
3//
4// Use, modification and distribution is subject to the Boost Software
5// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7//
8// Authors: Douglas Gregor
9// Andrew Lumsdaine
10// Tiago de Paula Peixoto
11
12#ifndef BOOST_GRAPH_GRAPHML_HPP
13#define BOOST_GRAPH_GRAPHML_HPP
14
15#include <boost/config.hpp>
16#include <boost/lexical_cast.hpp>
17#include <boost/any.hpp>
18#include <boost/type_traits/is_convertible.hpp>
19#include <boost/graph/dll_import_export.hpp>
20#include <boost/graph/graphviz.hpp> // for exceptions
21#include <typeinfo>
22#include <boost/mpl/bool.hpp>
23#include <boost/mpl/vector.hpp>
24#include <boost/mpl/find.hpp>
25#include <boost/mpl/for_each.hpp>
26#include <boost/property_tree/detail/xml_parser_utils.hpp>
27#include <boost/throw_exception.hpp>
28#include <exception>
29#include <sstream>
30
31namespace boost
32{
33
34/////////////////////////////////////////////////////////////////////////////
35// Graph reader exceptions
36/////////////////////////////////////////////////////////////////////////////
37struct parse_error: public graph_exception
38{
39 parse_error(const std::string& err) {error = err; statement = "parse error: " + error;}
40 virtual ~parse_error() throw() {}
41 virtual const char* what() const throw() {return statement.c_str();}
42 std::string statement;
43 std::string error;
44};
45
46
47class mutate_graph
48{
49public:
50 virtual ~mutate_graph() {}
51 virtual bool is_directed() const = 0;
52
53 virtual boost::any do_add_vertex() = 0;
54 virtual std::pair<boost::any,bool> do_add_edge(boost::any source, boost::any target) = 0;
55
56 virtual void
57 set_graph_property(const std::string& name, const std::string& value, const std::string& value_type) = 0;
58
59 virtual void
60 set_vertex_property(const std::string& name, boost::any vertex, const std::string& value, const std::string& value_type) = 0;
61
62 virtual void
63 set_edge_property(const std::string& name, boost::any edge, const std::string& value, const std::string& value_type) = 0;
64};
65
66template<typename MutableGraph>
67class mutate_graph_impl : public mutate_graph
68{
69 typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_descriptor;
70 typedef typename graph_traits<MutableGraph>::edge_descriptor edge_descriptor;
71
72 public:
73 mutate_graph_impl(MutableGraph& g, dynamic_properties& dp)
74 : m_g(g), m_dp(dp) { }
75
76 bool is_directed() const
77 {
78 return is_convertible<typename graph_traits<MutableGraph>::directed_category,
79 directed_tag>::value;
80 }
81
82 virtual any do_add_vertex()
83 {
84 return any(add_vertex(m_g));
85 }
86
87 virtual std::pair<any,bool> do_add_edge(any source, any target)
88 {
89 std::pair<edge_descriptor,bool> retval = add_edge(any_cast<vertex_descriptor>(source),
90 any_cast<vertex_descriptor>(target), m_g);
91 return std::make_pair(any(retval.first), retval.second);
92 }
93
94 virtual void
95 set_graph_property(const std::string& name, const std::string& value, const std::string& value_type)
96 {
97 bool type_found = false;
98 try
99 {
100 mpl::for_each<value_types>(put_property<MutableGraph,value_types>
101 (name, m_dp, m_g, value, value_type, m_type_names, type_found));
102 }
103 catch (bad_lexical_cast)
104 {
105 BOOST_THROW_EXCEPTION(
106 parse_error("invalid value \"" + value + "\" for key " +
107 name + " of type " + value_type));
108 }
109 if (!type_found)
110 {
111 BOOST_THROW_EXCEPTION(
112 parse_error("unrecognized type \"" + value_type +
113 "\" for key " + name));
114 }
115
116 }
117
118 virtual void
119 set_vertex_property(const std::string& name, any vertex, const std::string& value, const std::string& value_type)
120 {
121 bool type_found = false;
122 try
123 {
124 mpl::for_each<value_types>(put_property<vertex_descriptor,value_types>
125 (name, m_dp, any_cast<vertex_descriptor>(vertex),
126 value, value_type, m_type_names, type_found));
127 }
128 catch (bad_lexical_cast)
129 {
130 BOOST_THROW_EXCEPTION(
131 parse_error("invalid value \"" + value + "\" for key " +
132 name + " of type " + value_type));
133 }
134 if (!type_found)
135 {
136 BOOST_THROW_EXCEPTION(
137 parse_error("unrecognized type \"" + value_type +
138 "\" for key " + name));
139 }
140
141 }
142
143 virtual void
144 set_edge_property(const std::string& name, any edge, const std::string& value, const std::string& value_type)
145 {
146 bool type_found = false;
147 try
148 {
149 mpl::for_each<value_types>(put_property<edge_descriptor,value_types>
150 (name, m_dp, any_cast<edge_descriptor>(edge),
151 value, value_type, m_type_names, type_found));
152 }
153 catch (bad_lexical_cast)
154 {
155 BOOST_THROW_EXCEPTION(
156 parse_error("invalid value \"" + value + "\" for key " +
157 name + " of type " + value_type));
158 }
159 if (!type_found)
160 {
161 BOOST_THROW_EXCEPTION(
162 parse_error("unrecognized type \"" + value_type +
163 "\" for key " + name));
164 }
165 }
166
167 template <typename Key, typename ValueVector>
168 class put_property
169 {
170 public:
171 put_property(const std::string& name, dynamic_properties& dp, const Key& key,
172 const std::string& value, const std::string& value_type,
173 const char** type_names, bool& type_found)
174 : m_name(name), m_dp(dp), m_key(key), m_value(value),
175 m_value_type(value_type), m_type_names(type_names),
176 m_type_found(type_found) {}
177 template <class Value>
178 void operator()(Value)
179 {
180 if (m_value_type == m_type_names[mpl::find<ValueVector,Value>::type::pos::value])
181 {
182 put(m_name, m_dp, m_key, lexical_cast<Value>(m_value));
183 m_type_found = true;
184 }
185 }
186 private:
187 const std::string& m_name;
188 dynamic_properties& m_dp;
189 const Key& m_key;
190 const std::string& m_value;
191 const std::string& m_value_type;
192 const char** m_type_names;
193 bool& m_type_found;
194 };
195
196protected:
197 MutableGraph& m_g;
198 dynamic_properties& m_dp;
199 typedef mpl::vector<bool, int, long, float, double, std::string> value_types;
200 static const char* m_type_names[];
201};
202
203template<typename MutableGraph>
204const char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean", "int", "long", "float", "double", "string"};
205
206void BOOST_GRAPH_DECL
207read_graphml(std::istream& in, mutate_graph& g, size_t desired_idx);
208
209template<typename MutableGraph>
210void
211read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp, size_t desired_idx = 0)
212{
213 mutate_graph_impl<MutableGraph> mg(g,dp);
214 read_graphml(in, mg, desired_idx);
215}
216
217template <typename Types>
218class get_type_name
219{
220public:
221 get_type_name(const std::type_info& type, const char** type_names, std::string& type_name)
222 : m_type(type), m_type_names(type_names), m_type_name(type_name) {}
223 template <typename Type>
224 void operator()(Type)
225 {
226 if (typeid(Type) == m_type)
227 m_type_name = m_type_names[mpl::find<Types,Type>::type::pos::value];
228 }
229private:
230 const std::type_info &m_type;
231 const char** m_type_names;
232 std::string &m_type_name;
233};
234
235
236template <typename Graph, typename VertexIndexMap>
237void
238write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index,
239 const dynamic_properties& dp, bool ordered_vertices=false)
240{
241 typedef typename graph_traits<Graph>::directed_category directed_category;
242 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
243 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
244
245 using boost::property_tree::xml_parser::encode_char_entities;
246
247 BOOST_STATIC_CONSTANT(bool,
248 graph_is_directed =
249 (is_convertible<directed_category*, directed_tag*>::value));
250
251 out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"
252 << "<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";
253
254 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;
255 const char* type_names[] = {"boolean", "int", "int", "int", "int", "long", "long", "long", "long", "float", "double", "double", "string"};
256 std::map<std::string, std::string> graph_key_ids;
257 std::map<std::string, std::string> vertex_key_ids;
258 std::map<std::string, std::string> edge_key_ids;
259 int key_count = 0;
260
261 // Output keys
262 for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
263 {
264 std::string key_id = "key" + lexical_cast<std::string>(arg: key_count++);
265 if (i->second->key() == typeid(Graph*))
266 graph_key_ids[i->first] = key_id;
267 else if (i->second->key() == typeid(vertex_descriptor))
268 vertex_key_ids[i->first] = key_id;
269 else if (i->second->key() == typeid(edge_descriptor))
270 edge_key_ids[i->first] = key_id;
271 else
272 continue;
273 std::string type_name = "string";
274 mpl::for_each<value_types>(f: get_type_name<value_types>(i->second->value(), type_names, type_name));
275 out << " <key id=\"" << encode_char_entities(key_id) << "\" for=\""
276 << (i->second->key() == typeid(Graph*) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\""
277 << " attr.name=\"" << i->first << "\""
278 << " attr.type=\"" << type_name << "\""
279 << " />\n";
280 }
281
282 out << " <graph id=\"G\" edgedefault=\""
283 << (graph_is_directed ? "directed" : "undirected") << "\""
284 << " parse.nodeids=\"" << (ordered_vertices ? "canonical" : "free") << "\""
285 << " parse.edgeids=\"canonical\" parse.order=\"nodesfirst\">\n";
286
287 // Output graph data
288 for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
289 {
290 if (i->second->key() == typeid(Graph*))
291 {
292 // The const_cast here is just to get typeid correct for property
293 // map key; the graph should not be mutated using it.
294 out << " <data key=\"" << graph_key_ids[i->first] << "\">"
295 << encode_char_entities(i->second->get_string(key: const_cast<Graph*>(&g))) << "</data>\n";
296 }
297 }
298
299 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
300 vertex_iterator v, v_end;
301 for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
302 {
303 out << " <node id=\"n" << get(vertex_index, *v) << "\">\n";
304 // Output data
305 for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
306 {
307 if (i->second->key() == typeid(vertex_descriptor))
308 {
309 out << " <data key=\"" << vertex_key_ids[i->first] << "\">"
310 << encode_char_entities(i->second->get_string(key: *v)) << "</data>\n";
311 }
312 }
313 out << " </node>\n";
314 }
315
316 typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
317 edge_iterator e, e_end;
318 typename graph_traits<Graph>::edges_size_type edge_count = 0;
319 for (boost::tie(e, e_end) = edges(g); e != e_end; ++e)
320 {
321 out << " <edge id=\"e" << edge_count++ << "\" source=\"n"
322 << get(vertex_index, source(*e, g)) << "\" target=\"n"
323 << get(vertex_index, target(*e, g)) << "\">\n";
324
325 // Output data
326 for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
327 {
328 if (i->second->key() == typeid(edge_descriptor))
329 {
330 out << " <data key=\"" << edge_key_ids[i->first] << "\">"
331 << encode_char_entities(i->second->get_string(key: *e)) << "</data>\n";
332 }
333 }
334 out << " </edge>\n";
335 }
336
337 out << " </graph>\n"
338 << "</graphml>\n";
339}
340
341
342template <typename Graph>
343void
344write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp,
345 bool ordered_vertices=false)
346{
347 write_graphml(out, g, get(vertex_index, g), dp, ordered_vertices);
348}
349
350} // boost namespace
351
352#endif // BOOST_GRAPH_GRAPHML_HPP
353

source code of boost/boost/graph/graphml.hpp