Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / readwrite / gml.py @ 5cef0f13

History | View | Annotate | Download (27.2 KB)

1
# encoding: utf-8
2
#    Copyright (C) 2008-2019 by
3
#    Aric Hagberg <hagberg@lanl.gov>
4
#    Dan Schult <dschult@colgate.edu>
5
#    Pieter Swart <swart@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
#
9
# Author: Aric Hagberg (hagberg@lanl.gov)
10
"""
11
Read graphs in GML format.
12

13
"GML, the Graph Modelling Language, is our proposal for a portable
14
file format for graphs. GML's key features are portability, simple
15
syntax, extensibility and flexibility. A GML file consists of a
16
hierarchical key-value lists. Graphs can be annotated with arbitrary
17
data structures. The idea for a common file format was born at the
18
GD'95; this proposal is the outcome of many discussions. GML is the
19
standard file format in the Graphlet graph editor system. It has been
20
overtaken and adapted by several other systems for drawing graphs."
21

22
GML files are stored using a 7-bit ASCII encoding with any extended
23
ASCII characters (iso8859-1) appearing as HTML character entities.
24
You will need to give some thought into how the exported data should
25
interact with different languages and even different Python versions.
26
Re-importing from gml is also a concern.
27

28
Without specifying a `stringizer`/`destringizer`, the code is capable of
29
handling `int`/`float`/`str`/`dict`/`list` data as required by the GML
30
specification.  For other data types, you need to explicitly supply a
31
`stringizer`/`destringizer`.
32

33
For better interoperability of data generated by Python 2 and Python 3,
34
we've provided `literal_stringizer` and `literal_destringizer`.
35

36
For additional documentation on the GML file format, please see the
37
`GML website <http://www.infosun.fim.uni-passau.de/Graphlet/GML/gml-tr.html>`_.
38

39
Several example graphs in GML format may be found on Mark Newman's
40
`Network data page <http://www-personal.umich.edu/~mejn/netdata/>`_.
41
"""
42
try:
43
    try:
44
        from cStringIO import StringIO
45
    except ImportError:
46
        from StringIO import StringIO
47
except ImportError:
48
    from io import StringIO
49
from ast import literal_eval
50
from collections import defaultdict
51
import networkx as nx
52
from networkx.exception import NetworkXError
53
from networkx.utils import open_file
54

    
55
import re
56
try:
57
    import htmlentitydefs
58
except ImportError:
59
    # Python 3.x
60
    import html.entities as htmlentitydefs
61

    
62
__all__ = ['read_gml', 'parse_gml', 'generate_gml', 'write_gml']
63

    
64

    
65
try:
66
    long
67
except NameError:
68
    long = int
69
try:
70
    unicode
71
except NameError:
72
    unicode = str
73
try:
74
    unichr
75
except NameError:
76
    unichr = chr
77
try:
78
    literal_eval(r"u'\u4444'")
79
except SyntaxError:
80
    # Remove 'u' prefixes in unicode literals in Python 3
81
    def rtp_fix_unicode(s): return s[1:]
82
else:
83
    rtp_fix_unicode = None
84

    
85

    
86
def escape(text):
87
    """Use XML character references to escape characters.
88

89
    Use XML character references for unprintable or non-ASCII
90
    characters, double quotes and ampersands in a string
91
    """
92
    def fixup(m):
93
        ch = m.group(0)
94
        return '&#' + str(ord(ch)) + ';'
95

    
96
    text = re.sub('[^ -~]|[&"]', fixup, text)
97
    return text if isinstance(text, str) else str(text)
98

    
99

    
100
def unescape(text):
101
    """Replace XML character references with the referenced characters"""
102
    def fixup(m):
103
        text = m.group(0)
104
        if text[1] == '#':
105
            # Character reference
106
            if text[2] == 'x':
107
                code = int(text[3:-1], 16)
108
            else:
109
                code = int(text[2:-1])
110
        else:
111
            # Named entity
112
            try:
113
                code = htmlentitydefs.name2codepoint[text[1:-1]]
114
            except KeyError:
115
                return text  # leave unchanged
116
        try:
117
            return chr(code) if code < 256 else unichr(code)
