graphml.cpp 13.1 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

// Copyright (C) 2004 The Trustees of Indiana University.
//
// Boost Software License - Version 1.0 - August 17th, 2003
//
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

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

49
50
#include <boost/variant.hpp>
#include <boost/algorithm/string/replace.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
51
#include "expat.h"
52
#include "graphml.hpp"
Tiago Peixoto's avatar
Tiago Peixoto committed
53

54
using namespace boost;
Tiago Peixoto's avatar
Tiago Peixoto committed
55
56
57
58

class graphml_reader
{
public:
59
    graphml_reader(mutate_graph& g) 
60
        : m_g(g), m_canonical_vertices(false) { }
Tiago Peixoto's avatar
Tiago Peixoto committed
61
62
63
    
    void run(std::istream& in)
    {
64
        const int buffer_size = 4096;
65
66
67
68
        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);
69
        char buffer[buffer_size];
70
        int retval;
71
72
73
        do 
        {
            in.read(buffer, buffer_size);
74
            retval = XML_Parse(m_parser, buffer, in.gcount(), in.gcount() == 0);
75
        } 
76
        while (retval && in.good());
77

78
        if (retval == 0) 
79
80
        {
            std::stringstream s;
81
82
83
            s << "on line " << XML_GetCurrentLineNumber(m_parser) 
              <<", column " << XML_GetCurrentColumnNumber(m_parser)
              << ": " << XML_ErrorString(XML_GetErrorCode(m_parser));
84
85
            throw parse_error(s.str());
        }
86
        XML_ParserFree(m_parser);
Tiago Peixoto's avatar
Tiago Peixoto committed
87
88
89
90
91
    }

private:
    /// The kinds of keys. Not all of these are supported
    enum key_kind { 
92
93
94
95
96
97
98
        graph_key, 
        node_key, 
        edge_key,
        hyperedge_key,
        port_key,
        endpoint_key, 
        all_key
Tiago Peixoto's avatar
Tiago Peixoto committed
99
100
101
102
    };

    static void 
    on_start_element(void* user_data, const XML_Char *c_name,
103
                     const XML_Char **atts)
