Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/readwrite/graph6.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
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 """Functions for reading and writing graphs in the *graph6* format. | |
4 | |
5 The *graph6* file format is suitable for small graphs or large dense | |
6 graphs. For large sparse graphs, use the *sparse6* format. | |
7 | |
8 For more information, see the `graph6`_ homepage. | |
9 | |
10 .. _graph6: http://users.cecs.anu.edu.au/~bdm/data/formats.html | |
11 | |
12 """ | |
13 from itertools import islice | |
14 | |
15 import networkx as nx | |
16 from networkx.exception import NetworkXError | |
17 from networkx.utils import open_file, not_implemented_for | |
18 | |
19 __all__ = ["from_graph6_bytes", "read_graph6", "to_graph6_bytes", "write_graph6"] | |
20 | |
21 | |
22 def _generate_graph6_bytes(G, nodes, header): | |
23 """Yield bytes in the graph6 encoding of a graph. | |
24 | |
25 `G` is an undirected simple graph. `nodes` is the list of nodes for | |
26 which the node-induced subgraph will be encoded; if `nodes` is the | |
27 list of all nodes in the graph, the entire graph will be | |
28 encoded. `header` is a Boolean that specifies whether to generate | |
29 the header ``b'>>graph6<<'`` before the remaining data. | |
30 | |
31 This function generates `bytes` objects in the following order: | |
32 | |
33 1. the header (if requested), | |
34 2. the encoding of the number of nodes, | |
35 3. each character, one-at-a-time, in the encoding of the requested | |
36 node-induced subgraph, | |
37 4. a newline character. | |
38 | |
39 This function raises :exc:`ValueError` if the graph is too large for | |
40 the graph6 format (that is, greater than ``2 ** 36`` nodes). | |
41 | |
42 """ | |
43 n = len(G) | |
44 if n >= 2 ** 36: | |
45 raise ValueError( | |
46 "graph6 is only defined if number of nodes is less " "than 2 ** 36" | |
47 ) | |
48 if header: | |
49 yield b">>graph6<<" | |
50 for d in n_to_data(n): | |
51 yield str.encode(chr(d + 63)) | |
52 # This generates the same as `(v in G[u] for u, v in combinations(G, 2))`, | |
53 # but in "column-major" order instead of "row-major" order. | |
54 bits = (nodes[j] in G[nodes[i]] for j in range(1, n) for i in range(j)) | |
55 chunk = list(islice(bits, 6)) | |
56 while chunk: | |
57 d = sum(b << 5 - i for i, b in enumerate(chunk)) | |
58 yield str.encode(chr(d + 63)) | |
59 chunk = list(islice(bits, 6)) | |
60 yield b"\n" | |
61 | |
62 | |
63 def from_graph6_bytes(bytes_in): | |
64 """Read a simple undirected graph in graph6 format from bytes. | |
65 | |
66 Parameters | |
67 ---------- | |
68 bytes_in : bytes | |
69 Data in graph6 format, without a trailing newline. | |
70 | |
71 Returns | |
72 ------- | |
73 G : Graph | |
74 | |
75 Raises | |
76 ------ | |
77 NetworkXError | |
78 If bytes_in is unable to be parsed in graph6 format | |
79 | |
80 ValueError | |
81 If any character ``c`` in bytes_in does not satisfy | |
82 ``63 <= ord(c) < 127``. | |
83 | |
84 Examples | |
85 -------- | |
86 >>> G = nx.from_graph6_bytes(b"A_") | |
87 >>> sorted(G.edges()) | |
88 [(0, 1)] | |
89 | |
90 See Also | |
91 -------- | |
92 read_graph6, write_graph6 | |
93 | |
94 References | |
95 ---------- | |
96 .. [1] Graph6 specification | |
97 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
98 | |
99 """ | |
100 | |
101 def bits(): | |
102 """Returns sequence of individual bits from 6-bit-per-value | |
103 list of data values.""" | |
104 for d in data: | |
105 for i in [5, 4, 3, 2, 1, 0]: | |
106 yield (d >> i) & 1 | |
107 | |
108 if bytes_in.startswith(b">>graph6<<"): | |
109 bytes_in = bytes_in[10:] | |
110 | |
111 data = [c - 63 for c in bytes_in] | |
112 if any(c > 63 for c in data): | |
113 raise ValueError("each input character must be in range(63, 127)") | |
114 | |
115 n, data = data_to_n(data) | |
116 nd = (n * (n - 1) // 2 + 5) // 6 | |
117 if len(data) != nd: | |
118 raise NetworkXError( | |
119 f"Expected {n * (n - 1) // 2} bits but got {len(data) * 6} in graph6" | |
120 ) | |
121 | |
122 G = nx.Graph() | |
123 G.add_nodes_from(range(n)) | |
124 for (i, j), b in zip([(i, j) for j in range(1, n) for i in range(j)], bits()): | |
125 if b: | |
126 G.add_edge(i, j) | |
127 | |
128 return G | |
129 | |
130 | |
131 def to_graph6_bytes(G, nodes=None, header=True): | |
132 """Convert a simple undirected graph to bytes in graph6 format. | |
133 | |
134 Parameters | |
135 ---------- | |
136 G : Graph (undirected) | |
137 | |
138 nodes: list or iterable | |
139 Nodes are labeled 0...n-1 in the order provided. If None the ordering | |
140 given by ``G.nodes()`` is used. | |
141 | |
142 header: bool | |
143 If True add '>>graph6<<' bytes to head of data. | |
144 | |
145 Raises | |
146 ------ | |
147 NetworkXNotImplemented | |
148 If the graph is directed or is a multigraph. | |
149 | |
150 ValueError | |
151 If the graph has at least ``2 ** 36`` nodes; the graph6 format | |
152 is only defined for graphs of order less than ``2 ** 36``. | |
153 | |
154 Examples | |
155 -------- | |
156 >>> nx.to_graph6_bytes(nx.path_graph(2)) | |
157 b'>>graph6<<A_\\n' | |
158 | |
159 See Also | |
160 -------- | |
161 from_graph6_bytes, read_graph6, write_graph6_bytes | |
162 | |
163 Notes | |
164 ----- | |
165 The returned bytes end with a newline character. | |
166 | |
167 The format does not support edge or node labels, parallel edges or | |
168 self loops. If self loops are present they are silently ignored. | |
169 | |
170 References | |
171 ---------- | |
172 .. [1] Graph6 specification | |
173 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
174 | |
175 """ | |
176 if nodes is not None: | |
177 G = G.subgraph(nodes) | |
178 H = nx.convert_node_labels_to_integers(G) | |
179 nodes = sorted(H.nodes()) | |
180 return b"".join(_generate_graph6_bytes(H, nodes, header)) | |
181 | |
182 | |
183 @open_file(0, mode="rb") | |
184 def read_graph6(path): | |
185 """Read simple undirected graphs in graph6 format from path. | |
186 | |
187 Parameters | |
188 ---------- | |
189 path : file or string | |
190 File or filename to write. | |
191 | |
192 Returns | |
193 ------- | |
194 G : Graph or list of Graphs | |
195 If the file contains multiple lines then a list of graphs is returned | |
196 | |
197 Raises | |
198 ------ | |
199 NetworkXError | |
200 If the string is unable to be parsed in graph6 format | |
201 | |
202 Examples | |
203 -------- | |
204 You can read a graph6 file by giving the path to the file:: | |
205 | |
206 >>> import tempfile | |
207 >>> with tempfile.NamedTemporaryFile() as f: | |
208 ... _ = f.write(b">>graph6<<A_\\n") | |
209 ... _ = f.seek(0) | |
210 ... G = nx.read_graph6(f.name) | |
211 >>> list(G.edges()) | |
212 [(0, 1)] | |
213 | |
214 You can also read a graph6 file by giving an open file-like object:: | |
215 | |
216 >>> import tempfile | |
217 >>> with tempfile.NamedTemporaryFile() as f: | |
218 ... _ = f.write(b">>graph6<<A_\\n") | |
219 ... _ = f.seek(0) | |
220 ... G = nx.read_graph6(f) | |
221 >>> list(G.edges()) | |
222 [(0, 1)] | |
223 | |
224 See Also | |
225 -------- | |
226 from_graph6_bytes, write_graph6 | |
227 | |
228 References | |
229 ---------- | |
230 .. [1] Graph6 specification | |
231 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
232 | |
233 """ | |
234 glist = [] | |
235 for line in path: | |
236 line = line.strip() | |
237 if not len(line): | |
238 continue | |
239 glist.append(from_graph6_bytes(line)) | |
240 if len(glist) == 1: | |
241 return glist[0] | |
242 else: | |
243 return glist | |
244 | |
245 | |
246 @not_implemented_for("directed") | |
247 @not_implemented_for("multigraph") | |
248 @open_file(1, mode="wb") | |
249 def write_graph6(G, path, nodes=None, header=True): | |
250 """Write a simple undirected graph to a path in graph6 format. | |
251 | |
252 Parameters | |
253 ---------- | |
254 G : Graph (undirected) | |
255 | |
256 path : str | |
257 The path naming the file to which to write the graph. | |
258 | |
259 nodes: list or iterable | |
260 Nodes are labeled 0...n-1 in the order provided. If None the ordering | |
261 given by ``G.nodes()`` is used. | |
262 | |
263 header: bool | |
264 If True add '>>graph6<<' string to head of data | |
265 | |
266 Raises | |
267 ------ | |
268 NetworkXNotImplemented | |
269 If the graph is directed or is a multigraph. | |
270 | |
271 ValueError | |
272 If the graph has at least ``2 ** 36`` nodes; the graph6 format | |
273 is only defined for graphs of order less than ``2 ** 36``. | |
274 | |
275 Examples | |
276 -------- | |
277 You can write a graph6 file by giving the path to a file:: | |
278 | |
279 >>> import tempfile | |
280 >>> with tempfile.NamedTemporaryFile() as f: | |
281 ... nx.write_graph6(nx.path_graph(2), f.name) | |
282 ... _ = f.seek(0) | |
283 ... print(f.read()) | |
284 b'>>graph6<<A_\\n' | |
285 | |
286 See Also | |
287 -------- | |
288 from_graph6_bytes, read_graph6 | |
289 | |
290 Notes | |
291 ----- | |
292 The function writes a newline character after writing the encoding | |
293 of the graph. | |
294 | |
295 The format does not support edge or node labels, parallel edges or | |
296 self loops. If self loops are present they are silently ignored. | |
297 | |
298 References | |
299 ---------- | |
300 .. [1] Graph6 specification | |
301 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
302 | |
303 """ | |
304 return write_graph6_file(G, path, nodes=nodes, header=header) | |
305 | |
306 | |
307 @not_implemented_for("directed") | |
308 @not_implemented_for("multigraph") | |
309 def write_graph6_file(G, f, nodes=None, header=True): | |
310 """Write a simple undirected graph to a file-like object in graph6 format. | |
311 | |
312 Parameters | |
313 ---------- | |
314 G : Graph (undirected) | |
315 | |
316 f : file-like object | |
317 The file to write. | |
318 | |
319 nodes: list or iterable | |
320 Nodes are labeled 0...n-1 in the order provided. If None the ordering | |
321 given by ``G.nodes()`` is used. | |
322 | |
323 header: bool | |
324 If True add '>>graph6<<' string to head of data | |
325 | |
326 Raises | |
327 ------ | |
328 NetworkXNotImplemented | |
329 If the graph is directed or is a multigraph. | |
330 | |
331 ValueError | |
332 If the graph has at least ``2 ** 36`` nodes; the graph6 format | |
333 is only defined for graphs of order less than ``2 ** 36``. | |
334 | |
335 Examples | |
336 -------- | |
337 You can write a graph6 file by giving an open file-like object:: | |
338 | |
339 >>> import tempfile | |
340 >>> with tempfile.NamedTemporaryFile() as f: | |
341 ... nx.write_graph6(nx.path_graph(2), f) | |
342 ... _ = f.seek(0) | |
343 ... print(f.read()) | |
344 b'>>graph6<<A_\\n' | |
345 | |
346 See Also | |
347 -------- | |
348 from_graph6_bytes, read_graph6 | |
349 | |
350 Notes | |
351 ----- | |
352 The function writes a newline character after writing the encoding | |
353 of the graph. | |
354 | |
355 The format does not support edge or node labels, parallel edges or | |
356 self loops. If self loops are present they are silently ignored. | |
357 | |
358 References | |
359 ---------- | |
360 .. [1] Graph6 specification | |
361 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
362 | |
363 """ | |
364 if nodes is not None: | |
365 G = G.subgraph(nodes) | |
366 H = nx.convert_node_labels_to_integers(G) | |
367 nodes = sorted(H.nodes()) | |
368 for b in _generate_graph6_bytes(H, nodes, header): | |
369 f.write(b) | |
370 | |
371 | |
372 def data_to_n(data): | |
373 """Read initial one-, four- or eight-unit value from graph6 | |
374 integer sequence. | |
375 | |
376 Return (value, rest of seq.)""" | |
377 if data[0] <= 62: | |
378 return data[0], data[1:] | |
379 if data[1] <= 62: | |
380 return (data[1] << 12) + (data[2] << 6) + data[3], data[4:] | |
381 return ( | |
382 (data[2] << 30) | |
383 + (data[3] << 24) | |
384 + (data[4] << 18) | |
385 + (data[5] << 12) | |
386 + (data[6] << 6) | |
387 + data[7], | |
388 data[8:], | |
389 ) | |
390 | |
391 | |
392 def n_to_data(n): | |
393 """Convert an integer to one-, four- or eight-unit graph6 sequence. | |
394 | |
395 This function is undefined if `n` is not in ``range(2 ** 36)``. | |
396 | |
397 """ | |
398 if n <= 62: | |
399 return [n] | |
400 elif n <= 258047: | |
401 return [63, (n >> 12) & 0x3F, (n >> 6) & 0x3F, n & 0x3F] | |
402 else: # if n <= 68719476735: | |
403 return [ | |
404 63, | |
405 63, | |
406 (n >> 30) & 0x3F, | |
407 (n >> 24) & 0x3F, | |
408 (n >> 18) & 0x3F, | |
409 (n >> 12) & 0x3F, | |
410 (n >> 6) & 0x3F, | |
411 n & 0x3F, | |
412 ] |