118
        except (ValueError, OverflowError):
119
            return text  # leave unchanged
120

    
121
    return re.sub("&(?:[0-9A-Za-z]+|#(?:[0-9]+|x[0-9A-Fa-f]+));", fixup, text)
122

    
123

    
124
def literal_destringizer(rep):
125
    """Convert a Python literal to the value it represents.
126

127
    Parameters
128
    ----------
129
    rep : string
130
        A Python literal.
131

132
    Returns
133
    -------
134
    value : object
135
        The value of the Python literal.
136

137
    Raises
138
    ------
139
    ValueError
140
        If `rep` is not a Python literal.
141
    """
142
    if isinstance(rep, (str, unicode)):
143
        orig_rep = rep
144
        if rtp_fix_unicode is not None:
145
            rep = rtp_fix_unicode(rep)
146
        try:
147
            return literal_eval(rep)
148
        except SyntaxError:
149
            raise ValueError('%r is not a valid Python literal' % (orig_rep,))
150
    else:
151
        raise ValueError('%r is not a string' % (rep,))
152

    
153

    
154
@open_file(0, mode='rb')
155
def read_gml(path, label='label', destringizer=None):
156
    """Read graph in GML format from `path`.
157

158
    Parameters
159
    ----------
160
    path : filename or filehandle
161
        The filename or filehandle to read from.
162

163
    label : string, optional
164
        If not None, the parsed nodes will be renamed according to node
165
        attributes indicated by `label`. Default value: 'label'.
166

167
    destringizer : callable, optional
168
        A `destringizer` that recovers values stored as strings in GML. If it
169
        cannot convert a string to a value, a `ValueError` is raised. Default
170
        value : None.
171

172
    Returns
173
    -------
174
    G : NetworkX graph
175
        The parsed graph.
176

177
    Raises
178
    ------
179
    NetworkXError
180
        If the input cannot be parsed.
181

182
    See Also
183
    --------
184
    write_gml, parse_gml, literal_destringizer
185

186
    Notes
187
    -----
188
    GML files are stored using a 7-bit ASCII encoding with any extended
189
    ASCII characters (iso8859-1) appearing as HTML character entities.
190
    Without specifying a `stringizer`/`destringizer`, the code is capable of
191
    handling `int`/`float`/`str`/`dict`/`list` data as required by the GML
192
    specification.  For other data types, you need to explicitly supply a
193
    `stringizer`/`destringizer`.
194

195
    For additional documentation on the GML file format, please see the
196
    `GML website <http://www.infosun.fim.uni-passau.de/Graphlet/GML/gml-tr.html>`_.
197

198
    See the module docstring :mod:`networkx.readwrite.gml` for more details.
199

200
    Examples
201
    --------
202
    >>> G = nx.path_graph(4)
203
    >>> nx.write_gml(G, 'test.gml')
204
    >>> H = nx.read_gml('test.gml')
205
    """
206
    def filter_lines(lines):
207
        for line in lines:
208
            try:
209
                line = line.decode('ascii')
210
            except UnicodeDecodeError:
211
                raise NetworkXError('input is not ASCII-encoded')
212
            if not isinstance(line, str):
213
                lines = str(lines)
214
            if line and line[-1] == '\n':
215
                line = line[:-1]
216
            yield line
217

    
218
    G = parse_gml_lines(filter_lines(path), label, destringizer)
219
    return G
