1 | // Copyright (C) 2006 Tiago de Paula Peixoto <tiago@forked.de> |
2 | // Copyright (C) 2004,2009 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 | // Jeremiah Willcock |
10 | // Andrew Lumsdaine |
11 | // Tiago de Paula Peixoto |
12 | |
13 | #define BOOST_GRAPH_SOURCE |
14 | #include <boost/foreach.hpp> |
15 | #include <boost/optional.hpp> |
16 | #include <boost/throw_exception.hpp> |
17 | #include <boost/graph/graphml.hpp> |
18 | #include <boost/graph/dll_import_export.hpp> |
19 | #include <boost/property_tree/ptree.hpp> |
20 | #include <boost/property_tree/xml_parser.hpp> |
21 | #include <map> |
22 | #include <string> |
23 | #include <vector> |
24 | |
25 | using namespace boost; |
26 | |
27 | namespace |
28 | { |
29 | |
30 | class graphml_reader |
31 | { |
32 | public: |
33 | graphml_reader(mutate_graph& g) : m_g(g) {} |
34 | |
35 | static boost::property_tree::ptree::path_type path(const std::string& str) |
36 | { |
37 | return boost::property_tree::ptree::path_type(str, '/'); |
38 | } |
39 | |
40 | void get_graphs(const boost::property_tree::ptree& top, |
41 | size_t desired_idx /* or -1 for all */, bool is_root, |
42 | std::vector< const boost::property_tree::ptree* >& result) |
43 | { |
44 | using boost::property_tree::ptree; |
45 | size_t current_idx = 0; |
46 | bool is_first = is_root; |
47 | BOOST_FOREACH (const ptree::value_type& n, top) |
48 | { |
49 | if (n.first == "graph" ) |
50 | { |
51 | if (current_idx == desired_idx || desired_idx == (size_t)(-1)) |
52 | { |
53 | result.push_back(x: &n.second); |
54 | if (is_first) |
55 | { |
56 | is_first = false; |
57 | BOOST_FOREACH (const ptree::value_type& attr, n.second) |
58 | { |
59 | if (attr.first != "data" ) |
60 | continue; |
61 | std::string key = attr.second.get< std::string >( |
62 | path: path(str: "<xmlattr>/key" )); |
63 | std::string value = attr.second.get_value(default_value: "" ); |
64 | handle_graph_property(key_id: key, value); |
65 | } |
66 | } |
67 | |
68 | get_graphs(top: n.second, desired_idx: (size_t)(-1), is_root: false, result); |
69 | if (desired_idx != (size_t)(-1)) |
70 | break; |
71 | } |
72 | ++current_idx; |
73 | } |
74 | } |
75 | } |
76 | |
77 | void run(std::istream& in, size_t desired_idx) |
78 | { |
79 | using boost::property_tree::ptree; |
80 | ptree pt; |
81 | read_xml(stream&: in, pt, |
82 | flags: boost::property_tree::xml_parser::no_comments |
83 | | boost::property_tree::xml_parser::trim_whitespace); |
84 | ptree gml = pt.get_child(path: path(str: "graphml" )); |
85 | // Search for attributes |
86 | BOOST_FOREACH (const ptree::value_type& child, gml) |
87 | { |
88 | if (child.first != "key" ) |
89 | continue; |
90 | std::string id = child.second.get(path: path(str: "<xmlattr>/id" ), default_value: "" ); |
91 | std::string for_ = child.second.get(path: path(str: "<xmlattr>/for" ), default_value: "" ); |
92 | std::string name |
93 | = child.second.get(path: path(str: "<xmlattr>/attr.name" ), default_value: "" ); |
94 | std::string type |
95 | = child.second.get(path: path(str: "<xmlattr>/attr.type" ), default_value: "" ); |
96 | key_kind kind = all_key; |
97 | if (for_ == "graph" ) |
98 | kind = graph_key; |
99 | else if (for_ == "node" ) |
100 | kind = node_key; |
101 | else if (for_ == "edge" ) |
102 | kind = edge_key; |
103 | else if (for_ == "hyperedge" ) |
104 | kind = hyperedge_key; |
105 | else if (for_ == "port" ) |
106 | kind = port_key; |
107 | else if (for_ == "endpoint" ) |
108 | kind = endpoint_key; |
109 | else if (for_ == "all" ) |
110 | kind = all_key; |
111 | else if (for_ == "graphml" ) |
112 | kind = graphml_key; |
113 | else |
114 | { |
115 | BOOST_THROW_EXCEPTION( |
116 | parse_error("Attribute for is not valid: " + for_)); |
117 | } |
118 | m_keys[id] = kind; |
119 | m_key_name[id] = name; |
120 | m_key_type[id] = type; |
121 | boost::optional< std::string > default_ |
122 | = child.second.get_optional< std::string >(path: path(str: "default" )); |
123 | if (default_) |
124 | m_key_default[id] = default_.get(); |
125 | } |
126 | // Search for graphs |
127 | std::vector< const ptree* > graphs; |
128 | handle_graph(); |
129 | get_graphs(top: gml, desired_idx, is_root: true, result&: graphs); |
130 | BOOST_FOREACH (const ptree* gr, graphs) |
131 | { |
132 | // Search for nodes |
133 | BOOST_FOREACH (const ptree::value_type& node, *gr) |
134 | { |
135 | if (node.first != "node" ) |
136 | continue; |
137 | std::string id |
138 | = node.second.get< std::string >(path: path(str: "<xmlattr>/id" )); |
139 | handle_vertex(v: id); |
140 | BOOST_FOREACH (const ptree::value_type& attr, node.second) |
141 | { |
142 | if (attr.first != "data" ) |
143 | continue; |
144 | std::string key |
145 | = attr.second.get< std::string >(path: path(str: "<xmlattr>/key" )); |
146 | std::string value = attr.second.get_value(default_value: "" ); |
147 | handle_node_property(key_id: key, descriptor: id, value); |
148 | } |
149 | } |
150 | } |
151 | BOOST_FOREACH (const ptree* gr, graphs) |
152 | { |
153 | bool default_directed |
154 | = gr->get< std::string >(path: path(str: "<xmlattr>/edgedefault" )) |
155 | == "directed" ; |
156 | // Search for edges |
157 | BOOST_FOREACH (const ptree::value_type& edge, *gr) |
158 | { |
159 | if (edge.first != "edge" ) |
160 | continue; |
161 | std::string source |
162 | = edge.second.get< std::string >(path: path(str: "<xmlattr>/source" )); |
163 | std::string target |
164 | = edge.second.get< std::string >(path: path(str: "<xmlattr>/target" )); |
165 | std::string local_directed |
166 | = edge.second.get(path: path(str: "<xmlattr>/directed" ), default_value: "" ); |
167 | bool is_directed |
168 | = (local_directed.empty() ? default_directed |
169 | : local_directed == "true" ); |
170 | if (is_directed != m_g.is_directed()) |
171 | { |
172 | if (is_directed) |
173 | { |
174 | BOOST_THROW_EXCEPTION(directed_graph_error()); |
175 | } |
176 | else |
177 | { |
178 | BOOST_THROW_EXCEPTION(undirected_graph_error()); |
179 | } |
180 | } |
181 | size_t old_edges_size = m_edge.size(); |
182 | handle_edge(u: source, v: target); |
183 | BOOST_FOREACH (const ptree::value_type& attr, edge.second) |
184 | { |
185 | if (attr.first != "data" ) |
186 | continue; |
187 | std::string key |
188 | = attr.second.get< std::string >(path: path(str: "<xmlattr>/key" )); |
189 | std::string value = attr.second.get_value(default_value: "" ); |
190 | handle_edge_property(key_id: key, descriptor: old_edges_size, value); |
191 | } |
192 | } |
193 | } |
194 | } |
195 | |
196 | private: |
197 | /// The kinds of keys. Not all of these are supported |
198 | enum key_kind |
199 | { |
200 | graph_key, |
201 | node_key, |
202 | edge_key, |
203 | hyperedge_key, |
204 | port_key, |
205 | endpoint_key, |
206 | all_key, |
207 | graphml_key |
208 | }; |
209 | |
210 | void handle_vertex(const std::string& v) |
211 | { |
212 | bool is_new = false; |
213 | |
214 | if (m_vertex.find(x: v) == m_vertex.end()) |
215 | { |
216 | m_vertex[v] = m_g.do_add_vertex(); |
217 | is_new = true; |
218 | } |
219 | |
220 | if (is_new) |
221 | { |
222 | std::map< std::string, std::string >::iterator iter; |
223 | for (iter = m_key_default.begin(); iter != m_key_default.end(); |
224 | ++iter) |
225 | { |
226 | if (m_keys[iter->first] == node_key) |
227 | handle_node_property(key_id: iter->first, descriptor: v, value: iter->second); |
228 | } |
229 | } |
230 | } |
231 | |
232 | any get_vertex_descriptor(const std::string& v) { return m_vertex[v]; } |
233 | |
234 | void handle_edge(const std::string& u, const std::string& v) |
235 | { |
236 | handle_vertex(v: u); |
237 | handle_vertex(v); |
238 | |
239 | any source, target; |
240 | source = get_vertex_descriptor(v: u); |
241 | target = get_vertex_descriptor(v); |
242 | |
243 | any edge; |
244 | bool added; |
245 | boost::tie(t0&: edge, t1&: added) = m_g.do_add_edge(source, target); |
246 | if (!added) |
247 | { |
248 | BOOST_THROW_EXCEPTION(bad_parallel_edge(u, v)); |
249 | } |
250 | |
251 | size_t e = m_edge.size(); |
252 | m_edge.push_back(x: edge); |
253 | |
254 | std::map< std::string, std::string >::iterator iter; |
255 | for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter) |
256 | { |
257 | if (m_keys[iter->first] == edge_key) |
258 | handle_edge_property(key_id: iter->first, descriptor: e, value: iter->second); |
259 | } |
260 | } |
261 | |
262 | void handle_graph() |
263 | { |
264 | std::map< std::string, std::string >::iterator iter; |
265 | for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter) |
266 | { |
267 | if (m_keys[iter->first] == graph_key) |
268 | handle_graph_property(key_id: iter->first, value: iter->second); |
269 | } |
270 | } |
271 | |
272 | void handle_graph_property( |
273 | const std::string& key_id, const std::string& value) |
274 | { |
275 | m_g.set_graph_property(name: m_key_name[key_id], value, value_type: m_key_type[key_id]); |
276 | } |
277 | |
278 | void handle_node_property(const std::string& key_id, |
279 | const std::string& descriptor, const std::string& value) |
280 | { |
281 | m_g.set_vertex_property(name: m_key_name[key_id], vertex: m_vertex[descriptor], value, |
282 | value_type: m_key_type[key_id]); |
283 | } |
284 | |
285 | void handle_edge_property( |
286 | const std::string& key_id, size_t descriptor, const std::string& value) |
287 | { |
288 | m_g.set_edge_property( |
289 | name: m_key_name[key_id], edge: m_edge[descriptor], value, value_type: m_key_type[key_id]); |
290 | } |
291 | |
292 | mutate_graph& m_g; |
293 | std::map< std::string, key_kind > m_keys; |
294 | std::map< std::string, std::string > m_key_name; |
295 | std::map< std::string, std::string > m_key_type; |
296 | std::map< std::string, std::string > m_key_default; |
297 | std::map< std::string, any > m_vertex; |
298 | std::vector< any > m_edge; |
299 | }; |
300 | |
301 | } |
302 | |
303 | namespace boost |
304 | { |
305 | void BOOST_GRAPH_DECL read_graphml( |
306 | std::istream& in, mutate_graph& g, size_t desired_idx) |
307 | { |
308 | graphml_reader reader(g); |
309 | reader.run(in, desired_idx); |
310 | } |
311 | } |
312 | |