]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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>(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>(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(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(*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(*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 |