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