graphml.cpp 11.7 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
2
// Copyright (C) 2004  The Trustees of Indiana University.
Tiago Peixoto's avatar
Tiago Peixoto committed
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)
Tiago Peixoto's avatar
Tiago Peixoto committed
7
8
9
10
11

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
//           Tiago de Paula Peixoto

12
#include <boost/variant.hpp>
13
14
#include <expat.h>
#include <boost/graph/graphml.hpp>
15
#include <boost/algorithm/string/replace.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
16

17
using namespace boost;
18
19
20
21
22
23
24
25
26
27
28
29
namespace boost
{
std::string protect_xml_string(const std::string& os)
{
    using namespace boost::algorithm;
    std::string s(os);
    replace_all(s, "&", "&amp;");
    replace_all(s, "<", "&lt;");
    replace_all(s, ">", "&gt;");
    return s;
}
}
Tiago Peixoto's avatar
Tiago Peixoto committed
30
31
32
33

class graphml_reader
{
public:
34
    graphml_reader(mutate_graph& g)
35
        : m_g(g), m_canonical_vertices(false) { }
36

Tiago Peixoto's avatar
Tiago Peixoto committed
37
38
    void run(std::istream& in)
    {
39
        const int buffer_size = 4096;
40
41
42
43
        m_parser = XML_ParserCreateNS(0,'|');
        XML_SetElementHandler(m_parser, &on_start_element, &on_end_element);
        XML_SetCharacterDataHandler(m_parser, &on_character_data);
        XML_SetUserData(m_parser, this);
44
        char buffer[buffer_size];
45
46

        bool okay = true;
47
        do
48
49
        {
            in.read(buffer, buffer_size);
50
            okay = XML_Parse(m_parser, buffer, in.gcount(), in.gcount() == 0);
51
        }
52
        while (okay && in.good());
53

54
        if (!okay)
55
56
        {
            std::stringstream s;
57
            s << "on line " << XML_GetCurrentLineNumber(m_parser)
58
59
              <<", column " << XML_GetCurrentColumnNumber(m_parser)
              << ": " << XML_ErrorString(XML_GetErrorCode(m_parser));
60
61
            throw parse_error(s.str());
        }
62
        XML_ParserFree(m_parser);
Tiago Peixoto's avatar
Tiago Peixoto committed
63
64
65
66
    }

private:
    /// The kinds of keys. Not all of these are supported
67
68
69
    enum key_kind {
        graph_key,
        node_key,
70
71
72
        edge_key,
        hyperedge_key,
        port_key,
73
        endpoint_key,
74
        all_key
Tiago Peixoto's avatar
Tiago Peixoto committed
75
76
    };

77
    static void
Tiago Peixoto's avatar
Tiago Peixoto committed
78
    on_start_element(void* user_data, const XML_Char *c_name,
79
                     const XML_Char **atts)
Tiago Peixoto's avatar
Tiago Peixoto committed
80
    {
81
82
83
        graphml_reader* self = static_cast<graphml_reader*>(user_data);

        std::string name(c_name);
84
        replace_first(name, "http://graphml.graphdrawing.org/xmlns|", "");
85
86

        if (name == "edge")
87
88
        {
            std::string id;
89
            std::string source, target;
90
            while (*atts)
91
            {
92
93
94
95
                std::string name = *atts++;
                std::string value = *atts++;

                if (name == "id") id = value;
96
97
                else if (name == "source") source = value;
                else if (name == "target") target = value;
98
                else if (name == "directed")
99
                {
100
                    bool edge_is_directed = (value == "directed");
101
                    if (edge_is_directed != self->m_g.is_directed())
102
                    {
103
                        if (edge_is_directed)
104
105
106
                            throw directed_graph_error();
                        else
                            throw undirected_graph_error();
107
108
                    }
                }
109
110
            }

111
112
113
            self->m_active_descriptor = self->m_edge.size();
            self->handle_edge(source, target);
        }
114
        else if (name == "node")
115
116
117
        {
            std::string id;

118
            while (*atts)
119
            {
120
121
                std::string name = *atts++;
                std::string value = *atts++;
122

123
                if (name == "id") id = value;
124
125
126
127
            }

            self->handle_vertex(id);
            self->m_active_descriptor = id;
128
129
        }
        else if (name == "data")
130
        {
131
            while (*atts)
132
133
134
135
136
137
138
            {
                std::string name = *atts++;
                std::string value = *atts++;

                if (name == "key") self->m_active_key = value;
            }
        }
139
        else if (name == "key")
140
141
        {
            std::string id;
142
143
144
145
            std::string key_name;
            std::string key_type;
            key_kind kind = all_key;

146
            while (*atts)
147
            {
148
149
150
151
                std::string name = *atts++;
                std::string value = *atts++;

                if (name == "id") id = value;
152
153
                else if (name == "attr.name") key_name = value;
                else if (name == "attr.type") key_type = value;
154
                else if (name == "for")
155
                {
156
157
158
159
160
161
162
                    if (value == "graph") kind = graph_key;
                    else if (value == "node") kind = node_key;
                    else if (value == "edge") kind = edge_key;
                    else if (value == "hyperedge") kind = hyperedge_key;
                    else if (value == "port") kind = port_key;
                    else if (value == "endpoint") kind = endpoint_key;
                    else if (value == "all") kind = all_key;
163
                    else
164
                    {
165
                        std::stringstream s;
166
167
168
                        s << "on line "
                          << XML_GetCurrentLineNumber(self->m_parser)
                          << ", column "
169
                          << XML_GetCurrentColumnNumber(self->m_parser)
170
171
                          << ": unrecognized key kind '" << value << "'";
                        throw parse_error(s.str());
172
173
                    }
                }
174
175
            }

176
177
178
179
            self->m_keys[id] = kind;
            self->m_key_name[id] = key_name;
            self->m_key_type[id] = key_type;
            self->m_active_key = id;
180
181
        }
        else if (name == "graph")
182
        {
183
            while (*atts)
184
            {
185
186
                std::string name = *atts++;
                std::string value = *atts++;
187
188

                if (name == "edgedefault")
189
190
                {
                    bool edge_is_directed = (value == "directed");
191
                    if (edge_is_directed != self->m_g.is_directed())
192
                    {
193
                        if (edge_is_directed)
194
195
196
197
198
199
200
201
202
                            throw directed_graph_error();
                        else
                            throw undirected_graph_error();
                    }
                }
                else if (name == "parse.nodeids")
                {
                    self->m_canonical_vertices = (value == "canonical");
                }
203
204
            }
            self->m_active_descriptor = "";
205
        }
206
207

        self->m_character_data.clear();
Tiago Peixoto's avatar
Tiago Peixoto committed
208
    }
209

Tiago Peixoto's avatar
Tiago Peixoto committed
210
211
212
    static void
    on_end_element(void* user_data, const XML_Char *c_name)
    {
213
        graphml_reader* self = static_cast<graphml_reader*>(user_data);
214

215
        std::string name(c_name);
216
        replace_first(name, "http://graphml.graphdrawing.org/xmlns|", "");
217

218
219
        if (name == "data")
        {
220
            self->handle_property(self->m_active_key, self->m_active_descriptor,
221
                                  self->m_character_data);
222
        }
223
224
225
226
        else if (name == "default")
        {
            self->m_key_default[self->m_active_key] = self->m_character_data;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
227
228
229
230
231
    }

    static void
    on_character_data(void* user_data, const XML_Char* s, int len)
    {
232
233
        graphml_reader* self = static_cast<graphml_reader*>(user_data);
        self->m_character_data.append(s, len);
Tiago Peixoto's avatar
Tiago Peixoto committed
234
235
    }

236
    void
Tiago Peixoto's avatar
Tiago Peixoto committed
237
238
    handle_vertex(const std::string& v)
    {
239
240
241
242
243
244
245
        bool is_new = false;

        if (m_canonical_vertices)
        {
            size_t id;

            //strip leading "n" from name
246
            try
247
            {
248
                id = lexical_cast<size_t>(std::string(v,1));
249
250
251
            }
            catch (bad_lexical_cast)
            {
252
                std::stringstream s;
253
                s << "on line " << XML_GetCurrentLineNumber(m_parser)
254
255
256
                  << ", column " << XML_GetCurrentColumnNumber(m_parser)
                  << ": invalid vertex: " << v;
                throw parse_error(s.str());
257
            }
258

259
260
            while(id >= m_canonical_vertex.size())
            {
261
262
                m_canonical_vertex.push_back(m_g.do_add_vertex());
                is_new = true;
263
264
265
266
267
268
            }
        }
        else
        {
            if (m_vertex.find(v) == m_vertex.end())
            {
269
270
                m_vertex[v] = m_g.do_add_vertex();
                is_new = true;
271
272
273
274
275
276
            }
        }

        if (is_new)
        {
            std::map<std::string, std::string>::iterator iter;
277
            for (iter = m_key_default.begin(); iter != m_key_default.end();
278
                 ++iter)
279
            {
280
                if (m_keys[iter->first] == node_key)
281
                    handle_property(iter->first, v, iter->second);
282
283
            }
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
284
285
    }

286
    any
Tiago Peixoto's avatar
Tiago Peixoto committed
287
288
    get_vertex_descriptor(const std::string& v)
    {
289
290
291
292
293
294
295
        if (m_canonical_vertices)
        {
            //strip leading "n" from name
            size_t id = lexical_cast<size_t>(std::string(v,1));
            return m_canonical_vertex[id];
        }
        else
296
        {
297
298
            return m_vertex[v];
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
299
300
    }

301
    void
302
    handle_edge(const std::string& u, const std::string& v)
Tiago Peixoto's avatar
Tiago Peixoto committed
303
    {
304
305
        handle_vertex(u);
        handle_vertex(v);
Tiago Peixoto's avatar
Tiago Peixoto committed
306

307
308
309
        any source, target;
        source = get_vertex_descriptor(u);
        target = get_vertex_descriptor(v);
Tiago Peixoto's avatar
Tiago Peixoto committed
310

311
312
313
314
315
        any edge;
        bool added;
        tie(edge, added) = m_g.do_add_edge(source, target);
        if (!added)
            throw bad_parallel_edge(u, v);
Tiago Peixoto's avatar
Tiago Peixoto committed
316

317
318
        size_t e = m_edge.size();
        m_edge.push_back(edge);
319

320
321
322
323
        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)
324
                handle_property(iter->first, e, iter->second);
325
        }
326
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
327

328
329
    void handle_property(const std::string& key_id,
                         const variant<std::string,size_t>& descriptor,
330
                         const std::string& value)
Tiago Peixoto's avatar
Tiago Peixoto committed
331
    {
332
        try
333
        {
334
335
336
            if (get<std::string>(&descriptor))
            {
                if (get<std::string>(descriptor) == "")
337
                    m_g.set_graph_property(m_key_name[key_id], value,
338
                                           m_key_type[key_id]);
339
                else
340
                    m_g.set_vertex_property(m_key_name[key_id],
341
                                            get_vertex_descriptor
342
                                                (get<std::string>(descriptor)),
343
                                            value, m_key_type[key_id]);
344
            }
345
            else
346
            {
347
                m_g.set_edge_property(m_key_name[key_id],
348
                                      get_edge_descriptor
349
                                          (get<size_t>(descriptor)),
350
                                      value, m_key_type[key_id]);
351
            }
352
        }
353
        catch (parse_error &e)
354
        {
355
            std::stringstream s;
356
            s << "on line " << XML_GetCurrentLineNumber(m_parser)
357
358
359
              << ", column " << XML_GetCurrentColumnNumber(m_parser)
              << ": " << e.error;
            throw parse_error(s.str());
360
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
361
362
    }

363
364
365
366
367
368
    any
    get_edge_descriptor(size_t e)
    {
        return m_edge[e];
    }

369
    mutate_graph& m_g;
Tiago Peixoto's avatar
Tiago Peixoto committed
370
371
372
    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;
373
374
375
    std::map<std::string, std::string> m_key_default;
    std::map<std::string, any> m_vertex;
    std::vector<any> m_canonical_vertex;
376
377
    std::vector<any> m_edge;
    variant<std::string, size_t> m_active_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
378
379
380
381
    std::string m_active_key;
    std::string m_character_data;
    bool m_canonical_vertices;
    bool m_canonical_edges;
382
    XML_Parser m_parser;
Tiago Peixoto's avatar
Tiago Peixoto committed
383
384
};

385
namespace boost
Tiago Peixoto's avatar
Tiago Peixoto committed
386
387
{
void
388
read_graphml(std::istream& in, mutate_graph& g)
389
{
390
391
    graphml_reader reader(g);
    reader.run(in);
Tiago Peixoto's avatar
Tiago Peixoto committed
392
393
}
}