graphml.hpp 12.2 KB
Newer Older
1
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
2
// Copyright (C) 2004  The Trustees of Indiana University.
3
//
4
5
6
// 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)
7
8
9
10
11
//
//  Authors: Douglas Gregor
//           Andrew Lumsdaine
//           Tiago de Paula Peixoto

12
13
#ifndef BOOST_GRAPH_GRAPHML_HPP
#define BOOST_GRAPH_GRAPHML_HPP
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <boost/config.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/any.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/graph/graphviz.hpp> // for exceptions
#include <typeinfo>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/find.hpp>
#include <boost/mpl/for_each.hpp>
#include <exception>
#include <sstream>

namespace boost 
{

/////////////////////////////////////////////////////////////////////////////
// Graph reader exceptions
/////////////////////////////////////////////////////////////////////////////
struct parse_error: public graph_exception 
{
36
    parse_error(const std::string& err) {error = err; statement = "parse error: " + error;}        
37
38
39
    virtual ~parse_error() throw() {}
    virtual const char* what() const throw() {return statement.c_str();}
    std::string statement;
40
    std::string error;
41
42
43
44
45
46
47
48
49
50
51
52
};


class mutate_graph
{
public:
    virtual ~mutate_graph() {}
    virtual bool is_directed() const = 0;

    virtual boost::any do_add_vertex() = 0;
    virtual std::pair<boost::any,bool> do_add_edge(boost::any source, boost::any target) = 0;
    
53
54
55
    virtual void 
    set_graph_property(const std::string& name, const std::string& value, const std::string& value_type) = 0;

56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
    virtual void 
    set_vertex_property(const std::string& name, boost::any vertex, const std::string& value, const std::string& value_type) = 0;
    
    virtual void 
    set_edge_property(const std::string& name, boost::any edge, const std::string& value, const std::string& value_type) = 0;
};

template<typename MutableGraph>
class mutate_graph_impl : public mutate_graph
{
    typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex_descriptor;
    typedef typename graph_traits<MutableGraph>::edge_descriptor edge_descriptor;

 public:
    mutate_graph_impl(MutableGraph& g, dynamic_properties& dp)
71
        : m_g(g), m_dp(dp) { }
72
73
74

    bool is_directed() const
    {
75
76
        return is_convertible<typename graph_traits<MutableGraph>::directed_category,
                              directed_tag>::value;
77
78
79
80
    }

    virtual any do_add_vertex()
    {
81
        return any(add_vertex(m_g));
82
83
84
85
    }

    virtual std::pair<any,bool> do_add_edge(any source, any target)
    {
86
        std::pair<edge_descriptor,bool> retval = add_edge(any_cast<vertex_descriptor>(source),
87
                                                          any_cast<vertex_descriptor>(target), m_g);
88
        return std::make_pair(any(retval.first), retval.second);
89
    }
90
91
92
93

    virtual void 
    set_graph_property(const std::string& name, const std::string& value, const std::string& value_type)
    {
94
95
96
        bool type_found = false;
        try
        {
97
98
            mpl::for_each<value_types>(put_property<graph_property_tag,value_types>
                                       (name, m_dp, graph_property_tag(), value, value_type, m_type_names, type_found));            
99
100
101
102
        }
        catch (bad_lexical_cast)
        {
            throw parse_error("invalid value \"" + value + "\" for key " + 
103
                              name + " of type " + value_type);
104
105
106
        }
        if (!type_found)
            throw  parse_error("unrecognized type \"" + value_type + 
107
                               "\" for key " + name);
108
            
109
    }
110
111
112
113
    
