Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.3 KB)

1
# Original author: D. Eppstein, UC Irvine, August 12, 2003.
2
# The original code at http://www.ics.uci.edu/~eppstein/PADS/ is public domain.
3
#    Copyright (C) 2004-2019 by
4
#    Aric Hagberg <hagberg@lanl.gov>
5
#    Dan Schult <dschult@colgate.edu>
6
#    Pieter Swart <swart@lanl.gov>
7
#    Tomas Gavenciak <gavento@ucw.cz>
8
#    All rights reserved.
9
#    BSD license.
10
#
11
# Authors: Tomas Gavenciak <gavento@ucw.cz>
12
#          Aric Hagberg <aric.hagberg@lanl.gov>
13
"""Functions for reading and writing graphs in the *graph6* format.
14

15
The *graph6* file format is suitable for small graphs or large dense
16
graphs. For large sparse graphs, use the *sparse6* format.
17

18
For more information, see the `graph6`_ homepage.
19

20
.. _graph6: http://users.cecs.anu.edu.au/~bdm/data/formats.html
21

22
"""
23
from itertools import islice
24
import sys
25

    
26
import networkx as nx
27
from networkx.exception import NetworkXError
28
from networkx.utils import open_file, not_implemented_for
29

    
30
__all__ = ['from_graph6_bytes', 'read_graph6', 'to_graph6_bytes',
31
           'write_graph6']
32

    
33

    
34
def _generate_graph6_bytes(G, nodes, header):
35
    """Yield bytes in the graph6 encoding of a graph.
36

37
    `G` is an undirected simple graph. `nodes` is the list of nodes for
38
    which the node-induced subgraph will be encoded; if `nodes` is the
39
    list of all nodes in the graph, the entire graph will be
40
    encoded. `header` is a Boolean that specifies whether to generate
41
    the header ``b'>>graph6<<'`` before the remaining data.
42

43
    This function generates `bytes` objects in the following order:
44

45
    1. the header (if requested),
46
    2. the encoding of the number of nodes,
47
    3. each character, one-at-a-time, in the encoding of the requested
48
       node-induced subgraph,
49
    4. a newline character.
50

51
    This function raises :exc:`ValueError` if the graph is too large for
52
    the graph6 format (that is, greater than ``2 ** 36`` nodes).
53

54
    """
55
    n = len(G)
56
    if n >= 2 ** 36:
57
        raise ValueError('graph6 is only defined if number of nodes is less '
58
                         'than 2 ** 36')
59
    if header:
60
        yield b'>>graph6<<'
61
    for d in n_to_data(n):
62
        yield str.encode(chr(d + 63))
63
    # This generates the same as `(v in G[u] for u, v in combinations(G, 2))`,
64
    # but in "column-major" order instead of "row-major" order.
65
    bits = (nodes[j] in G[nodes[i]] for j in range(1, n) for i in range(j))
66
    chunk = list(islice(bits, 6))
67
    while chunk:
68
        d = sum(b << 5 - i for i, b in enumerate(chunk))
69
        yield str.encode(chr(d + 63))
70
        chunk = list(islice(bits, 6))
71
    yield b'\n'
72

    
73

    
74
def from_graph6_bytes(string):
75
    """Read a simple undirected graph in graph6 format from string.
76

77
    Parameters
78
    ----------
79
    string : string
80
       Data in graph6 format, without a trailing newline.
81

82
    Returns
83
    -------
84
    G : Graph
85

86
    Raises
87
    ------
88
    NetworkXError
89
        If the string is unable to be parsed in graph6 format
90

91
    ValueError
92
        If any character ``c`` in the input string does not satisfy
93
        ``63 <= ord(c) < 127``.
94

95
    Examples
96
    --------
97
    >>> G = nx.from_graph6_bytes(b'A_')
98
    >>> sorted(G.edges())
99
    [(0, 1)]
100

101
    See Also
102
    --------
103
    read_graph6, write_graph6
104

105
    References
106
    ----------
107
    .. [1] Graph6 specification
108
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
109

110
    """
111
    def bits():
112
        """Returns sequence of individual bits from 6-bit-per-value
113
        list of data values."""
114
        for d in data:
115
            for i in [5, 4, 3, 2, 1, 0]:
116
                yield (d >> i) & 1
117

    
118
    if string.startswith(b'>>graph6<<'):
119
        string = string[10:]
120

    
121
    if sys.version_info < (3, ):
122
        data = [ord(c) - 63 for c in string]
123
    else:
124
        data = [c - 63 for c in string]
125
    if any(c > 63 for c in data):
