Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.4 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 *sparse6* format.
14

15
The *sparse6* file format is a space-efficient format for large sparse
16
graphs. For small graphs or large dense graphs, use the *graph6* file
17
format.
18

19
For more information, see the `sparse6`_ homepage.
20

21
.. _sparse6: http://users.cecs.anu.edu.au/~bdm/data/formats.html
22

23
"""
24
from itertools import chain
25
import math
26
import sys
27

    
28
import networkx as nx
29
from networkx.exception import NetworkXError
30
from networkx.utils import open_file, not_implemented_for
31
from networkx.readwrite.graph6 import data_to_n, n_to_data
32

    
33
__all__ = ['from_sparse6_bytes', 'read_sparse6', 'to_sparse6_bytes',
34
           'write_sparse6']
35

    
36

    
37
def _generate_sparse6_bytes(G, nodes, header):
38
    """Yield bytes in the sparse6 encoding of a graph.
39

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

46
    This function generates `bytes` objects in the following order:
47

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

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

57
    """
58
    n = len(G)
59
    if n >= 2 ** 36:
60
        raise ValueError('sparse6 is only defined if number of nodes is less '
61
                         'than 2 ** 36')
62
    if header:
63
        yield b'>>sparse6<<'
64
    yield b':'
65
    for d in n_to_data(n):
66
        yield str.encode(chr(d + 63))
67

    
68
    k = 1
69
    while 1 << k < n:
70
        k += 1
71

    
72
    def enc(x):
73
        """Big endian k-bit encoding of x"""
74
        return [1 if (x & 1 << (k - 1 - i)) else 0 for i in range(k)]
75

    
76
    edges = sorted((max(u, v), min(u, v)) for u, v in G.edges())
77
    bits = []
78
    curv = 0
79
    for (v, u) in edges:
80
        if v == curv:  # current vertex edge
81
            bits.append(0)
82
            bits.extend(enc(u))
83
        elif v == curv + 1:  # next vertex edge
84
            curv += 1
85
            bits.append(1)
86
            bits.extend(enc(u))
87
        else:  # skip to vertex v and then add edge to u
88
            curv = v
89
            bits.append(1)
90
            bits.extend(enc(v))
91
            bits.append(0)
92
            bits.extend(enc(u))
93
    if k < 6 and n == (1 << k) and ((-len(bits)) % 6) >= k and curv < (n - 1):
94
        # Padding special case: small k, n=2^k,
95
        # more than k bits of padding needed,
96
        # current vertex is not (n-1) --
97
        # appending 1111... would add a loop on (n-1)
98
        bits.append(0)
99
        bits.extend([1] * ((-len(bits)) % 6))
100
    else:
101
        bits.extend([1] * ((-len(bits)) % 6))
102

    
103
    data = [(bits[i + 0] << 5) + (bits[i + 1] << 4) + (bits[i + 2] << 3) + (bits[i + 3] << 2) +
104
            (bits[i + 4] << 1) + (bits[i + 5] << 0) for i in range(0, len(bits), 6)]
105

    
106
    for d in data:
107
        yield str.encode(chr(d + 63))
108
    yield b'\n'
109

    
110

    
111
def from_sparse6_bytes(string):
112
    """Read an undirected graph in sparse6 format from string.
113

114
    Parameters
115
    ----------
116
    string : string
117
       Data in sparse6 format
118

119
    Returns
120
    -------
121
    G : Graph
122

123
    Raises
124
    ------
125
    NetworkXError
126
        If the string is unable to be parsed in sparse6 format
127

128
    Examples
129
    --------
130
    >>> G = nx.from_sparse6_bytes(b':A_')
131
    >>> sorted(G.edges())
132
    [(0, 1), (0, 1), (0, 1)]
133

134
    See Also
135
    --------
136
    read_sparse6, write_sparse6
137

138
    References
139
    ----------
140
    .. [1] Sparse6 specification
141
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
142

143
    """
144
    if string.startswith(b'>>sparse6<<'):
145
        string = string[11:]
146
    if not string.startswith(b':'):
147
        raise NetworkXError('Expected leading colon in sparse6')
148

    
149
    if sys.version_info < (3, ):
150
        chars = [ord(c) - 63 for c in string[1:]]
151
    else:
152
        chars = [c - 63 for c in string[1:]]
153
    n, data = data_to_n(chars)
154
    k = 1
155
    while 1 << k < n:
156
        k += 1
157

    
158
    def parseData():
159
        """Returns stream of pairs b[i], x[i] for sparse6 format."""
160
        chunks = iter(data)
161
        d = None  # partial data word
162
        dLen = 0  # how many unparsed bits are left in d
163

    
164
        while 1:
165
            if dLen < 1:
166
                try:
167
                    d = next(chunks)
168
                except StopIteration:
169
                    return
170
                dLen = 6
171
            dLen -= 1
172
            b = (d >> dLen) & 1  # grab top remaining bit
173

    
174
            x = d & ((1 << dLen) - 1)  # partially built up value of x
175
            xLen = dLen                # how many bits included so far in x
176
            while xLen < k:  # now grab full chunks until we have enough
177
                try:
178
                    d = next(chunks)
179
                except StopIteration:
180
                    return
181
                dLen = 6
182
                x = (x << 6) + d
183
                xLen += 6
184
            x = (x >> (xLen - k))  # shift back the extra bits
185
            dLen = xLen - k
186
            yield b, x
187

    
188
    v = 0
189

    
190
    G = nx.MultiGraph()
191
    G.add_nodes_from(range(n))
192

    
193
    multigraph = False
194
    for b, x in parseData():
195
        if b == 1:
196
            v += 1
197
        # padding with ones can cause overlarge number here
198
        if x >= n or v >= n:
199
            break
200
        elif x > v:
201
            v = x
202
        else:
203
            if G.has_edge(x, v):
204
                multigraph = True
205
            G.add_edge(x, v)
206
    if not multigraph:
207
        G = nx.Graph(G)
208
    return G
209

    
210

    
211
def to_sparse6_bytes(G, nodes=None, header=True):
212
    """Convert an undirected graph to bytes in sparse6 format.
