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
25using namespace boost;
26
27namespace
28{
29
30class graphml_reader
31{
32public:
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
196private:
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
303namespace boost
304{
305void 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

source code of boost/libs/graph/src/graphml.cpp