    virtual void 
    set_vertex_property(const std::string& name, any vertex, const std::string& value, const std::string& value_type)
    {
114
115
116
117
        bool type_found = false;
        try
        {
            mpl::for_each<value_types>(put_property<vertex_descriptor,value_types>
118
119
                                       (name, m_dp, any_cast<vertex_descriptor>(vertex),
                                        value, value_type, m_type_names, type_found));            
120
121
122
123
        }
        catch (bad_lexical_cast)
        {
            throw parse_error("invalid value \"" + value + "\" for key " + 
124
                              name + " of type " + value_type);
125
126
127
        }
        if (!type_found)
            throw  parse_error("unrecognized type \"" + value_type + 
128
                               "\" for key " + name);
129
            
130
131
132
133
134
    }
    
    virtual void 
    set_edge_property(const std::string& name, any edge, const std::string& value, const std::string& value_type)
    {
135
136
137
138
        bool type_found = false;
        try
        {
            mpl::for_each<value_types>(put_property<edge_descriptor,value_types>
139
140
                                       (name, m_dp, any_cast<edge_descriptor>(edge),
                                        value, value_type, m_type_names, type_found));            
141
142
143
144
        }
        catch (bad_lexical_cast)
        {
            throw parse_error("invalid value \"" + value + "\" for key " + 
145
                              name + " of type " + value_type);
146
147
148
        }
        if (!type_found)
            throw  parse_error("unrecognized type \"" + value_type + 
149
                               "\" for key " + name);
150
151
152
153
154
155
    }

    template <typename Key, typename ValueVector>
    class put_property
    {
    public:
156
        put_property(const std::string& name, dynamic_properties& dp, const Key& key, 
157
                     const std::string& value, const std::string& value_type, 
158
                     const char** type_names, bool& type_found)
159
160
161
162
163
164
165
166
            : m_name(name), m_dp(dp), m_key(key), m_value(value), 
              m_value_type(value_type), m_type_names(type_names), 
              m_type_found(type_found) {}
        template <class Value>
        void operator()(Value)
        {
            if (m_value_type == m_type_names[mpl::find<ValueVector,Value>::type::pos::value])
            {
167
168
                put(m_name, m_dp, m_key, lexical_cast<Value>(m_value));
                m_type_found = true;
169
170
            }
        }
171
    private:
172
173
174
175
176
        const std::string& m_name;
        dynamic_properties& m_dp;
        const Key& m_key;
        const std::string& m_value;
        const std::string& m_value_type;
177
        const  char** m_type_names;
178
        bool& m_type_found;
179
180
181
182
183
184
    };    
    
protected:
    MutableGraph& m_g;
    dynamic_properties& m_dp;
    typedef mpl::vector<bool, int, long, float, double, std::string> value_types;
185
    static const char* m_type_names[]; 
186
187
188
};

template<typename MutableGraph>
189
const char* mutate_graph_impl<MutableGraph>::m_type_names[] = {"boolean", "int", "long", "float", "double", "string"};
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

void
read_graphml(std::istream& in, mutate_graph& g);

template<typename MutableGraph>
void
read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp)
{    
    mutate_graph_impl<MutableGraph> mg(g,dp);
    read_graphml(in, mg);
}

template <typename Types>
class get_type_name
{
public:
206
    get_type_name(const std::type_info& type, const char** type_names, std::string& type_name)
207
        : m_type(type), m_type_names(type_names), m_type_name(type_name) {}
208
209
210
    template <typename Type>
    void operator()(Type)
    {
211
212
        if (typeid(Type) == m_type)
            m_type_name = m_type_names[mpl::find<Types,Type>::type::pos::value];
213
214
215
    }
private:
    const std::type_info &m_type;
216
    const char** m_type_names;
217
218
219
220
221
222
223
    std::string &m_type_name;
};


template <typename Graph, typename VertexIndexMap>
void
write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index,
224
              const dynamic_properties& dp, bool ordered_vertices=false)
