Chris@16: // Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
Chris@16: // Copyright (C) 2004  The Trustees of Indiana University.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: //  Authors: Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: //           Tiago de Paula Peixoto
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_GRAPHML_HPP
Chris@16: #define BOOST_GRAPH_GRAPHML_HPP
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/lexical_cast.hpp>
Chris@16: #include <boost/any.hpp>
Chris@16: #include <boost/type_traits/is_convertible.hpp>
Chris@16: #include <boost/graph/dll_import_export.hpp>
Chris@16: #include <boost/graph/graphviz.hpp> // for exceptions
Chris@16: #include <typeinfo>
Chris@16: #include <boost/mpl/bool.hpp>
Chris@16: #include <boost/mpl/vector.hpp>
Chris@16: #include <boost/mpl/find.hpp>
Chris@16: #include <boost/mpl/for_each.hpp>
Chris@16: #include <boost/property_tree/detail/xml_parser_utils.hpp>
Chris@16: #include <boost/throw_exception.hpp>
Chris@16: #include <exception>
Chris@16: #include <sstream>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16: 
Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: // Graph reader exceptions
Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: struct parse_error: public graph_exception
Chris@16: {
Chris@16:     parse_error(const std::string& err) {error = err; statement = "parse error: " + error;}
Chris@16:     virtual ~parse_error() throw() {}
Chris@16:     virtual const char* what() const throw() {return statement.c_str();}
Chris@16:     std::string statement;
Chris@16:     std::string error;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: class mutate_graph
Chris@16: {
Chris@16: public:
Chris@16:     virtual ~mutate_graph() {}
Chris@16:     virtual bool is_directed() const = 0;
Chris@16: 
Chris@16:     virtual boost::any do_add_vertex() = 0;
Chris@16:     virtual std::pair<boost::any,bool> do_add_edge(boost::any source, boost::any target) = 0;
Chris@16: 
Chris@16:     virtual void
Chris@16:     set_graph_property(const std::string& name, const std::string& value, const std::string& value_type) = 0;
Chris@16: 
Chris@16:     virtual void
Chris@16:     set_vertex_property(const std::string& name, boost::any vertex, const std::string& value, const std::string& value_type) = 0;
Chris@16: 
Chris@16:     virtual void
Chris@16:     set_edge_property(const std::string& name, boost::any edge, const std::string& value, const std::string& value_type) = 0;
Chris@16: };
Chris@16: 
Chris@16: template<typename MutableGraph>
Chris@16: class mutate_graph_impl : public mutate_graph
Chris@16: {
Chris@16:     typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_descriptor;
Chris@16:     typedef typename graph_traits<MutableGraph>::edge_descriptor edge_descriptor;
Chris@16: 
Chris@16:  public:
Chris@16:     mutate_graph_impl(MutableGraph& g, dynamic_properties& dp)
Chris@16:         : m_g(g), m_dp(dp) { }
Chris@16: 
Chris@16:     bool is_directed() const
Chris@16:     {
Chris@16:         return is_convertible<typename graph_traits<MutableGraph>::directed_category,
Chris@16:                               directed_tag>::value;
Chris@16:     }
Chris@16: 
Chris@16:     virtual any do_add_vertex()
Chris@16:     {
Chris@16:         return any(add_vertex(m_g));
Chris@16:     }
Chris@16: 
Chris@16:     virtual std::pair<any,bool> do_add_edge(any source, any target)
Chris@16:     {
Chris@16:         std::pair<edge_descriptor,bool> retval = add_edge(any_cast<vertex_descriptor>(source),
Chris@16:                                                           any_cast<vertex_descriptor>(target), m_g);
Chris@16:         return std::make_pair(any(retval.first), retval.second);
Chris@16:     }
Chris@16: 
Chris@16:     virtual void
Chris@16:     set_graph_property(const std::string& name, const std::string& value, const std::string& value_type)
Chris@16:     {
Chris@16:         bool type_found = false;
Chris@16:         try
Chris@16:         {
Chris@16:             mpl::for_each<value_types>(put_property<MutableGraph,value_types>
Chris@16:                                        (name, m_dp, m_g, value, value_type, m_type_names, type_found));
Chris@16:         }
Chris@16:         catch (bad_lexical_cast)
Chris@16:         {
Chris@16:             BOOST_THROW_EXCEPTION(
Chris@16:               parse_error("invalid value \"" + value + "\" for key " +
Chris@16:                           name + " of type " + value_type));
Chris@16:         }
Chris@16:         if (!type_found)
Chris@16:         {
Chris@16:             BOOST_THROW_EXCEPTION(
Chris@16:               parse_error("unrecognized type \"" + value_type +
Chris@16:                           "\" for key " + name));
Chris@16:         }
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16:     virtual void
Chris@16:     set_vertex_property(const std::string& name, any vertex, const std::string& value, const std::string& value_type)
Chris@16:     {
Chris@16:         bool type_found = false;
Chris@16:         try
Chris@16:         {
Chris@16:             mpl::for_each<value_types>(put_property<vertex_descriptor,value_types>
Chris@16:                                        (name, m_dp, any_cast<vertex_descriptor>(vertex),
Chris@16:                                         value, value_type, m_type_names, type_found));
Chris@16:         }
Chris@16:         catch (bad_lexical_cast)
Chris@16:         {
Chris@16:             BOOST_THROW_EXCEPTION(
Chris@16:               parse_error("invalid value \"" + value + "\" for key " +
Chris@16:                           name + " of type " + value_type));
Chris@16:         }
Chris@16:         if (!type_found)
Chris@16:         {
Chris@16:             BOOST_THROW_EXCEPTION(
Chris@16:               parse_error("unrecognized type \"" + value_type +
Chris@16:                           "\" for key " + name));
Chris@16:         }
Chris@16: 
Chris@16:     }
Chris@16: 
Chris@16:     virtual void
Chris@16:     set_edge_property(const std::string& name, any edge, const std::string& value, const std::string& value_type)
Chris@16:     {
Chris@16:         bool type_found = false;
Chris@16:         try
Chris@16:         {
Chris@16:             mpl::for_each<value_types>(put_property<edge_descriptor,value_types>
Chris@16:                                        (name, m_dp, any_cast<edge_descriptor>(edge),
Chris@16:                                         value, value_type, m_type_names, type_found));
Chris@16:         }
Chris@16:         catch (bad_lexical_cast)
Chris@16:         {
Chris@16:             BOOST_THROW_EXCEPTION(
Chris@16:               parse_error("invalid value \"" + value + "\" for key " +
Chris@16:                           name + " of type " + value_type));
Chris@16:         }
Chris@16:         if (!type_found)
Chris@16:         {
Chris@16:             BOOST_THROW_EXCEPTION(
Chris@16:               parse_error("unrecognized type \"" + value_type +
Chris@16:                           "\" for key " + name));
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Key, typename ValueVector>
Chris@16:     class put_property
Chris@16:     {
Chris@16:     public:
Chris@16:         put_property(const std::string& name, dynamic_properties& dp, const Key& key,
Chris@16:                      const std::string& value, const std::string& value_type,
Chris@16:                      const char** type_names, bool& type_found)
Chris@16:             : m_name(name), m_dp(dp), m_key(key), m_value(value),
Chris@16:               m_value_type(value_type), m_type_names(type_names),
Chris@16:               m_type_found(type_found) {}
Chris@16:         template <class Value>
Chris@16:         void operator()(Value)
Chris@16:         {
Chris@16:             if (m_value_type == m_type_names[mpl::find<ValueVector,Value>::type::pos::value])
Chris@16:             {
Chris@16:                 put(m_name, m_dp, m_key, lexical_cast<Value>(m_value));
Chris@16:                 m_type_found = true;
Chris@16:             }
Chris@16:         }
Chris@16:     private:
Chris@16:         const std::string& m_name;
Chris@16:         dynamic_properties& m_dp;
Chris@16:         const Key& m_key;
Chris@16:         const std::string& m_value;
Chris@16:         const std::string& m_value_type;
Chris@16:         const char** m_type_names;
Chris@16:         bool& m_type_found;
Chris@16:     };
Chris@16: 
Chris@16: protected:
Chris@16:     MutableGraph& m_g;
Chris@16:     dynamic_properties& m_dp;
Chris@16:     typedef mpl::vector<bool, int, long, float, double, std::string> value_types;
Chris@16:     static const char* m_type_names[];
Chris@16: };
Chris@16: 
Chris@16: template<typename MutableGraph>
Chris@16: const char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean", "int", "long", "float", "double", "string"};
Chris@16: 
Chris@16: void BOOST_GRAPH_DECL
Chris@16: read_graphml(std::istream& in, mutate_graph& g, size_t desired_idx);
Chris@16: 
Chris@16: template<typename MutableGraph>
Chris@16: void
Chris@16: read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp, size_t desired_idx = 0)
Chris@16: {
Chris@16:     mutate_graph_impl<MutableGraph> mg(g,dp);
Chris@16:     read_graphml(in, mg, desired_idx);
Chris@16: }
Chris@16: 
Chris@16: template <typename Types>
Chris@16: class get_type_name
Chris@16: {
Chris@16: public:
Chris@16:     get_type_name(const std::type_info& type, const char** type_names, std::string& type_name)
Chris@16:         : m_type(type), m_type_names(type_names), m_type_name(type_name) {}
Chris@16:     template <typename Type>
Chris@16:     void operator()(Type)
Chris@16:     {
Chris@16:         if (typeid(Type) == m_type)
Chris@16:             m_type_name = m_type_names[mpl::find<Types,Type>::type::pos::value];
Chris@16:     }
Chris@16: private:
Chris@16:     const std::type_info &m_type;
Chris@16:     const char** m_type_names;
Chris@16:     std::string &m_type_name;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph, typename VertexIndexMap>
Chris@16: void
Chris@16: write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index,
Chris@16:               const dynamic_properties& dp, bool ordered_vertices=false)
Chris@16: {
Chris@16:     typedef typename graph_traits<Graph>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Chris@16:     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:     using boost::property_tree::xml_parser::encode_char_entities;
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(bool,
Chris@16:                           graph_is_directed =
Chris@16:                           (is_convertible<directed_category*, directed_tag*>::value));
Chris@16: 
Chris@16:     out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"
Chris@16:         << "<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns\" xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd\">\n";
Chris@16: 
Chris@16:     typedef mpl::vector<bool, short, unsigned short, int, unsigned int, long, unsigned long, long long, unsigned long long, float, double, long double, std::string> value_types;
Chris@16:     const char* type_names[] = {"boolean", "int", "int", "int", "int", "long", "long", "long", "long", "float", "double", "double", "string"};
Chris@16:     std::map<std::string, std::string> graph_key_ids;
Chris@16:     std::map<std::string, std::string> vertex_key_ids;
Chris@16:     std::map<std::string, std::string> edge_key_ids;
Chris@16:     int key_count = 0;
Chris@16: 
Chris@16:     // Output keys
Chris@16:     for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
Chris@16:     {
Chris@16:         std::string key_id = "key" + lexical_cast<std::string>(key_count++);
Chris@16:         if (i->second->key() == typeid(Graph*))
Chris@16:             graph_key_ids[i->first] = key_id;
Chris@16:         else if (i->second->key() == typeid(vertex_descriptor))
Chris@16:             vertex_key_ids[i->first] = key_id;
Chris@16:         else if (i->second->key() == typeid(edge_descriptor))
Chris@16:             edge_key_ids[i->first] = key_id;
Chris@16:         else
Chris@16:             continue;
Chris@16:         std::string type_name = "string";
Chris@16:         mpl::for_each<value_types>(get_type_name<value_types>(i->second->value(), type_names, type_name));
Chris@16:         out << "  <key id=\"" << encode_char_entities(key_id) << "\" for=\""
Chris@16:             << (i->second->key() == typeid(Graph*) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\""
Chris@16:             << " attr.name=\"" << i->first << "\""
Chris@16:             << " attr.type=\"" << type_name << "\""
Chris@16:             << " />\n";
Chris@16:     }
Chris@16: 
Chris@16:     out << "  <graph id=\"G\" edgedefault=\""
Chris@16:         << (graph_is_directed ? "directed" : "undirected") << "\""
Chris@16:         << " parse.nodeids=\"" << (ordered_vertices ? "canonical" : "free") << "\""
Chris@16:         << " parse.edgeids=\"canonical\" parse.order=\"nodesfirst\">\n";
Chris@16: 
Chris@16:     // Output graph data
Chris@16:     for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
Chris@16:     {
Chris@16:         if (i->second->key() == typeid(Graph*))
Chris@16:         {
Chris@16:             // The const_cast here is just to get typeid correct for property
Chris@16:             // map key; the graph should not be mutated using it.
Chris@16:             out << "   <data key=\"" << graph_key_ids[i->first] << "\">"
Chris@16:                 << encode_char_entities(i->second->get_string(const_cast<Graph*>(&g))) << "</data>\n";
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
Chris@16:     vertex_iterator v, v_end;
Chris@16:     for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
Chris@16:     {
Chris@16:         out << "    <node id=\"n" << get(vertex_index, *v) << "\">\n";
Chris@16:         // Output data
Chris@16:         for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
Chris@16:         {
Chris@16:             if (i->second->key() == typeid(vertex_descriptor))
Chris@16:             {
Chris@16:                 out << "      <data key=\"" << vertex_key_ids[i->first] << "\">"
Chris@16:                     << encode_char_entities(i->second->get_string(*v)) << "</data>\n";
Chris@16:             }
Chris@16:         }
Chris@16:         out << "    </node>\n";
Chris@16:     }
Chris@16: 
Chris@16:     typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
Chris@16:     edge_iterator e, e_end;
Chris@16:     typename graph_traits<Graph>::edges_size_type edge_count = 0;
Chris@16:     for (boost::tie(e, e_end) = edges(g); e != e_end; ++e)
Chris@16:     {
Chris@16:         out << "    <edge id=\"e" << edge_count++ << "\" source=\"n"
Chris@16:             << get(vertex_index, source(*e, g)) << "\" target=\"n"
Chris@16:             << get(vertex_index, target(*e, g)) << "\">\n";
Chris@16: 
Chris@16:         // Output data
Chris@16:         for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
Chris@16:         {
Chris@16:             if (i->second->key() == typeid(edge_descriptor))
Chris@16:             {
Chris@16:                 out << "      <data key=\"" << edge_key_ids[i->first] << "\">"
Chris@16:                     << encode_char_entities(i->second->get_string(*e)) << "</data>\n";
Chris@16:             }
Chris@16:         }
Chris@16:         out << "    </edge>\n";
Chris@16:     }
Chris@16: 
Chris@16:     out << "  </graph>\n"
Chris@16:         << "</graphml>\n";
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template <typename Graph>
Chris@16: void
Chris@16: write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp,
Chris@16:               bool ordered_vertices=false)
Chris@16: {
Chris@16:     write_graphml(out, g, get(vertex_index, g), dp, ordered_vertices);
Chris@16: }
Chris@16: 
Chris@16: } // boost namespace
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_GRAPHML_HPP