220

    
221

    
222
def parse_gml(lines, label='label', destringizer=None):
223
    """Parse GML graph from a string or iterable.
224

225
    Parameters
226
    ----------
227
    lines : string or iterable of strings
228
       Data in GML format.
229

230
    label : string, optional
231
        If not None, the parsed nodes will be renamed according to node
232
        attributes indicated by `label`. Default value: 'label'.
233

234
    destringizer : callable, optional
235
        A `destringizer` that recovers values stored as strings in GML. If it
236
        cannot convert a string to a value, a `ValueError` is raised. Default
237
        value : None.
238

239
    Returns
240
    -------
241
    G : NetworkX graph
242
        The parsed graph.
243

244
    Raises
245
    ------
246
    NetworkXError
247
        If the input cannot be parsed.
248

249
    See Also
250
    --------
251
    write_gml, read_gml, literal_destringizer
252

253
    Notes
254
    -----
255
    This stores nested GML attributes as dictionaries in the NetworkX graph,
256
    node, and edge attribute structures.
257

258
    GML files are stored using a 7-bit ASCII encoding with any extended
259
    ASCII characters (iso8859-1) appearing as HTML character entities.
260
    Without specifying a `stringizer`/`destringizer`, the code is capable of
261
    handling `int`/`float`/`str`/`dict`/`list` data as required by the GML
262
    specification.  For other data types, you need to explicitly supply a
263
    `stringizer`/`destringizer`.
264

265
    For additional documentation on the GML file format, please see the
266
    `GML website <http://www.infosun.fim.uni-passau.de/Graphlet/GML/gml-tr.html>`_.
267

268
    See the module docstring :mod:`networkx.readwrite.gml` for more details.
269
    """
270
    def decode_line(line):
271
        if isinstance(line, bytes):
272
            try:
273
                line.decode('ascii')
274
            except UnicodeDecodeError:
275
                raise NetworkXError('input is not ASCII-encoded')
276
        if not isinstance(line, str):
277
            line = str(line)
278
        return line
279

    
280
    def filter_lines(lines):
281
        if isinstance(lines, (str, unicode)):
282
            lines = decode_line(lines)
283
            lines = lines.splitlines()
284
            for line in lines:
285
                yield line
286
        else:
287
            for line in lines:
288
                line = decode_line(line)
289
                if line and line[-1] == '\n':
290
                    line = line[:-1]
291
                if line.find('\n') != -1:
292
                    raise NetworkXError('input line contains newline')
293
                yield line
294

    
295
    G = parse_gml_lines(filter_lines(lines), label, destringizer)
296
    return G
297

    
298

    
299
def parse_gml_lines(lines, label, destringizer):
300
    """Parse GML `lines` into a graph.
301
    """
302
    def tokenize():
303
        patterns = [
304
            r'[A-Za-z][0-9A-Za-z_]*\b',  # keys
305
            r'[+-]?(?:[0-9]*\.[0-9]+|[0-9]+\.[0-9]*)(?:[Ee][+-]?[0-9]+)?',  # reals
306
            r'[+-]?[0-9]+',   # ints
307
            r'".*?"',         # strings
308
            r'\[',            # dict start
309
            r'\]',            # dict end
310
            r'#.*$|\s+'       # comments and whitespaces
311
        ]
312
        tokens = re.compile(
313
            '|'.join('(' + pattern + ')' for pattern in patterns))
314
        lineno = 0
315
        for line in lines:
316
            length = len(line)
317
            pos = 0
318
            while pos < length:
319
                match = tokens.match(line, pos)
320
                if match is not None:
321
                    for i in range(len(patterns)):
322
                        group = match.group(i + 1)
323
                        if group is not None:
324
                            if i == 0:    # keys
325
                                value = group.rstrip()
326
                            elif i == 1:  # reals
327
                                value = float(group)
328
                            elif i == 2:  # ints
329
                                value = int(group)
330
                            else:
331
                                value = group
332
                            if i != 6:    # comments and whitespaces
333
                                yield (i, value, lineno + 1, pos + 1)
334
                            pos += len(group)
335
                            break
336
                else:
337
                    raise NetworkXError('cannot tokenize %r at (%d, %d)' %
338
                                        (line[pos:], lineno + 1, pos + 1))
339
            lineno += 1
340
        yield (None, None, lineno + 1, 1)  # EOF
341

    
342
    def unexpected(curr_token, expected):
343
        category, value, lineno, pos = curr_token
344
        raise NetworkXError(
345
            'expected %s, found %s at (%d, %d)' %
346
            (expected, repr(value) if value is not None else 'EOF', lineno,
347
             pos))
348

    
349
    def consume(curr_token, category, expected):
350
        if curr_token[0] == category:
351
            return next(tokens)
352
        unexpected(curr_token, expected)
353

    
354
    def parse_kv(curr_token):
355
        dct = defaultdict(list)
356
        while curr_token[0] == 0:  # keys
357
            key = curr_token[1]