126
        raise ValueError('each input character must be in range(63, 127)')
127

    
128
    n, data = data_to_n(data)
129
    nd = (n * (n - 1) // 2 + 5) // 6
130
    if len(data) != nd:
131
        raise NetworkXError(
132
            'Expected %d bits but got %d in graph6' % (n * (n - 1) // 2, len(data) * 6))
133

    
134
    G = nx.Graph()
135
    G.add_nodes_from(range(n))
136
    for (i, j), b in zip([(i, j) for j in range(1, n) for i in range(j)], bits()):
137
        if b:
138
            G.add_edge(i, j)
139

    
140
    return G
141

    
142

    
143
def to_graph6_bytes(G, nodes=None, header=True):
144
    """Convert a simple undirected graph to bytes in graph6 format.
145

146
    Parameters
147
    ----------
148
    G : Graph (undirected)
149

150
    nodes: list or iterable
151
       Nodes are labeled 0...n-1 in the order provided.  If None the ordering
152
       given by ``G.nodes()`` is used.
153

154
    header: bool
155
       If True add '>>graph6<<' bytes to head of data.
156

157
    Raises
158
    ------
159
    NetworkXNotImplemented
160
        If the graph is directed or is a multigraph.
161

162
    ValueError
163
        If the graph has at least ``2 ** 36`` nodes; the graph6 format
164
        is only defined for graphs of order less than ``2 ** 36``.
165

166
    Examples
167
    --------
168
    >>> nx.to_graph6_bytes(nx.path_graph(2)) # doctest: +SKIP
169
    b'>>graph6<<A_\\n'
170

171
    See Also
172
    --------
173
    from_graph6_bytes, read_graph6, write_graph6_bytes
174

175
    Notes
176
    -----
177
    The returned bytes end with a newline character.
178

179
    The format does not support edge or node labels, parallel edges or
180
    self loops. If self loops are present they are silently ignored.
181

182
    References
183
    ----------
184
    .. [1] Graph6 specification
185
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
186

187
    """
188
    if nodes is not None:
189
        G = G.subgraph(nodes)
190
    H = nx.convert_node_labels_to_integers(G)
191
    nodes = sorted(H.nodes())
192
    return b''.join(_generate_graph6_bytes(H, nodes, header))
193

    
194

    
195
@open_file(0, mode='rb')
196
def read_graph6(path):
197
    """Read simple undirected graphs in graph6 format from path.
198

199
    Parameters
200
    ----------
201
    path : file or string
202
       File or filename to write.
203

204
    Returns
205
    -------
206
    G : Graph or list of Graphs
207
       If the file contains multiple lines then a list of graphs is returned
208

209
    Raises
210
    ------
211
    NetworkXError
212
        If the string is unable to be parsed in graph6 format
213

214
    Examples
215
    --------
216
    You can read a graph6 file by giving the path to the file::
217

218
        >>> import tempfile
219
        >>> with tempfile.NamedTemporaryFile() as f:
220
        ...     _ = f.write(b'>>graph6<<A_\\n')
221
        ...     _ = f.seek(0)
222
        ...     G = nx.read_graph6(f.name)
223
        >>> list(G.edges())
224
        [(0, 1)]
225

226
    You can also read a graph6 file by giving an open file-like object::
227

228
        >>> import tempfile
229
        >>> with tempfile.NamedTemporaryFile() as f:
230
        ...     _ = f.write(b'>>graph6<<A_\\n')
231
        ...     _ = f.seek(0)
232
        ...     G = nx.read_graph6(f)
233
        >>> list(G.edges())
234
        [(0, 1)]
235

236
    See Also
237
    --------
238
    from_graph6_bytes, write_graph6
239

240
    References
241
    ----------
242
    .. [1] Graph6 specification
243
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
244

245
    """
246
    glist = []
247
    for line in path:
248
        line = line.strip()
249
        if not len(line):
250
            continue
251
        glist.append(from_graph6_bytes(line))
252
    if len(glist) == 1:
253
        return glist[0]
254
    else:
255
        return glist
256

    
257

    
258
@not_implemented_for('directed')
259
@not_implemented_for('multigraph')
260
@open_file(1, mode='wb')
261
def write_graph6(G, path, nodes=None, header=True):
262
    """Write a simple undirected graph to a path in graph6 format.
263

264
    Parameters
265
    ----------
266
    G : Graph (undirected)
267

268
    path : str
269
       The path naming the file to which to write the graph.
270

271
    nodes: list or iterable
272
       Nodes are labeled 0...n-1 in the order provided.  If None the ordering
273
       given by ``G.nodes()`` is used.
274

275
    header: bool
276
       If True add '>>graph6<<' string to head of data
277

278
    Raises
279
    ------
280
    NetworkXNotImplemented
281
        If the graph is directed or is a multigraph.
282

283
    ValueError
284
        If the graph has at least ``2 ** 36`` nodes; the graph6 format
285
        is only defined for graphs of order less than ``2 ** 36``.
286

287
    Examples
288
    --------
289
    You can write a graph6 file by giving the path to a file::
290

291
        >>> import tempfile
292
        >>> with tempfile.NamedTemporaryFile() as f:
293
        ...     nx.write_graph6(nx.path_graph(2), f.name)
294
        ...     _ = f.seek(0)
295
        ...     print(f.read())  # doctest: +SKIP
296
        b'>>graph6<<A_\\n'
297

298
    See Also
299
    --------
300
    from_graph6_bytes, read_graph6
301

302
    Notes
303
    -----
304
    The function writes a newline character after writing the encoding
305
    of the graph.
306

307
    The format does not support edge or node labels, parallel edges or
308
    self loops.  If self loops are present they are silently ignored.
309

310
    References
311
    ----------
312
    .. [1] Graph6 specification
313
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
314

315
    """
316
    return write_graph6_file(G, path, nodes=nodes, header=header)
317

    
318

    
319
@not_implemented_for('directed')
320
@not_implemented_for('multigraph')
321
def write_graph6_file(G, f, nodes=None, header=True):
322
    """Write a simple undirected graph to a file-like object in graph6 format.
323

324
    Parameters
325
    ----------
326
    G : Graph (undirected)
327

328
    f : file-like object
329
       The file to write.
330

331
    nodes: list or iterable
332
       Nodes are labeled 0...n-1 in the order provided.  If None the ordering
333
       given by ``G.nodes()`` is used.
334

335
    header: bool
336
       If True add '>>graph6<<' string to head of data
337

338
    Raises
339
    ------
340
    NetworkXNotImplemented
341
        If the graph is directed or is a multigraph.
342

343
    ValueError
344
        If the graph has at least ``2 ** 36`` nodes; the graph6 format
345
        is only defined for graphs of order less than ``2 ** 36``.
346

347
    Examples
348
    --------
349
    You can write a graph6 file by giving an open file-like object::
350

351
        >>> import tempfile
352
        >>> with tempfile.NamedTemporaryFile() as f:
353
        ...     nx.write_graph6(nx.path_graph(2), f)
354
        ...     _ = f.seek(0)
355
        ...     print(f.read())  # doctest: +SKIP
356
        b'>>graph6<<A_\\n'
357

358
    See Also
359
    --------
360
    from_graph6_bytes, read_graph6
361

362
    Notes
363
    -----
364
    The function writes a newline character after writing the encoding
365
    of the graph.
366

367
    The format does not support edge or node labels, parallel edges or
368
    self loops.  If self loops are present they are silently ignored.
369

370
    References
371
    ----------
372
    .. [1] Graph6 specification
373
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
374

375
    """
376
    if nodes is not None:
377
        G = G.subgraph(nodes)
378
    H = nx.convert_node_labels_to_integers(G)
379
    nodes = sorted(H.nodes())
380
    for b in _generate_graph6_bytes(H, nodes, header):
381
        f.write(b)
382

    
383

    
384
def data_to_n(data):
385
    """Read initial one-, four- or eight-unit value from graph6
386
    integer sequence.
387

388
    Return (value, rest of seq.)"""
389
    if data[0] <= 62:
390
        return data[0], data[1:]
391
    if data[1] <= 62:
392
        return (data[1] << 12) + (data[2] << 6) + data[3], data[4:]
393
    return ((data[2] << 30) + (data[3] << 24) + (data[4] << 18) +
394
            (data[5] << 12) + (data[6] << 6) + data[7], data[8:])
395

    
396

    
397
def n_to_data(n):
398
    """Convert an integer to one-, four- or eight-unit graph6 sequence.
399

400
    This function is undefined if `n` is not in ``range(2 ** 36)``.
401

402
    """
403
    if n <= 62:
404
        return [n]
405
    elif n <= 258047:
406
        return [63, (n >> 12) & 0x3f, (n >> 6) & 0x3f, n & 0x3f]
407
    else:  # if n <= 68719476735:
408
        return [63, 63,
409
                (n >> 30) & 0x3f, (n >> 24) & 0x3f, (n >> 18) & 0x3f,
410
                (n >> 12) & 0x3f, (n >> 6) & 0x3f, n & 0x3f]