Subject: [Boost-commit] svn:boost r58035 - trunk/libs/graph/src
From: jewillco_at_[hidden]
Date: 2009-11-29 15:35:25
Author: jewillco
Date: 2009-11-29 15:35:25 EST (Sun, 29 Nov 2009)
New Revision: 58035
URL: http://svn.boost.org/trac/boost/changeset/58035
Log:
Rewrote GraphML parser to use Boost.PropertyTree; fixes #3300
Text files modified:
trunk/libs/graph/src/graphml.cpp | 357 ++++++++++-----------------------------
1 files changed, 97 insertions(+), 260 deletions(-)
Modified: trunk/libs/graph/src/graphml.cpp
==============================================================================
--- trunk/libs/graph/src/graphml.cpp (original)
+++ trunk/libs/graph/src/graphml.cpp 2009-11-29 15:35:25 EST (Sun, 29 Nov 2009)
@@ -1,18 +1,20 @@
// Copyright (C) 2006 Tiago de Paula Peixoto <tiago_at_[hidden]>
-// Copyright (C) 2004 The Trustees of Indiana University.
+// Copyright (C) 2004,2009 The Trustees of Indiana University.
//
// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
// Authors: Douglas Gregor
+// Jeremiah Willcock
// Andrew Lumsdaine
// Tiago de Paula Peixoto
-#include <boost/variant.hpp>
-#include <expat.h>
+#include <boost/foreach.hpp>
+#include <boost/optional.hpp>
#include <boost/graph/graphml.hpp>
-#include <boost/algorithm/string/replace.hpp>
+#include <boost/property_tree/ptree.hpp>
+#include <boost/property_tree/xml_parser.hpp>
using namespace boost;
@@ -20,34 +22,91 @@
{
public:
graphml_reader(mutate_graph& g)
- : m_g(g), m_canonical_vertices(false) { }
+ : m_g(g) { }
+
+ static boost::property_tree::ptree::path_type path(const std::string& str) {
+ return boost::property_tree::ptree::path_type(str, '/');
+ }
+
+ static void get_graphs(const boost::property_tree::ptree& top,
+ std::vector<const boost::property_tree::ptree*>& result) {
+ using boost::property_tree::ptree;
+ BOOST_FOREACH(const ptree::value_type& n, top) {
+ if (n.first == "graph") {
+ result.push_back(&n.second);
+ get_graphs(n.second, result);
+ }
+ }
+ }
void run(std::istream& in)
{
- const int buffer_size = 4096;
- m_parser = XML_ParserCreateNS(0,'|');
- XML_SetElementHandler(m_parser, &on_start_element, &on_end_element);
- XML_SetCharacterDataHandler(m_parser, &on_character_data);
- XML_SetUserData(m_parser, this);
- char buffer[buffer_size];
-
- bool okay = true;
- do
- {
- in.read(buffer, buffer_size);
- okay = XML_Parse(m_parser, buffer, in.gcount(), in.gcount() == 0);
- }
- while (okay && in.good());
-
- if (!okay)
- {
- std::stringstream s;
- s << "on line " << XML_GetCurrentLineNumber(m_parser)
- <<", column " << XML_GetCurrentColumnNumber(m_parser)
- << ": " << XML_ErrorString(XML_GetErrorCode(m_parser));
- throw parse_error(s.str());
+ using boost::property_tree::ptree;
+ ptree pt;
+ read_xml(in, pt, boost::property_tree::xml_parser::no_comments | boost::property_tree::xml_parser::trim_whitespace);
+ ptree gml = pt.get_child(path("graphml"));
+ // Search for attributes
+ BOOST_FOREACH(const ptree::value_type& child, gml) {
+ if (child.first != "key") continue;
+ std::string id = child.second.get(path("<xmlattr>/id"), "");
+ std::string for_ = child.second.get(path("<xmlattr>/for"), "");
+ std::string name = child.second.get(path("<xmlattr>/attr.name"), "");
+ std::string type = child.second.get(path("<xmlattr>/attr.type"), "");
+ key_kind kind = all_key;
+ if (for_ == "graph") kind = graph_key;
+ else if (for_ == "node") kind = node_key;
+ else if (for_ == "edge") kind = edge_key;
+ else if (for_ == "hyperedge") kind = hyperedge_key;
+ else if (for_ == "port") kind = port_key;
+ else if (for_ == "endpoint") kind = endpoint_key;
+ else if (for_ == "all") kind = all_key;
+ else throw parse_error("Attribute for is not valid: " + for_);
+ m_keys[id] = kind;
+ m_key_name[id] = name;
+ m_key_type[id] = type;
+ boost::optional<std::string> default_ = child.second.get_optional<std::string>(path("default"));
+ if (default_) m_key_default[id] = default_.get();
+ }
+ // Search for graphs
+ std::vector<const ptree*> graphs;
+ get_graphs(gml, graphs);
+ BOOST_FOREACH(const ptree* gr, graphs) {
+ // Search for nodes
+ BOOST_FOREACH(const ptree::value_type& node, *gr) {
+ if (node.first != "node") continue;
+ std::string id = node.second.get<std::string>(path("<xmlattr>/id"));
+ handle_vertex(id);
+ BOOST_FOREACH(const ptree::value_type& attr, node.second) {
+ if (attr.first != "data") continue;
+ std::string key = attr.second.get<std::string>(path("<xmlattr>/key"));
+ std::string value = attr.second.get_value("");
+ handle_node_property(key, id, value);
+ }
+ }
+ }
+ BOOST_FOREACH(const ptree* gr, graphs) {
+ bool default_directed = gr->get<std::string>(path("<xmlattr>/edgedefault")) == "directed";
+ // Search for edges
+ BOOST_FOREACH(const ptree::value_type& edge, *gr) {
+ if (edge.first != "edge") continue;
+ std::string id = edge.second.get<std::string>(path("<xmlattr>/id"));
+ std::string source = edge.second.get<std::string>(path("<xmlattr>/source"));
+ std::string target = edge.second.get<std::string>(path("<xmlattr>/target"));
+ std::string local_directed = edge.second.get(path("<xmlattr>/directed"), "");
+ bool is_directed = (local_directed == "" ? default_directed : local_directed == "true");
+ if (is_directed != m_g.is_directed()) {
+ if (is_directed) throw directed_graph_error(); else throw undirected_graph_error();
+ }
+ size_t old_edges_size = m_edge.size();
+ handle_edge(source, target);
+ BOOST_FOREACH(const ptree::value_type& attr, edge.second) {
+ if (attr.first != "data") continue;
+ std::string key = attr.second.get<std::string>(path("<xmlattr>/key"));
+ std::string value = attr.second.get_value("");
+ handle_edge_property(key, old_edges_size, value);
+ }
}
- XML_ParserFree(m_parser);
+ }
}
private:
@@ -62,199 +121,15 @@
all_key
};
- static void
- on_start_element(void* user_data, const XML_Char *c_name,
- const XML_Char **atts)
- {
- graphml_reader* self = static_cast<graphml_reader*>(user_data);
-
- std::string name(c_name);
- replace_first(name, "http://graphml.graphdrawing.org/xmlns|", "");
-
- if (name == "edge")
- {
- std::string id;
- std::string source, target;
- while (*atts)
- {
- std::string name = *atts++;
- std::string value = *atts++;
-
- if (name == "id") id = value;
- else if (name == "source") source = value;
- else if (name == "target") target = value;
- else if (name == "directed")
- {
- bool edge_is_directed = (value == "directed");
- if (edge_is_directed != self->m_g.is_directed())
- {
- if (edge_is_directed)
- throw directed_graph_error();
- else
- throw undirected_graph_error();
- }
- }
- }
-
- self->m_active_descriptor = self->m_edge.size();
- self->handle_edge(source, target);
- }
- else if (name == "node")
- {
- std::string id;
-
- while (*atts)
- {
- std::string name = *atts++;
- std::string value = *atts++;
-
- if (name == "id") id = value;
- }
-
- self->handle_vertex(id);
- self->m_active_descriptor = id;
- }
- else if (name == "data")
- {
- while (*atts)
- {
- std::string name = *atts++;
- std::string value = *atts++;
-
- if (name == "key") self->m_active_key = value;
- }
- }
- else if (name == "key")
- {
- std::string id;
- std::string key_name;
- std::string key_type;
- key_kind kind = all_key;
-
- while (*atts)
- {
- std::string name = *atts++;
- std::string value = *atts++;
-
- if (name == "id") id = value;
- else if (name == "attr.name") key_name = value;
- else if (name == "attr.type") key_type = value;
- else if (name == "for")
- {
- if (value == "graph") kind = graph_key;
- else if (value == "node") kind = node_key;
- else if (value == "edge") kind = edge_key;
- else if (value == "hyperedge") kind = hyperedge_key;
- else if (value == "port") kind = port_key;
- else if (value == "endpoint") kind = endpoint_key;
- else if (value == "all") kind = all_key;
- else
- {
- std::stringstream s;
- s << "on line " << XML_GetCurrentLineNumber(self->m_parser)
- << ", column " << XML_GetCurrentColumnNumber(self->m_parser)
- << ": unrecognized key kind '" << value << "'";
- throw parse_error(s.str());
- }
- }
- }
-
- self->m_keys[id] = kind;
- self->m_key_name[id] = key_name;
- self->m_key_type[id] = key_type;
- self->m_active_key = id;
- }
- else if (name == "graph")
- {
- while (*atts)
- {
- std::string name = *atts++;
- std::string value = *atts++;
-
- if (name == "edgedefault")
- {
- bool edge_is_directed = (value == "directed");
- if (edge_is_directed != self->m_g.is_directed())
- {
- if (edge_is_directed)
- throw directed_graph_error();
- else
- throw undirected_graph_error();
- }
- }
- else if (name == "parse.nodeids")
- {
- self->m_canonical_vertices = (value == "canonical");
- }
- }
- self->m_active_descriptor = "";
- }
-
- self->m_character_data.clear();
- }
-
- static void
- on_end_element(void* user_data, const XML_Char *c_name)
- {
- graphml_reader* self = static_cast<graphml_reader*>(user_data);
-
- std::string name(c_name);
- replace_first(name, "http://graphml.graphdrawing.org/xmlns|", "");
-
- if (name == "data")
- {
- self->handle_property(self->m_active_key, self->m_active_descriptor,
- self->m_character_data);
- }
- else if (name == "default")
- {
- self->m_key_default[self->m_active_key] = self->m_character_data;
- }
- }
-
- static void
- on_character_data(void* user_data, const XML_Char* s, int len)
- {
- graphml_reader* self = static_cast<graphml_reader*>(user_data);
- self->m_character_data.append(s, len);
- }
-
void
handle_vertex(const std::string& v)
{
bool is_new = false;
- if (m_canonical_vertices)
- {
- size_t id;
-
- //strip leading "n" from name
- try
- {
- id = lexical_cast<size_t>(std::string(v,1));
- }
- catch (bad_lexical_cast)
- {
- std::stringstream s;
- s << "on line " << XML_GetCurrentLineNumber(m_parser)
- << ", column " << XML_GetCurrentColumnNumber(m_parser)
- << ": invalid vertex: " << v;
- throw parse_error(s.str());
- }
-
- while(id >= m_canonical_vertex.size())
- {
- m_canonical_vertex.push_back(m_g.do_add_vertex());
- is_new = true;
- }
- }
- else
+ if (m_vertex.find(v) == m_vertex.end())
{
- if (m_vertex.find(v) == m_vertex.end())
- {
- m_vertex[v] = m_g.do_add_vertex();
- is_new = true;
- }
+ m_vertex[v] = m_g.do_add_vertex();
+ is_new = true;
}
if (is_new)
@@ -263,7 +138,7 @@
for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter)
{
if (m_keys[iter->first] == node_key)
- handle_property(iter->first, v, iter->second);
+ handle_node_property(iter->first, v, iter->second);
}
}
}
@@ -271,16 +146,7 @@
any
get_vertex_descriptor(const std::string& v)
{
- if (m_canonical_vertices)
- {
- //strip leading "n" from name
- size_t id = lexical_cast<size_t>(std::string(v,1));
- return m_canonical_vertex[id];
- }
- else
- {
- return m_vertex[v];
- }
+ return m_vertex[v];
}
void
@@ -306,40 +172,18 @@
for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter)
{
if (m_keys[iter->first] == edge_key)
- handle_property(iter->first, e, iter->second);
+ handle_edge_property(iter->first, e, iter->second);
}
}
- void handle_property(const std::string& key_id, const variant<std::string,size_t>& descriptor, const std::string& value)
+ void handle_node_property(const std::string& key_id, const std::string& descriptor, const std::string& value)
{
- try
- {
- if (get<std::string>(&descriptor))
- {
- if (get<std::string>(descriptor) == "")
- m_g.set_graph_property(m_key_name[key_id], value, m_key_type[key_id]);
- else
- m_g.set_vertex_property(m_key_name[key_id], get_vertex_descriptor(get<std::string>(descriptor)), value, m_key_type[key_id]);
- }
- else
- {
- m_g.set_edge_property(m_key_name[key_id], get_edge_descriptor(get<size_t>(descriptor)), value, m_key_type[key_id]);
- }
- }
- catch (parse_error &e)
- {
- std::stringstream s;
- s << "on line " << XML_GetCurrentLineNumber(m_parser)
- << ", column " << XML_GetCurrentColumnNumber(m_parser)
- << ": " << e.error;
- throw parse_error(s.str());
- }
+ m_g.set_vertex_property(m_key_name[key_id], m_vertex[descriptor], value, m_key_type[key_id]);
}
- any
- get_edge_descriptor(size_t e)
+ void handle_edge_property(const std::string& key_id, size_t descriptor, const std::string& value)
{
- return m_edge[e];
+ m_g.set_edge_property(m_key_name[key_id], m_edge[descriptor], value, m_key_type[key_id]);
}
mutate_graph& m_g;
@@ -348,14 +192,7 @@
std::map<std::string, std::string> m_key_type;
std::map<std::string, std::string> m_key_default;
std::map<std::string, any> m_vertex;
- std::vector<any> m_canonical_vertex;
std::vector<any> m_edge;
- variant<std::string, size_t> m_active_descriptor;
- std::string m_active_key;
- std::string m_character_data;
- bool m_canonical_vertices;
- bool m_canonical_edges;
- XML_Parser m_parser;
};
namespace boost