358
            curr_token = next(tokens)
359
            category = curr_token[0]
360
            if category == 1 or category == 2:  # reals or ints
361
                value = curr_token[1]
362
                curr_token = next(tokens)
363
            elif category == 3:  # strings
364
                value = unescape(curr_token[1][1:-1])
365
                if destringizer:
366
                    try:
367
                        value = destringizer(value)
368
                    except ValueError:
369
                        pass
370
                curr_token = next(tokens)
371
            elif category == 4:  # dict start
372
                curr_token, value = parse_dict(curr_token)
373
            else:
374
                unexpected(curr_token, "an int, float, string or '['")
375
            dct[key].append(value)
376
        dct = {key: (value if not isinstance(value, list) or len(value) != 1
377
                     else value[0]) for key, value in dct.items()}
378
        return curr_token, dct
379

    
380
    def parse_dict(curr_token):
381
        curr_token = consume(curr_token, 4, "'['")    # dict start
382
        curr_token, dct = parse_kv(curr_token)
383
        curr_token = consume(curr_token, 5, "']'")  # dict end
384
        return curr_token, dct
385

    
386
    def parse_graph():
387
        curr_token, dct = parse_kv(next(tokens))
388
        if curr_token[0] is not None:  # EOF
389
            unexpected(curr_token, 'EOF')
390
        if 'graph' not in dct:
391
            raise NetworkXError('input contains no graph')
392
        graph = dct['graph']
393
        if isinstance(graph, list):
394
            raise NetworkXError('input contains more than one graph')
395
        return graph
396

    
397
    tokens = tokenize()
398
    graph = parse_graph()
399

    
400
    directed = graph.pop('directed', False)
401
    multigraph = graph.pop('multigraph', False)
402
    if not multigraph:
403
        G = nx.DiGraph() if directed else nx.Graph()
404
    else:
405
        G = nx.MultiDiGraph() if directed else nx.MultiGraph()
406
    G.graph.update((key, value) for key, value in graph.items()
407
                   if key != 'node' and key != 'edge')
408

    
409
    def pop_attr(dct, category, attr, i):
410
        try:
411
            return dct.pop(attr)
412
        except KeyError:
413
            raise NetworkXError(
414
                "%s #%d has no '%s' attribute" % (category, i, attr))
415

    
416
    nodes = graph.get('node', [])
417
    mapping = {}
418
    node_labels = set()
419
    for i, node in enumerate(nodes if isinstance(nodes, list) else [nodes]):
420
        id = pop_attr(node, 'node', 'id', i)
421
        if id in G:
422
            raise NetworkXError('node id %r is duplicated' % (id,))
423
        if label is not None and label != 'id':
424
            node_label = pop_attr(node, 'node', label, i)
425
            if node_label in node_labels:
426
                raise NetworkXError('node label %r is duplicated' %
427
                                    (node_label,))
428
            node_labels.add(node_label)
429
            mapping[id] = node_label
430
        G.add_node(id, **node)
431

    
432
    edges = graph.get('edge', [])
433
    for i, edge in enumerate(edges if isinstance(edges, list) else [edges]):
434
        source = pop_attr(edge, 'edge', 'source', i)
435
        target = pop_attr(edge, 'edge', 'target', i)
436
        if source not in G:
437
            raise NetworkXError(
438
                'edge #%d has an undefined source %r' % (i, source))
439
        if target not in G:
440
            raise NetworkXError(
441
                'edge #%d has an undefined target %r' % (i, target))
442
        if not multigraph:
443
            if not G.has_edge(source, target):
444
                G.add_edge(source, target, **edge)
445
            else:
446
                raise nx.NetworkXError(
447
                    """edge #%d (%r%s%r) is duplicated
448

449
Hint:  If this is a multigraph, add "multigraph 1" to the header of the file.""" %
450
                    (i, source, '->' if directed else '--', target))
451
        else:
452
            key = edge.pop('key', None)
453
            if key is not None and G.has_edge(source, target, key):
454
                raise nx.NetworkXError(
455
                    'edge #%d (%r%s%r, %r) is duplicated' %
456
                    (i, source, '->' if directed else '--', target, key))
