graph/src/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/graphml.hpp>
#include <boost/graph/dll_import_export.hpp>
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/xml_parser.hpp>

using namespace boost;

namespace {

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"));
      // 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 == "" ? default_directed : local_directed == "true");
          if (is_directed != m_g.is_directed()) {
            if (is_directed) {
              BOOST_THROW_EXCEPTION(directed_graph_error());
            } else {
              BOOST_THROW_EXCEPTION(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();
            is_new = true;
        }

        if (is_new)
        {
            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);
            }
        }
    }

    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);

        any source, target;
        source = get_vertex_descriptor(u);
        target = get_vertex_descriptor(v);

        any edge;
        bool added;
        boost::tie(edge, added) = m_g.do_add_edge(source, target);
        if (!added) {
            BOOST_THROW_EXCEPTION(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, any> m_vertex;
    std::vector<any> m_edge;
};

}

namespace boost
{
void BOOST_GRAPH_DECL
read_graphml(std::istream& in, mutate_graph& g, size_t desired_idx)
{
    graphml_reader reader(g);
    reader.run(in, desired_idx);
}
}