text: // 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;
  
  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, '/');
      }
  
      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)
      {
        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 {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;
        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) {
                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
      };
  
      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_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)
  {    
      graphml_reader reader(g);
      reader.run(in);
  }
  }
  