457
            G.add_edge(source, target, key, **edge)
458

    
459
    if label is not None and label != 'id':
460
        G = nx.relabel_nodes(G, mapping)
461
    return G
462

    
463

    
464
def literal_stringizer(value):
465
    """Convert a `value` to a Python literal in GML representation.
466

467
    Parameters
468
    ----------
469
    value : object
470
        The `value` to be converted to GML representation.
471

472
    Returns
473
    -------
474
    rep : string
475
        A double-quoted Python literal representing value. Unprintable
476
        characters are replaced by XML character references.
477

478
    Raises
479
    ------
480
    ValueError
481
        If `value` cannot be converted to GML.
482

483
    Notes
484
    -----
485
    `literal_stringizer` is largely the same as `repr` in terms of
486
    functionality but attempts prefix `unicode` and `bytes` literals with
487
    `u` and `b` to provide better interoperability of data generated by
488
    Python 2 and Python 3.
489

490
    The original value can be recovered using the
491
    :func:`networkx.readwrite.gml.literal_destringizer` function.
492
    """
493
    def stringize(value):
494
        if isinstance(value, (int, long, bool)) or value is None:
495
            if value is True:  # GML uses 1/0 for boolean values.
496
                buf.write(str(1))
497
            elif value is False:
498
                buf.write(str(0))
499
            else:
500
                buf.write(str(value))
501
        elif isinstance(value, unicode):
502
            text = repr(value)
503
            if text[0] != 'u':
504
                try:
505
                    value.encode('latin1')
506
                except UnicodeEncodeError:
507
                    text = 'u' + text
508
            buf.write(text)
509
        elif isinstance(value, (float, complex, str, bytes)):
510
            buf.write(repr(value))
511
        elif isinstance(value, list):
512
            buf.write('[')
513
            first = True
514
            for item in value:
515
                if not first:
516
                    buf.write(',')
517
                else:
518
                    first = False
519
                stringize(item)
520
            buf.write(']')
521
        elif isinstance(value, tuple):
522
            if len(value) > 1:
523
                buf.write('(')
524
                first = True
525
                for item in value:
526
                    if not first:
527
                        buf.write(',')
528
                    else:
529
                        first = False
530
                    stringize(item)
531
                buf.write(')')
532
            elif value:
533
                buf.write('(')
534
                stringize(value[0])
535
                buf.write(',)')
536
            else:
537
                buf.write('()')
538
        elif isinstance(value, dict):
539
            buf.write('{')
540
            first = True
541
            for key, value in value.items():
542
                if not first:
543
                    buf.write(',')
544
                else:
545
                    first = False
546
                stringize(key)
547
                buf.write(':')
548
                stringize(value)
549
            buf.write('}')
550
        elif isinstance(value, set):
551
            buf.write('{')
552
            first = True
553
            for item in value:
554
                if not first:
555
                    buf.write(',')
556
                else:
557
                    first = False
558
                stringize(item)
559
            buf.write('}')
560
        else:
561
            raise ValueError(
562
                '%r cannot be converted into a Python literal' % (value,))
563

    
564
    buf = StringIO()
565
    stringize(value)
566
    return buf.getvalue()
