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 | class graphml_reader |
27 | { |
28 | public: |
29 | graphml_reader(mutate_graph& g) |
30 | : m_g(g) { } |
31 | |
32 | static boost::property_tree::ptree::path_type path(const std::string& str) { |
33 | return boost::property_tree::ptree::path_type(str, '/'); |
34 | } |
35 | |
36 | static void get_graphs(const boost::property_tree::ptree& top, |
37 | size_t desired_idx /* or -1 for all */, |
38 | std::vector<const boost::property_tree::ptree*>& result) { |
39 | using boost::property_tree::ptree; |
40 | size_t current_idx = 0; |
41 | BOOST_FOREACH(const ptree::value_type& n, top) { |
42 | if (n.first == "graph" ) { |
43 | if (current_idx == desired_idx || desired_idx == (size_t)(-1)) { |
44 | result.push_back(x: &n.second); |
45 | get_graphs(top: n.second, desired_idx: (size_t)(-1), result); |
46 | if (desired_idx != (size_t)(-1)) break; |
47 | } |
48 | ++current_idx; |
49 | } |
50 | } |
51 | } |
52 | |
53 | void run(std::istream& in, size_t desired_idx) |
54 | { |
55 | using boost::property_tree::ptree; |
56 | ptree pt; |
57 | read_xml(stream&: in, pt, flags: boost::property_tree::xml_parser::no_comments | boost::property_tree::xml_parser::trim_whitespace); |
58 | ptree gml = pt.get_child(path: path(str: "graphml" )); |
59 | // Search for attributes |
60 | BOOST_FOREACH(const ptree::value_type& child, gml) { |
61 | if (child.first != "key" ) continue; |
62 | std::string id = child.second.get(path: path(str: "<xmlattr>/id" ), default_value: "" ); |
63 | std::string for_ = child.second.get(path: path(str: "<xmlattr>/for" ), default_value: "" ); |
64 | std::string name = child.second.get(path: path(str: "<xmlattr>/attr.name" ), default_value: "" ); |
65 | std::string type = child.second.get(path: path(str: "<xmlattr>/attr.type" ), default_value: "" ); |
66 | key_kind kind = all_key; |
67 | if (for_ == "graph" ) kind = graph_key; |
68 | else if (for_ == "node" ) kind = node_key; |
69 | else if (for_ == "edge" ) kind = edge_key; |
70 | else if (for_ == "hyperedge" ) kind = hyperedge_key; |
71 | else if (for_ == "port" ) kind = port_key; |
72 | else if (for_ == "endpoint" ) kind = endpoint_key; |
73 | else if (for_ == "all" ) kind = all_key; |
74 | else if (for_ == "graphml" ) kind = graphml_key; |
75 | else {BOOST_THROW_EXCEPTION(parse_error("Attribute for is not valid: " + for_));} |
76 | m_keys[id] = kind; |
77 | m_key_name[id] = name; |
78 | m_key_type[id] = type; |
79 | boost::optional<std::string> default_ = child.second.get_optional<std::string>(path: path(str: "default" )); |
80 | if (default_) m_key_default[id] = default_.get(); |
81 | } |
82 | // Search for graphs |
83 | std::vector<const ptree*> graphs; |
84 | get_graphs(top: gml, desired_idx, result&: graphs); |
85 | BOOST_FOREACH(const ptree* gr, graphs) { |
86 | // Search for nodes |
87 | BOOST_FOREACH(const ptree::value_type& node, *gr) { |
88 | if (node.first != "node" ) continue; |
89 | std::string id = node.second.get<std::string>(path: path(str: "<xmlattr>/id" )); |
90 | handle_vertex(v: id); |
91 | BOOST_FOREACH(const ptree::value_type& attr, node.second) { |
92 | if (attr.first != "data" ) continue; |
93 | std::string key = attr.second.get<std::string>(path: path(str: "<xmlattr>/key" )); |
94 | std::string value = attr.second.get_value(default_value: "" ); |
95 | handle_node_property(key_id: key, descriptor: id, value); |
96 | } |
97 | } |
98 | } |
99 | BOOST_FOREACH(const ptree* gr, graphs) { |
100 | bool default_directed = gr->get<std::string>(path: path(str: "<xmlattr>/edgedefault" )) == "directed" ; |
101 | // Search for edges |
102 | BOOST_FOREACH(const ptree::value_type& edge, *gr) { |
103 | if (edge.first != "edge" ) continue; |
104 | std::string source = edge.second.get<std::string>(path: path(str: "<xmlattr>/source" )); |
105 | std::string target = edge.second.get<std::string>(path: path(str: "<xmlattr>/target" )); |
106 | std::string local_directed = edge.second.get(path: path(str: "<xmlattr>/directed" ), default_value: "" ); |
107 | bool is_directed = (local_directed == "" ? default_directed : local_directed == "true" ); |
108 | if (is_directed != m_g.is_directed()) { |
109 | if (is_directed) { |
110 | BOOST_THROW_EXCEPTION(directed_graph_error()); |
111 | } else { |
112 | BOOST_THROW_EXCEPTION(undirected_graph_error()); |
113 | } |
114 | } |
115 | size_t old_edges_size = m_edge.size(); |
116 | handle_edge(u: source, v: target); |
117 | BOOST_FOREACH(const ptree::value_type& attr, edge.second) { |
118 | if (attr.first != "data" ) continue; |
119 | std::string key = attr.second.get<std::string>(path: path(str: "<xmlattr>/key" )); |
120 | std::string value = attr.second.get_value(default_value: "" ); |
121 | handle_edge_property(key_id: key, descriptor: old_edges_size, value); |
122 | } |
123 | } |
124 | } |
125 | } |
126 | |
127 | private: |
128 | /// The kinds of keys. Not all of these are supported |
129 | enum key_kind { |
130 | graph_key, |
131 | node_key, |
132 | edge_key, |
133 | hyperedge_key, |
134 | port_key, |
135 | endpoint_key, |
136 | all_key, |
137 | graphml_key |
138 | }; |
139 | |
140 | void |
141 | handle_vertex(const std::string& v) |
142 | { |
143 | bool is_new = false; |
144 | |
145 | if (m_vertex.find(x: v) == m_vertex.end()) |
146 | { |
147 | m_vertex[v] = m_g.do_add_vertex(); |
148 | is_new = true; |
149 | } |
150 | |
151 | if (is_new) |
152 | { |
153 | std::map<std::string, std::string>::iterator iter; |
154 | for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter) |
155 | { |
156 | if (m_keys[iter->first] == node_key) |
157 | handle_node_property(key_id: iter->first, descriptor: v, value: iter->second); |
158 | } |
159 | } |
160 | } |
161 | |
162 | any |
163 | get_vertex_descriptor(const std::string& v) |
164 | { |
165 | return m_vertex[v]; |
166 | } |
167 | |
168 | void |
169 | handle_edge(const std::string& u, const std::string& v) |
170 | { |
171 | handle_vertex(v: u); |
172 | handle_vertex(v); |
173 | |
174 | any source, target; |
175 | source = get_vertex_descriptor(v: u); |
176 | target = get_vertex_descriptor(v); |
177 | |
178 | any edge; |
179 | bool added; |
180 | boost::tie(t0&: edge, t1&: added) = m_g.do_add_edge(source, target); |
181 | if (!added) { |
182 | BOOST_THROW_EXCEPTION(bad_parallel_edge(u, v)); |
183 | } |
184 | |
185 | size_t e = m_edge.size(); |
186 | m_edge.push_back(x: edge); |
187 | |
188 | std::map<std::string, std::string>::iterator iter; |
189 | for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter) |
190 | { |
191 | if (m_keys[iter->first] == edge_key) |
192 | handle_edge_property(key_id: iter->first, descriptor: e, value: iter->second); |
193 | } |
194 | } |
195 | |
196 | void handle_node_property(const std::string& key_id, const std::string& descriptor, const std::string& value) |
197 | { |
198 | m_g.set_vertex_property(name: m_key_name[key_id], vertex: m_vertex[descriptor], value, value_type: m_key_type[key_id]); |
199 | } |
200 | |
201 | void handle_edge_property(const std::string& key_id, size_t descriptor, const std::string& value) |
202 | { |
203 | m_g.set_edge_property(name: m_key_name[key_id], edge: m_edge[descriptor], value, value_type: m_key_type[key_id]); |
204 | } |
205 | |
206 | mutate_graph& m_g; |
207 | std::map<std::string, key_kind> m_keys; |
208 | std::map<std::string, std::string> m_key_name; |
209 | std::map<std::string, std::string> m_key_type; |
210 | std::map<std::string, std::string> m_key_default; |
211 | std::map<std::string, any> m_vertex; |
212 | std::vector<any> m_edge; |
213 | }; |
214 | |
215 | } |
216 | |
217 | namespace boost |
218 | { |
219 | void BOOST_GRAPH_DECL |
220 | read_graphml(std::istream& in, mutate_graph& g, size_t desired_idx) |
221 | { |
222 | graphml_reader reader(g); |
223 | reader.run(in, desired_idx); |
224 | } |
225 | } |
226 | |