Tiago Peixoto's avatar
Tiago Peixoto committed
104
    {
105
106
107
        graphml_reader* self = static_cast<graphml_reader*>(user_data);

        std::string name(c_name);
108
        replace_first(name, "http://graphml.graphdrawing.org/xmlns|", "");
109
110
        
        if (name == "edge") 
111
112
        {
            std::string id;
113
            std::string source, target;
114
115
            while (*atts) 
            {
116
117
118
119
                std::string name = *atts++;
                std::string value = *atts++;

                if (name == "id") id = value;
120
121
122
                else if (name == "source") source = value;
                else if (name == "target") target = value;
                else if (name == "directed") 
123
                {
124
125
                    bool edge_is_directed = (value == "directed");
                    if (edge_is_directed != self->m_g.is_directed()) 
126
                    {
127
128
129
130
                        if (edge_is_directed) 
                            throw directed_graph_error();
                        else
                            throw undirected_graph_error();
131
132
                    }
                }
133
134
            }

135
136
137
            self->m_active_descriptor = self->m_edge.size();
            self->handle_edge(source, target);
        }
138
139
140
141
142
143
        else if (name == "node") 
        {
            std::string id;

            while (*atts) 
            {
144
145
146
147
                std::string name = *atts++;
                std::string value = *atts++;
                
                if (name == "id") id = value;
148
149
150
151
152
            }

            self->handle_vertex(id);
            self->m_active_descriptor = id;
        } 
153
154
155
156
157
158
159
160
161
162
163
        else if (name == "data") 
        {
            while (*atts) 
            {
                std::string name = *atts++;
                std::string value = *atts++;

                if (name == "key") self->m_active_key = value;
            }
        }
        else if (name == "key") 
164
165
        {
            std::string id;
166
167
168
169
            std::string key_name;
            std::string key_type;
            key_kind kind = all_key;

170
171
            while (*atts) 
            {
172
173
174
175
                std::string name = *atts++;
                std::string value = *atts++;

                if (name == "id") id = value;
176
177
178
                else if (name == "attr.name") key_name = value;
                else if (name == "attr.type") key_type = value;
                else if (name == "for") 
179
                {
180
181
182
183
184
185
186
187
                    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;
                    else 
188
                    {
189
190
191
192
193
                        std::stringstream s;
                        s << "on line " << XML_GetCurrentLineNumber(self->m_parser) 
                          << ", column " << XML_GetCurrentColumnNumber(self->m_parser)
                          << ": unrecognized key kind '" << value << "'";
                        throw parse_error(s.str());
194
195
                    }
                }
196
197
            }

198
199
200
201
            self->m_keys[id] = kind;
            self->m_key_name[id] = key_name;
            self->m_key_type[id] = key_type;
            self->m_active_key = id;
202
203
204
205
206
        } 
        else if (name == "graph") 
        {
            while (*atts) 
            {
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
                std::string name = *atts++;
                std::string value = *atts++;
                
                if (name == "edgedefault") 
                {
                    bool edge_is_directed = (value == "directed");
                    if (edge_is_directed != self->m_g.is_directed()) 
                    {
                        if (edge_is_directed) 
                            throw directed_graph_error();
                        else
                            throw undirected_graph_error();
                    }
                }
                else if (name == "parse.nodeids")
                {
                    self->m_canonical_vertices = (value == "canonical");
                }
225
226
227
228
229
            }
            self->m_active_descriptor = "";
        } 

        self->m_character_data.clear();
Tiago Peixoto's avatar
Tiago Peixoto committed
230
231
232
233
234
    }
    
    static void
    on_end_element(void* user_data, const XML_Char *c_name)
    {
235
        graphml_reader* self = static_cast<graphml_reader*>(user_data);
236

237
        std::string name(c_name);
238
        replace_first(name, "http://graphml.graphdrawing.org/xmlns|", "");
239
240

        if (name == "data") 
241
        {            
242
            self->handle_property(self->m_active_key, self->m_active_descriptor,
243
                                  self->m_character_data);
244
245
246
247
248
        } 
        else if (name == "default")
        {
            self->m_key_default[self->m_active_key] = self->m_character_data;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
249
250
251
252
253
    }

    static void
    on_character_data(void* user_data, const XML_Char* s, int len)
    {
254
255
        graphml_reader* self = static_cast<graphml_reader*>(user_data);
        self->m_character_data.append(s, len);
Tiago Peixoto's avatar
Tiago Peixoto committed
256
257
258
259
260
    }

    void 
    handle_vertex(const std::string& v)
    {
261
262
263
264
265
266
267
268
269
        bool is_new = false;

        if (m_canonical_vertices)
        {
            size_t id;

            //strip leading "n" from name
            try 
            {
270
                id = lexical_cast<size_t>(std::string(v,1));
271
272
273
            }
            catch (bad_lexical_cast)
            {
274
275
276
277
278
                std::stringstream s;
                s << "on line " << XML_GetCurrentLineNumber(m_parser) 
                  << ", column " << XML_GetCurrentColumnNumber(m_parser)
                  << ": invalid vertex: " << v;
                throw parse_error(s.str());
279
280
281
282
            }
            
            while(id >= m_canonical_vertex.size())
            {
283
284
                m_canonical_vertex.push_back(m_g.do_add_vertex());
                is_new = true;
285
286
287
288
289
290
            }
        }
        else
        {
            if (m_vertex.find(v) == m_vertex.end())
            {
291
292
                m_vertex[v] = m_g.do_add_vertex();
                is_new = true;
293
294
295
296
297
298
299
300
            }
        }

        if (is_new)
        {
            std::map<std::string, std::string>::iterator iter;
            for (iter = m_key_default.begin(); iter != m_key_default.end(); ++iter)
            {
301
                if (m_keys[iter->first] == node_key)
302
                    handle_property(iter->first, v, iter->second);
303
304
            }
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
305
306
    }

307
    any
Tiago Peixoto's avatar
Tiago Peixoto committed
308
309
    get_vertex_descriptor(const std::string& v)
    {
310
311
312
313
314
315
316
        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
317
        {            
318
319
            return m_vertex[v];
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
320
321
322
    }

    void 
323
    handle_edge(const std::string& u, const std::string& v)
Tiago Peixoto's avatar
Tiago Peixoto committed
324
    {
325
326
        handle_vertex(u);
        handle_vertex(v);
Tiago Peixoto's avatar
Tiago Peixoto committed
327

328
329
330
        any source, target;
        source = get_vertex_descriptor(u);
        target = get_vertex_descriptor(v);
Tiago Peixoto's avatar
Tiago Peixoto committed
331

332
333
334
335
336
        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
337

338
339
340
        size_t e = m_edge.size();
        m_edge.push_back(edge);
        
341
342
343
344
        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)
345
                handle_property(iter->first, e, iter->second);
346
        }
347
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
348

349
    void handle_property(const std::string& key_id, const variant<std::string,size_t>& descriptor, const std::string& value)
Tiago Peixoto's avatar
Tiago Peixoto committed
350
    {
351
        try 
352
        {
353
354
355
356
357
358
359
            if (get<std::string>(&descriptor))
            {
                if (get<std::string>(descriptor) == "")
                    m_g.set_graph_property(m_key_name[key_id], value, m_key_type[key_id]);
                else
                    m_g.set_vertex_property(m_key_name[key_id], get_vertex_descriptor(get<std::string>(descriptor)), value, m_key_type[key_id]);
            }
360
            else
361
362
363
            {
                m_g.set_edge_property(m_key_name[key_id], get_edge_descriptor(get<size_t>(descriptor)), value, m_key_type[key_id]);
            }
364
        }
365
        catch (parse_error &e)
366
        {
367
368
369
370
371
            std::stringstream s;
            s << "on line " << XML_GetCurrentLineNumber(m_parser) 
              << ", column " << XML_GetCurrentColumnNumber(m_parser)
              << ": " << e.error;
            throw parse_error(s.str());
372
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
373
374
    }

375
376
377
378
379
380
    any
    get_edge_descriptor(size_t e)
    {
        return m_edge[e];
    }

381
    mutate_graph& m_g;
Tiago Peixoto's avatar
Tiago Peixoto committed
382
383
384
    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;
385
386
387
    std::map<std::string, std::string> m_key_default;
    std::map<std::string, any> m_vertex;
    std::vector<any> m_canonical_vertex;
388
389
    std::vector<any> m_edge;
    variant<std::string, size_t> m_active_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
390
391
392
393
    std::string m_active_key;
    std::string m_character_data;
    bool m_canonical_vertices;
    bool m_canonical_edges;
394
    XML_Parser m_parser;
Tiago Peixoto's avatar
Tiago Peixoto committed
395
396
};

397
namespace boost
Tiago Peixoto's avatar
Tiago Peixoto committed
398
399
{
void
400
401
402
403
read_graphml(std::istream& in, mutate_graph& g)
{    
    graphml_reader reader(g);
    reader.run(in);
Tiago Peixoto's avatar
Tiago Peixoto committed
404
405
}
}