567

    
568

    
569
def generate_gml(G, stringizer=None):
570
    r"""Generate a single entry of the graph `G` in GML format.
571

572
    Parameters
573
    ----------
574
    G : NetworkX graph
575
        The graph to be converted to GML.
576

577
    stringizer : callable, optional
578
        A `stringizer` which converts non-int/non-float/non-dict values into
579
        strings. If it cannot convert a value into a string, it should raise a
580
        `ValueError` to indicate that. Default value: None.
581

582
    Returns
583
    -------
584
    lines: generator of strings
585
        Lines of GML data. Newlines are not appended.
586

587
    Raises
588
    ------
589
    NetworkXError
590
        If `stringizer` cannot convert a value into a string, or the value to
591
        convert is not a string while `stringizer` is None.
592

593
    See Also
594
    --------
595
    literal_stringizer
596

597
    Notes
598
    -----
599
    Graph attributes named 'directed', 'multigraph', 'node' or
600
    'edge', node attributes named 'id' or 'label', edge attributes
601
    named 'source' or 'target' (or 'key' if `G` is a multigraph)
602
    are ignored because these attribute names are used to encode the graph
603
    structure.
604

605
    GML files are stored using a 7-bit ASCII encoding with any extended
606
    ASCII characters (iso8859-1) appearing as HTML character entities.
607
    Without specifying a `stringizer`/`destringizer`, the code is capable of
608
    handling `int`/`float`/`str`/`dict`/`list` data as required by the GML
609
    specification.  For other data types, you need to explicitly supply a
610
    `stringizer`/`destringizer`.
611

612
    For additional documentation on the GML file format, please see the
613
    `GML website <http://www.infosun.fim.uni-passau.de/Graphlet/GML/gml-tr.html>`_.
614

615
    See the module docstring :mod:`networkx.readwrite.gml` for more details.
616

617
    Examples
618
    --------
619
    >>> G = nx.Graph()
620
    >>> G.add_node("1")
621
    >>> print("\n".join(nx.generate_gml(G)))
622
    graph [
623
      node [
624
        id 0
625
        label "1"
626
      ]
627
    ]
628
    >>> G = nx.OrderedMultiGraph([("a", "b"), ("a", "b")])
629
    >>> print("\n".join(nx.generate_gml(G)))
630
    graph [
631
      multigraph 1
632
      node [
633
        id 0
634
        label "a"
635
      ]
636
      node [
637
        id 1
638
        label "b"
639
      ]
640
      edge [
641
        source 0
642
        target 1
643
        key 0
644
      ]
645
      edge [
646
        source 0
647
        target 1
648
        key 1
649
      ]
650
    ]
651
    """
652
    valid_keys = re.compile('^[A-Za-z][0-9A-Za-z]*$')
653

    
654
    def stringize(key, value, ignored_keys, indent, in_list=False):
655
        if not isinstance(key, (str, unicode)):
656
            raise NetworkXError('%r is not a string' % (key,))
657
        if not valid_keys.match(key):
658
            raise NetworkXError('%r is not a valid key' % (key,))
659
        if not isinstance(key, str):
660
            key = str(key)
661
        if key not in ignored_keys:
662
            if isinstance(value, (int, long, bool)):
663
                if key == 'label':
664
                    yield indent + key + ' "' + str(value) + '"'
665
                elif value is True:
666
                    # python bool is an instance of int
667
                    yield indent + key + ' 1'
668
                elif value is False:
669
                    yield indent + key + ' 0'
670
                else:
671
                    yield indent + key + ' ' + str(value)
672
            elif isinstance(value, float):
673
                text = repr(value).upper()
674
                # GML requires that a real literal contain a decimal point, but
675
                # repr may not output a decimal point when the mantissa is
676
                # integral and hence needs fixing.
677
                epos = text.rfind('E')
678
                if epos != -1 and text.find('.', 0, epos) == -1:
679
                    text = text[:epos] + '.' + text[epos:]
680
                if key == 'label':
681
                    yield indent + key + ' "' + text + '"'
682
                else:
683
                    yield indent + key + ' ' + text
684
            elif isinstance(value, dict):
685
                yield indent + key + ' ['
686
                next_indent = indent + '  '
687
                for key, value in value.items():
688
                    for line in stringize(key, value, (), next_indent):
689
                        yield line
690
                yield indent + ']'
691
            elif isinstance(value, (list, tuple)) and key != 'label' \
692
                    and value and not in_list:
693
                next_indent = indent + '  '
694
                for val in value:
695
                    for line in stringize(key, val, (), next_indent, True):
696
                        yield line
697
            else:
698
                if stringizer:
699
                    try:
700
                        value = stringizer(value)
701
                    except ValueError:
702
                        raise NetworkXError(
703
                            '%r cannot be converted into a string' % (value,))
704
                if not isinstance(value, (str, unicode)):
705
                    raise NetworkXError('%r is not a string' % (value,))
706
                yield indent + key + ' "' + escape(value) + '"'
707

    
708
    multigraph = G.is_multigraph()
709
    yield 'graph ['
710

    
711
    # Output graph attributes
712
    if G.is_directed():
713
        yield '  directed 1'
