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 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 | |
47 | class mutate_graph |
48 | { |
49 | public: |
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 | |
66 | template<typename MutableGraph> |
67 | class 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 | |
196 | protected: |
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 | |
203 | template<typename MutableGraph> |
204 | const char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean" , "int" , "long" , "float" , "double" , "string" }; |
205 | |
206 | void BOOST_GRAPH_DECL |
207 | read_graphml(std::istream& in, mutate_graph& g, size_t desired_idx); |
208 | |
209 | template<typename MutableGraph> |
210 | void |
211 | read_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 | |
217 | template <typename Types> |
218 | class get_type_name |
219 | { |
220 | public: |
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 | } |
229 | private: |
230 | const std::type_info &m_type; |
231 | const char** m_type_names; |
232 | std::string &m_type_name; |
233 | }; |
234 | |
235 | |
236 | template <typename Graph, typename VertexIndexMap> |
237 | void |
238 | write_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 | |
342 | template <typename Graph> |
343 | void |
344 | write_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 | |