225
226
227
228
229
230
{
    typedef typename graph_traits<Graph>::directed_category directed_category;
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

    BOOST_STATIC_CONSTANT(bool, 
231
232
                          graph_is_directed = 
                          (is_convertible<directed_category*, directed_tag*>::value));
233
234

    out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"
235
        << "<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";
236
237

    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;
238
    const char* type_names[] = {"boolean", "int", "int", "int", "int", "long", "long", "long", "long", "float", "double", "double", "string"};    
239
    std::map<std::string, std::string> graph_key_ids;
240
241
242
243
244
245
246
    std::map<std::string, std::string> vertex_key_ids;
    std::map<std::string, std::string> edge_key_ids;
    int key_count = 0;

    // Output keys
    for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) 
    {
247
        std::string key_id = "key" + lexical_cast<std::string>(key_count++);
248
249
        if (i->second->key() == typeid(graph_property_tag))
            graph_key_ids[i->first] = key_id;
250
251
252
253
254
255
256
257
258
        else if (i->second->key() == typeid(vertex_descriptor))
            vertex_key_ids[i->first] = key_id;
        else if (i->second->key() == typeid(edge_descriptor))
            edge_key_ids[i->first] = key_id;
        else
            continue;
        std::string type_name = "string";
        mpl::for_each<value_types>(get_type_name<value_types>(i->second->value(), type_names, type_name));
        out << "  <key id=\"" << key_id << "\" for=\"" 
259
            << (i->second->key() == typeid(graph_property_tag) ? "graph" : (i->second->key() == typeid(vertex_descriptor) ? "node" : "edge")) << "\""
260
261
262
            << " attr.name=\"" << i->first << "\""
            << " attr.type=\"" << type_name << "\""
            << " />\n";
263
264
265
    }

    out << "  <graph id=\"G\" edgedefault=\"" 
266
267
268
        << (graph_is_directed ? "directed" : "undirected") << "\""
        << " parse.nodeids=\"" << (ordered_vertices ? "canonical" : "free") << "\""
        << " parse.edgeids=\"canonical\" parse.order=\"nodesfirst\">\n";
269

270
271
272
    // Output graph data
    for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
    {
273
        if (i->second->key() == typeid(graph_property_tag)) 
274
275
        {
            out << "   <data key=\"" << graph_key_ids[i->first] << "\">"
276
                << i->second->get_string(graph_property_tag()) << "</data>\n";
277
        }
278
279
    }
    
280
281
282
283
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
    vertex_iterator v, v_end;
    for (tie(v, v_end) = vertices(g); v != v_end; ++v)
    {
284
285
286
287
288
289
        out << "    <node id=\"n" << get(vertex_index, *v) << "\">\n";
        // Output data
        for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
        {
            if (i->second->key() == typeid(vertex_descriptor)) 
            {
290
291
                out << "      <data key=\"" << vertex_key_ids[i->first] << "\">"
                    << i->second->get_string(*v) << "</data>\n";
292
293
294
            }
        }
        out << "    </node>\n";
295
296
297
298
299
300
301
    }

    typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
    edge_iterator e, e_end;
    typename graph_traits<Graph>::edges_size_type edge_count = 0;
    for (tie(e, e_end) = edges(g); e != e_end; ++e) 
    {
302
303
304
305
306
307
308
309
310
        out << "    <edge id=\"e" << edge_count++ << "\" source=\"n"
            << get(vertex_index, source(*e, g)) << "\" target=\"n"
            << get(vertex_index, target(*e, g)) << "\">\n";

        // Output data
        for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
        {
            if (i->second->key() == typeid(edge_descriptor)) 
            {
311
312
                out << "      <data key=\"" << edge_key_ids[i->first] << "\">"
                    << i->second->get_string(*e) << "</data>\n";
313
314
315
            }
        }
        out << "    </edge>\n";
316
317
318
    }

    out << "  </graph>\n"
319
        << "</graphml>\n";
320
321
322
323
324
325
}


template <typename Graph>
void
write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp, 
326
              bool ordered_vertices=false)
327
328
329
330
331
332
{
    write_graphml(out, g, get(vertex_index, g), dp, ordered_vertices);
}

} // boost namespace

333
#endif // BOOST_GRAPH_GRAPHML_HPP