213

214
    Parameters
215
    ----------
216
    G : Graph (undirected)
217

218
    nodes: list or iterable
219
       Nodes are labeled 0...n-1 in the order provided.  If None the ordering
220
       given by ``G.nodes()`` is used.
221

222
    header: bool
223
       If True add '>>sparse6<<' bytes to head of data.
224

225
    Raises
226
    ------
227
    NetworkXNotImplemented
228
        If the graph is directed.
229

230
    ValueError
231
        If the graph has at least ``2 ** 36`` nodes; the sparse6 format
232
        is only defined for graphs of order less than ``2 ** 36``.
233

234
    Examples
235
    --------
236
    >>> nx.to_sparse6_bytes(nx.path_graph(2))  # doctest: +SKIP
237
    b'>>sparse6<<:An\\n'
238

239
    See Also
240
    --------
241
    to_sparse6_bytes, read_sparse6, write_sparse6_bytes
242

243
    Notes
244
    -----
245
    The returned bytes end with a newline character.
246

247
    The format does not support edge or node labels.
248

249
    References
250
    ----------
251
    .. [1] Graph6 specification
252
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
253

254
    """
255
    if nodes is not None:
256
        G = G.subgraph(nodes)
257
    G = nx.convert_node_labels_to_integers(G, ordering='sorted')
258
    return b''.join(_generate_sparse6_bytes(G, nodes, header))
259

    
260

    
261
@open_file(0, mode='rb')
262
def read_sparse6(path):
263
    """Read an undirected graph in sparse6 format from path.
264

265
    Parameters
266
    ----------
267
    path : file or string
268
       File or filename to write.
269

270
    Returns
271
    -------
272
    G : Graph/Multigraph or list of Graphs/MultiGraphs
273
       If the file contains multiple lines then a list of graphs is returned
274

275
    Raises
276
    ------
277
    NetworkXError
278
        If the string is unable to be parsed in sparse6 format
279

280
    Examples
281
    --------
282
    You can read a sparse6 file by giving the path to the file::
283

284
        >>> import tempfile
285
        >>> with tempfile.NamedTemporaryFile() as f:
286
        ...     _ = f.write(b'>>sparse6<<:An\\n')
287
        ...     _ = f.seek(0)
288
        ...     G = nx.read_sparse6(f.name)
289
        >>> list(G.edges())
290
        [(0, 1)]
291

292
    You can also read a sparse6 file by giving an open file-like object::
293

294
        >>> import tempfile
295
        >>> with tempfile.NamedTemporaryFile() as f:
296
        ...     _ = f.write(b'>>sparse6<<:An\\n')
297
        ...     _ = f.seek(0)
298
        ...     G = nx.read_sparse6(f)
299
        >>> list(G.edges())
300
        [(0, 1)]
301

302
    See Also
303
    --------
304
    read_sparse6, from_sparse6_bytes
305

306
    References
307
    ----------
308
    .. [1] Sparse6 specification
309
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
310

311
    """
312
    glist = []
313
    for line in path:
314
        line = line.strip()
315
        if not len(line):
316
            continue
317
        glist.append(from_sparse6_bytes(line))
318
    if len(glist) == 1:
319
        return glist[0]
320
    else:
321
        return glist
322

    
323

    
324
@not_implemented_for('directed')
325
@open_file(1, mode='wb')
326
def write_sparse6(G, path, nodes=None, header=True):
327
    """Write graph G to given path in sparse6 format.
328

329
    Parameters
330
    ----------
331
    G : Graph (undirected)
332

333
    path : file or string
334
       File or filename to write
335

336
    nodes: list or iterable
337
       Nodes are labeled 0...n-1 in the order provided.  If None the ordering
338
       given by G.nodes() is used.
339

340
    header: bool
341
       If True add '>>sparse6<<' string to head of data
342

343
    Raises
344
    ------
345
    NetworkXError
346
        If the graph is directed
347

348
    Examples
349
    --------
350
    You can write a sparse6 file by giving the path to the file::
351

352
        >>> import tempfile
353
        >>> with tempfile.NamedTemporaryFile() as f:
354
        ...     nx.write_sparse6(nx.path_graph(2), f.name)
355
        ...     print(f.read())  # doctest: +SKIP
356
        b'>>sparse6<<:An\\n'
357

358
    You can also write a sparse6 file by giving an open file-like object::
359

360
        >>> with tempfile.NamedTemporaryFile() as f:
361
        ...     nx.write_sparse6(nx.path_graph(2), f)
362
        ...     _ = f.seek(0)
363
        ...     print(f.read())  # doctest: +SKIP
364
        b'>>sparse6<<:An\\n'
365

366
    See Also
367
    --------
368
    read_sparse6, from_sparse6_bytes
369

370
    Notes
371
    -----
372
    The format does not support edge or node labels.
373

374
    References
375
    ----------
376
    .. [1] Sparse6 specification
377
           <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
378

379
    """
380
    if nodes is not None:
381
        G = G.subgraph(nodes)
382
    G = nx.convert_node_labels_to_integers(G, ordering='sorted')
383
    for b in _generate_sparse6_bytes(G, nodes, header):
384
        path.write(b)