]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
1e59de90 TL |
21 | #include <map> |
22 | #include <string> | |
23 | #include <vector> | |
7c673cae FG |
24 | |
25 | using namespace boost; | |
26 | ||
f67539c2 TL |
27 | namespace |
28 | { | |
7c673cae FG |
29 | |
30 | class graphml_reader | |
31 | { | |
32 | public: | |
f67539c2 | 33 | graphml_reader(mutate_graph& g) : m_g(g) {} |
7c673cae | 34 | |
f67539c2 TL |
35 | static boost::property_tree::ptree::path_type path(const std::string& str) |
36 | { | |
37 | return boost::property_tree::ptree::path_type(str, '/'); | |
7c673cae FG |
38 | } |
39 | ||
40 | void get_graphs(const boost::property_tree::ptree& top, | |
f67539c2 TL |
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") | |
7c673cae | 50 | { |
f67539c2 TL |
51 | if (current_idx == desired_idx || desired_idx == (size_t)(-1)) |
52 | { | |
53 | result.push_back(&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("<xmlattr>/key")); | |
63 | std::string value = attr.second.get_value(""); | |
64 | handle_graph_property(key, value); | |
65 | } | |
66 | } | |
67 | ||
68 | get_graphs(n.second, (size_t)(-1), false, result); | |
69 | if (desired_idx != (size_t)(-1)) | |
70 | break; | |
71 | } | |
72 | ++current_idx; | |
7c673cae | 73 | } |
7c673cae | 74 | } |
7c673cae | 75 | } |
f67539c2 | 76 | |
7c673cae FG |
77 | void run(std::istream& in, size_t desired_idx) |
78 | { | |
f67539c2 TL |
79 | using boost::property_tree::ptree; |
80 | ptree pt; | |
81 | read_xml(in, pt, | |
82 | boost::property_tree::xml_parser::no_comments | |
83 | | boost::property_tree::xml_parser::trim_whitespace); | |
84 | ptree gml = pt.get_child(path("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("<xmlattr>/id"), ""); | |
91 | std::string for_ = child.second.get(path("<xmlattr>/for"), ""); | |
92 | std::string name | |
93 | = child.second.get(path("<xmlattr>/attr.name"), ""); | |
94 | std::string type | |
95 | = child.second.get(path("<xmlattr>/attr.type"), ""); | |
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("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(gml, desired_idx, true, 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("<xmlattr>/id")); | |
139 | handle_vertex(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("<xmlattr>/key")); | |
146 | std::string value = attr.second.get_value(""); | |
147 | handle_node_property(key, id, value); | |
148 | } | |
149 | } | |
7c673cae | 150 | } |
f67539c2 TL |
151 | BOOST_FOREACH (const ptree* gr, graphs) |
152 | { | |
153 | bool default_directed | |
154 | = gr->get< std::string >(path("<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("<xmlattr>/source")); | |
163 | std::string target | |
164 | = edge.second.get< std::string >(path("<xmlattr>/target")); | |
165 | std::string local_directed | |
166 | = edge.second.get(path("<xmlattr>/directed"), ""); | |
167 | bool is_directed | |
1e59de90 TL |
168 | = (local_directed.empty() ? default_directed |
169 | : local_directed == "true"); | |
f67539c2 TL |
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(source, 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("<xmlattr>/key")); | |
189 | std::string value = attr.second.get_value(""); | |
190 | handle_edge_property(key, old_edges_size, value); | |
191 | } | |
7c673cae | 192 | } |
7c673cae | 193 | } |
7c673cae FG |
194 | } |
195 | ||
196 | private: | |
197 | /// The kinds of keys. Not all of these are supported | |
f67539c2 TL |
198 | enum key_kind |
199 | { | |
200 | graph_key, | |
201 | node_key, | |
7c673cae FG |
202 | edge_key, |
203 | hyperedge_key, | |
204 | port_key, | |
f67539c2 | 205 | endpoint_key, |
7c673cae FG |
206 | all_key, |
207 | graphml_key | |
208 | }; | |
209 | ||
f67539c2 | 210 | void handle_vertex(const std::string& v) |
7c673cae FG |
211 | { |
212 | bool is_new = false; | |
213 | ||
214 | if (m_vertex.find(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 | { | |
f67539c2 TL |
222 | std::map< std::string, std::string >::iterator iter; |
223 | for (iter = m_key_default.begin(); iter != m_key_default.end(); | |
224 | ++iter) | |
7c673cae FG |
225 | { |
226 | if (m_keys[iter->first] == node_key) | |
227 | handle_node_property(iter->first, v, iter->second); | |
228 | } | |
229 | } | |
230 | } | |
231 | ||
f67539c2 | 232 | any get_vertex_descriptor(const std::string& v) { return m_vertex[v]; } |
7c673cae | 233 | |
f67539c2 | 234 | void handle_edge(const std::string& u, const std::string& v) |
7c673cae FG |
235 | { |
236 | handle_vertex(u); | |
237 | handle_vertex(v); | |
238 | ||
239 | any source, target; | |
240 | source = get_vertex_descriptor(u); | |
241 | target = get_vertex_descriptor(v); | |
242 | ||
243 | any edge; | |
244 | bool added; | |
245 | boost::tie(edge, added) = m_g.do_add_edge(source, target); | |
f67539c2 TL |
246 | if (!added) |
247 | { | |
7c673cae FG |
248 | BOOST_THROW_EXCEPTION(bad_parallel_edge(u, v)); |
249 | } | |
250 | ||
251 | size_t e = m_edge.size(); | |
252 | m_edge.push_back(edge); | |
f67539c2 TL |
253 | |
254 | std::map< std::string, std::string >::iterator iter; | |
7c673cae FG |
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(iter->first, e, iter->second); | |
259 | } | |
260 | } | |
261 | ||
f67539c2 | 262 | void handle_graph() |
7c673cae | 263 | { |
f67539c2 TL |
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(iter->first, iter->second); | |
269 | } | |
7c673cae FG |
270 | } |
271 | ||
f67539c2 TL |
272 | void handle_graph_property( |
273 | const std::string& key_id, const std::string& value) | |
7c673cae | 274 | { |
f67539c2 | 275 | m_g.set_graph_property(m_key_name[key_id], value, m_key_type[key_id]); |
7c673cae FG |
276 | } |
277 | ||
f67539c2 TL |
278 | void handle_node_property(const std::string& key_id, |
279 | const std::string& descriptor, const std::string& value) | |
7c673cae | 280 | { |
f67539c2 TL |
281 | m_g.set_vertex_property(m_key_name[key_id], m_vertex[descriptor], value, |
282 | m_key_type[key_id]); | |
7c673cae FG |
283 | } |
284 | ||
f67539c2 TL |
285 | void handle_edge_property( |
286 | const std::string& key_id, size_t descriptor, const std::string& value) | |
7c673cae | 287 | { |
f67539c2 TL |
288 | m_g.set_edge_property( |
289 | m_key_name[key_id], m_edge[descriptor], value, m_key_type[key_id]); | |
7c673cae FG |
290 | } |
291 | ||
292 | mutate_graph& m_g; | |
f67539c2 TL |
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; | |
7c673cae FG |
299 | }; |
300 | ||
301 | } | |
302 | ||
303 | namespace boost | |
304 | { | |
f67539c2 TL |
305 | void BOOST_GRAPH_DECL read_graphml( |
306 | std::istream& in, mutate_graph& g, size_t desired_idx) | |
307 | { | |
7c673cae FG |
308 | graphml_reader reader(g); |
309 | reader.run(in, desired_idx); | |
310 | } | |
311 | } |