graphml.cpp
// Copyright (C) 2006 Tiago de Paula Peixoto <tiago@forked.de>
// 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
#define BOOST_GRAPH_SOURCE
#include <boost/foreach.hpp>
#include <boost/optional.hpp>
#include <boost/throw_exception.hpp>
#include <boost/graph/dll_import_export.hpp>
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/xml_parser.hpp>
#include <map>
#include <string>
#include <vector>
#include "graphml/graphml.hpp"
namespace
{
using namespace pds;
class graphml_reader
{
public:
graphml_reader(mutate_graph& g) : m_g(g) {}
static boost::property_tree::ptree::path_type path(const std::string& str)
{
return boost::property_tree::ptree::path_type(str, '/');
}
void get_graphs(const boost::property_tree::ptree& top,
size_t desired_idx /* or -1 for all */, bool is_root,
std::vector< const boost::property_tree::ptree* >& result)
{
using boost::property_tree::ptree;
size_t current_idx = 0;
bool is_first = is_root;
BOOST_FOREACH (const ptree::value_type& n, top)
{
if (n.first == "graph")
{
if (current_idx == desired_idx || desired_idx == (size_t)(-1))
{
result.push_back(&n.second);
if (is_first)
{
is_first = false;
BOOST_FOREACH (const ptree::value_type& attr, n.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_graph_property(key, value);
}
}
get_graphs(n.second, (size_t)(-1), false, result);
if (desired_idx != (size_t)(-1))
break;
}
++current_idx;
}
}
}
void run(std::istream& in, size_t desired_idx)
{
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"));
m_keys["name"] = node_key;
m_key_type["name"] = "string";
m_key_name["name"] = "name";
m_keys["id"] = node_key;
m_key_type["id"] = "long";
m_key_name["id"] = "id";
// 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 if (for_ == "graphml")
kind = graphml_key;
else
{
BOOST_THROW_EXCEPTION(
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;
handle_graph();
get_graphs(gml, desired_idx, true, 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 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.empty() ? default_directed
: local_directed == "true");
if (is_directed != m_g.is_directed())
{
if (is_directed)
{
BOOST_THROW_EXCEPTION(boost::directed_graph_error());
}
else
{
BOOST_THROW_EXCEPTION(boost::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);
}
}
}
}
private:
/// The kinds of keys. Not all of these are supported
enum key_kind
{
graph_key,
node_key,
edge_key,
hyperedge_key,
port_key,
endpoint_key,
all_key,
graphml_key
};
void handle_vertex(const std::string& v)
{
bool is_new = false;
if (m_vertex.find(v) == m_vertex.end())
{
m_vertex[v] = m_g.do_add_vertex();
m_vertex_index.emplace(v, m_vertex_index.size());
is_new = true;
}
if (is_new)
{
handle_node_property("name", v, v);
handle_node_property("id", v, std::to_string(m_vertex_index[v]));
std::map< std::string, std::string >::iterator iter;
for (iter = m_key_default.begin(); iter != m_key_default.end();
++iter)
{
if (m_keys[iter->first] == node_key)
handle_node_property(iter->first, v, iter->second);
}
}
}
boost::any get_vertex_descriptor(const std::string& v) { return m_vertex[v]; }
void handle_edge(const std::string& u, const std::string& v)
{
handle_vertex(u);
handle_vertex(v);
boost::any source, target;
source = get_vertex_descriptor(u);
target = get_vertex_descriptor(v);
boost::any edge;
bool added;
boost::tie(edge, added) = m_g.do_add_edge(source, target);
if (!added)
{
BOOST_THROW_EXCEPTION(boost::bad_parallel_edge(u, v));
}
size_t e = m_edge.size();
m_edge.push_back(edge);
std::map< std::string, std::string >::iterator iter;
for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter)
{
if (m_keys[iter->first] == edge_key)
handle_edge_property(iter->first, e, iter->second);
}
}
void handle_graph()
{
std::map< std::string, std::string >::iterator iter;
for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter)
{
if (m_keys[iter->first] == graph_key)
handle_graph_property(iter->first, iter->second);
}
}
void handle_graph_property(
const std::string& key_id, const std::string& value)
{
m_g.set_graph_property(m_key_name[key_id], value, m_key_type[key_id]);
}
void handle_node_property(const std::string& key_id,
const std::string& descriptor, const std::string& value)
{
m_g.set_vertex_property(m_key_name[key_id], m_vertex[descriptor], value,
m_key_type[key_id]);
}
void handle_edge_property(
const std::string& key_id, size_t descriptor, const std::string& value)
{
m_g.set_edge_property(
m_key_name[key_id], m_edge[descriptor], value, m_key_type[key_id]);
}
mutate_graph& m_g;
std::map<std::string, key_kind > m_keys;
std::map<std::string, std::string > m_key_name;
std::map<std::string, std::string > m_key_type;
std::map<std::string, std::string > m_key_default;
std::map<std::string, boost::any > m_vertex;
std::map<std::string, size_t> m_vertex_index;
std::vector< boost::any > m_edge;
};
}
namespace pds {
void read_graphml(
std::istream& in, mutate_graph& g, size_t desired_idx)
{
graphml_reader reader(g);
reader.run(in, desired_idx);
}
}
