libs/graph/src/graphml.cpp

   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(&n.second);
  45             get_graphs(n.second, (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(in, pt, boost::property_tree::xml_parser::no_comments | boost::property_tree::xml_parser::trim_whitespace);
  58       ptree gml = pt.get_child(path("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("<xmlattr>/id"), "");
  63         std::string for_ = child.second.get(path("<xmlattr>/for"), "");
  64         std::string name = child.second.get(path("<xmlattr>/attr.name"), "");
  65         std::string type = child.second.get(path("<xmlattr>/attr.type"), "");
  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("default"));
  80         if (default_) m_key_default[id] = default_.get();
  81       }
  82       // Search for graphs
  83       std::vector<const ptree*> graphs;
  84       get_graphs(gml, desired_idx, 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("<xmlattr>/id"));
  90           handle_vertex(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("<xmlattr>/key"));
  94             std::string value = attr.second.get_value("");
  95             handle_node_property(key, id, value);
  96           }
  97         }
  98       }
  99       BOOST_FOREACH(const ptree* gr, graphs) {
 100         bool default_directed = gr->get<std::string>(path("<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("<xmlattr>/source"));
 105           std::string target = edge.second.get<std::string>(path("<xmlattr>/target"));
 106           std::string local_directed = edge.second.get(path("<xmlattr>/directed"), "");
 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(source, 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("<xmlattr>/key"));
 120             std::string value = attr.second.get_value("");
 121             handle_edge_property(key, 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(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(iter->first, v, 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(u);
 172         handle_vertex(v);
 173
 174         any source, target;
 175         source = get_vertex_descriptor(u);
 176         target = get_vertex_descriptor(v);
 177
 178         any edge;
 179         bool added;
 180         boost::tie(edge, 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(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(iter->first, e, 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(m_key_name[key_id], m_vertex[descriptor], value, 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(m_key_name[key_id], m_edge[descriptor], value, 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 }