Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/readwrite/graph6.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 *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]