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