714
    if multigraph:
715
        yield '  multigraph 1'
716
    ignored_keys = {'directed', 'multigraph', 'node', 'edge'}
717
    for attr, value in G.graph.items():
718
        for line in stringize(attr, value, ignored_keys, '  '):
719
            yield line
720

    
721
    # Output node data
722
    node_id = dict(zip(G, range(len(G))))
723
    ignored_keys = {'id', 'label'}
724
    for node, attrs in G.nodes.items():
725
        yield '  node ['
726
        yield '    id ' + str(node_id[node])
727
        for line in stringize('label', node, (), '    '):
728
            yield line
729
        for attr, value in attrs.items():
730
            for line in stringize(attr, value, ignored_keys, '    '):
731
                yield line
732
        yield '  ]'
733

    
734
    # Output edge data
735
    ignored_keys = {'source', 'target'}
736
    kwargs = {'data': True}
737
    if multigraph:
738
        ignored_keys.add('key')
739
        kwargs['keys'] = True
740
    for e in G.edges(**kwargs):
741
        yield '  edge ['
742
        yield '    source ' + str(node_id[e[0]])
743
        yield '    target ' + str(node_id[e[1]])
744
        if multigraph:
745
            for line in stringize('key', e[2], (), '    '):
746
                yield line
747
        for attr, value in e[-1].items():
748
            for line in stringize(attr, value, ignored_keys, '    '):
749
                yield line
750
        yield '  ]'
751
    yield ']'
752

    
753

    
754
@open_file(1, mode='wb')
755
def write_gml(G, path, stringizer=None):
756
    """Write a graph `G` in GML format to the file or file handle `path`.
757

758
    Parameters
759
    ----------
760
    G : NetworkX graph
761
        The graph to be converted to GML.
762

763
    path : filename or filehandle
764
        The filename or filehandle to write. Files whose names end with .gz or
765
        .bz2 will be compressed.
766

767
    stringizer : callable, optional
768
        A `stringizer` which converts non-int/non-float/non-dict values into
769
        strings. If it cannot convert a value into a string, it should raise a
770
        `ValueError` to indicate that. Default value: None.
771

772
    Raises
773
    ------
774
    NetworkXError
775
        If `stringizer` cannot convert a value into a string, or the value to
776
        convert is not a string while `stringizer` is None.
777

778
    See Also
779
    --------
780
    read_gml, generate_gml, literal_stringizer
781

782
    Notes
783
    -----
784
    Graph attributes named 'directed', 'multigraph', 'node' or
785
    'edge', node attributes named 'id' or 'label', edge attributes
786
    named 'source' or 'target' (or 'key' if `G` is a multigraph)
787
    are ignored because these attribute names are used to encode the graph
788
    structure.
789

790
    GML files are stored using a 7-bit ASCII encoding with any extended
791
    ASCII characters (iso8859-1) appearing as HTML character entities.
792
    Without specifying a `stringizer`/`destringizer`, the code is capable of
793
    handling `int`/`float`/`str`/`dict`/`list` data as required by the GML
794
    specification.  For other data types, you need to explicitly supply a
795
    `stringizer`/`destringizer`.
796

797
    Note that while we allow non-standard GML to be read from a file, we make
798
    sure to write GML format. In particular, underscores are not allowed in
799
    attribute names.
800
    For additional documentation on the GML file format, please see the
801
    `GML website <http://www.infosun.fim.uni-passau.de/Graphlet/GML/gml-tr.html>`_.
802

803
    See the module docstring :mod:`networkx.readwrite.gml` for more details.
804

805
    Examples
806
    --------
807
    >>> G = nx.path_graph(4)
808
    >>> nx.write_gml(G, "test.gml")
809

810
    Filenames ending in .gz or .bz2 will be compressed.
811

812
    >>> nx.write_gml(G, "test.gml.gz")
813
    """
814
    for line in generate_gml(G, stringizer):
815
        path.write((line + '\n').encode('ascii'))
816

    
817

    
818
# fixture for nose
819
def teardown_module(module):
820
    import os
821
    for fname in ['test.gml', 'test.gml.gz']:
822
        if os.path.isfile(fname):
823
            os.unlink(fname)