Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/readwrite/sparse6.py @ 0:26e78fe6e8c4 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit c699937486c35866861690329de38ec1a5d9f783"
author shellac
date Sat, 02 May 2020 07:14:21 -0400
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:26e78fe6e8c4
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)