Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/readwrite/sparse6.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 *sparse6* format. | |
4 | |
5 The *sparse6* file format is a space-efficient format for large sparse | |
6 graphs. For small graphs or large dense graphs, use the *graph6* file | |
7 format. | |
8 | |
9 For more information, see the `sparse6`_ homepage. | |
10 | |
11 .. _sparse6: http://users.cecs.anu.edu.au/~bdm/data/formats.html | |
12 | |
13 """ | |
14 import networkx as nx | |
15 from networkx.exception import NetworkXError | |
16 from networkx.utils import open_file, not_implemented_for | |
17 from networkx.readwrite.graph6 import data_to_n, n_to_data | |
18 | |
19 __all__ = ["from_sparse6_bytes", "read_sparse6", "to_sparse6_bytes", "write_sparse6"] | |
20 | |
21 | |
22 def _generate_sparse6_bytes(G, nodes, header): | |
23 """Yield bytes in the sparse6 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'>>sparse6<<'`` 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 "sparse6 is only defined if number of nodes is less " "than 2 ** 36" | |
47 ) | |
48 if header: | |
49 yield b">>sparse6<<" | |
50 yield b":" | |
51 for d in n_to_data(n): | |
52 yield str.encode(chr(d + 63)) | |
53 | |
54 k = 1 | |
55 while 1 << k < n: | |
56 k += 1 | |
57 | |
58 def enc(x): | |
59 """Big endian k-bit encoding of x""" | |
60 return [1 if (x & 1 << (k - 1 - i)) else 0 for i in range(k)] | |
61 | |
62 edges = sorted((max(u, v), min(u, v)) for u, v in G.edges()) | |
63 bits = [] | |
64 curv = 0 | |
65 for (v, u) in edges: | |
66 if v == curv: # current vertex edge | |
67 bits.append(0) | |
68 bits.extend(enc(u)) | |
69 elif v == curv + 1: # next vertex edge | |
70 curv += 1 | |
71 bits.append(1) | |
72 bits.extend(enc(u)) | |
73 else: # skip to vertex v and then add edge to u | |
74 curv = v | |
75 bits.append(1) | |
76 bits.extend(enc(v)) | |
77 bits.append(0) | |
78 bits.extend(enc(u)) | |
79 if k < 6 and n == (1 << k) and ((-len(bits)) % 6) >= k and curv < (n - 1): | |
80 # Padding special case: small k, n=2^k, | |
81 # more than k bits of padding needed, | |
82 # current vertex is not (n-1) -- | |
83 # appending 1111... would add a loop on (n-1) | |
84 bits.append(0) | |
85 bits.extend([1] * ((-len(bits)) % 6)) | |
86 else: | |
87 bits.extend([1] * ((-len(bits)) % 6)) | |
88 | |
89 data = [ | |
90 (bits[i + 0] << 5) | |
91 + (bits[i + 1] << 4) | |
92 + (bits[i + 2] << 3) | |
93 + (bits[i + 3] << 2) | |
94 + (bits[i + 4] << 1) | |
95 + (bits[i + 5] << 0) | |
96 for i in range(0, len(bits), 6) | |
97 ] | |
98 | |
99 for d in data: | |
100 yield str.encode(chr(d + 63)) | |
101 yield b"\n" | |
102 | |
103 | |
104 def from_sparse6_bytes(string): | |
105 """Read an undirected graph in sparse6 format from string. | |
106 | |
107 Parameters | |
108 ---------- | |
109 string : string | |
110 Data in sparse6 format | |
111 | |
112 Returns | |
113 ------- | |
114 G : Graph | |
115 | |
116 Raises | |
117 ------ | |
118 NetworkXError | |
119 If the string is unable to be parsed in sparse6 format | |
120 | |
121 Examples | |
122 -------- | |
123 >>> G = nx.from_sparse6_bytes(b":A_") | |
124 >>> sorted(G.edges()) | |
125 [(0, 1), (0, 1), (0, 1)] | |
126 | |
127 See Also | |
128 -------- | |
129 read_sparse6, write_sparse6 | |
130 | |
131 References | |
132 ---------- | |
133 .. [1] Sparse6 specification | |
134 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
135 | |
136 """ | |
137 if string.startswith(b">>sparse6<<"): | |
138 string = string[11:] | |
139 if not string.startswith(b":"): | |
140 raise NetworkXError("Expected leading colon in sparse6") | |
141 | |
142 chars = [c - 63 for c in string[1:]] | |
143 n, data = data_to_n(chars) | |
144 k = 1 | |
145 while 1 << k < n: | |
146 k += 1 | |
147 | |
148 def parseData(): | |
149 """Returns stream of pairs b[i], x[i] for sparse6 format.""" | |
150 chunks = iter(data) | |
151 d = None # partial data word | |
152 dLen = 0 # how many unparsed bits are left in d | |
153 | |
154 while 1: | |
155 if dLen < 1: | |
156 try: | |
157 d = next(chunks) | |
158 except StopIteration: | |
159 return | |
160 dLen = 6 | |
161 dLen -= 1 | |
162 b = (d >> dLen) & 1 # grab top remaining bit | |
163 | |
164 x = d & ((1 << dLen) - 1) # partially built up value of x | |
165 xLen = dLen # how many bits included so far in x | |
166 while xLen < k: # now grab full chunks until we have enough | |
167 try: | |
168 d = next(chunks) | |
169 except StopIteration: | |
170 return | |
171 dLen = 6 | |
172 x = (x << 6) + d | |
173 xLen += 6 | |
174 x = x >> (xLen - k) # shift back the extra bits | |
175 dLen = xLen - k | |
176 yield b, x | |
177 | |
178 v = 0 | |
179 | |
180 G = nx.MultiGraph() | |
181 G.add_nodes_from(range(n)) | |
182 | |
183 multigraph = False | |
184 for b, x in parseData(): | |
185 if b == 1: | |
186 v += 1 | |
187 # padding with ones can cause overlarge number here | |
188 if x >= n or v >= n: | |
189 break | |
190 elif x > v: | |
191 v = x | |
192 else: | |
193 if G.has_edge(x, v): | |
194 multigraph = True | |
195 G.add_edge(x, v) | |
196 if not multigraph: | |
197 G = nx.Graph(G) | |
198 return G | |
199 | |
200 | |
201 def to_sparse6_bytes(G, nodes=None, header=True): | |
202 """Convert an undirected graph to bytes in sparse6 format. | |
203 | |
204 Parameters | |
205 ---------- | |
206 G : Graph (undirected) | |
207 | |
208 nodes: list or iterable | |
209 Nodes are labeled 0...n-1 in the order provided. If None the ordering | |
210 given by ``G.nodes()`` is used. | |
211 | |
212 header: bool | |
213 If True add '>>sparse6<<' bytes to head of data. | |
214 | |
215 Raises | |
216 ------ | |
217 NetworkXNotImplemented | |
218 If the graph is directed. | |
219 | |
220 ValueError | |
221 If the graph has at least ``2 ** 36`` nodes; the sparse6 format | |
222 is only defined for graphs of order less than ``2 ** 36``. | |
223 | |
224 Examples | |
225 -------- | |
226 >>> nx.to_sparse6_bytes(nx.path_graph(2)) | |
227 b'>>sparse6<<:An\\n' | |
228 | |
229 See Also | |
230 -------- | |
231 to_sparse6_bytes, read_sparse6, write_sparse6_bytes | |
232 | |
233 Notes | |
234 ----- | |
235 The returned bytes end with a newline character. | |
236 | |
237 The format does not support edge or node labels. | |
238 | |
239 References | |
240 ---------- | |
241 .. [1] Graph6 specification | |
242 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
243 | |
244 """ | |
245 if nodes is not None: | |
246 G = G.subgraph(nodes) | |
247 G = nx.convert_node_labels_to_integers(G, ordering="sorted") | |
248 return b"".join(_generate_sparse6_bytes(G, nodes, header)) | |
249 | |
250 | |
251 @open_file(0, mode="rb") | |
252 def read_sparse6(path): | |
253 """Read an undirected graph in sparse6 format from path. | |
254 | |
255 Parameters | |
256 ---------- | |
257 path : file or string | |
258 File or filename to write. | |
259 | |
260 Returns | |
261 ------- | |
262 G : Graph/Multigraph or list of Graphs/MultiGraphs | |
263 If the file contains multiple lines then a list of graphs is returned | |
264 | |
265 Raises | |
266 ------ | |
267 NetworkXError | |
268 If the string is unable to be parsed in sparse6 format | |
269 | |
270 Examples | |
271 -------- | |
272 You can read a sparse6 file by giving the path to the file:: | |
273 | |
274 >>> import tempfile | |
275 >>> with tempfile.NamedTemporaryFile() as f: | |
276 ... _ = f.write(b">>sparse6<<:An\\n") | |
277 ... _ = f.seek(0) | |
278 ... G = nx.read_sparse6(f.name) | |
279 >>> list(G.edges()) | |
280 [(0, 1)] | |
281 | |
282 You can also read a sparse6 file by giving an open file-like object:: | |
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) | |
289 >>> list(G.edges()) | |
290 [(0, 1)] | |
291 | |
292 See Also | |
293 -------- | |
294 read_sparse6, from_sparse6_bytes | |
295 | |
296 References | |
297 ---------- | |
298 .. [1] Sparse6 specification | |
299 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
300 | |
301 """ | |
302 glist = [] | |
303 for line in path: | |
304 line = line.strip() | |
305 if not len(line): | |
306 continue | |
307 glist.append(from_sparse6_bytes(line)) | |
308 if len(glist) == 1: | |
309 return glist[0] | |
310 else: | |
311 return glist | |
312 | |
313 | |
314 @not_implemented_for("directed") | |
315 @open_file(1, mode="wb") | |
316 def write_sparse6(G, path, nodes=None, header=True): | |
317 """Write graph G to given path in sparse6 format. | |
318 | |
319 Parameters | |
320 ---------- | |
321 G : Graph (undirected) | |
322 | |
323 path : file or string | |
324 File or filename to write | |
325 | |
326 nodes: list or iterable | |
327 Nodes are labeled 0...n-1 in the order provided. If None the ordering | |
328 given by G.nodes() is used. | |
329 | |
330 header: bool | |
331 If True add '>>sparse6<<' string to head of data | |
332 | |
333 Raises | |
334 ------ | |
335 NetworkXError | |
336 If the graph is directed | |
337 | |
338 Examples | |
339 -------- | |
340 You can write a sparse6 file by giving the path to the file:: | |
341 | |
342 >>> import tempfile | |
343 >>> with tempfile.NamedTemporaryFile() as f: | |
344 ... nx.write_sparse6(nx.path_graph(2), f.name) | |
345 ... print(f.read()) | |
346 b'>>sparse6<<:An\\n' | |
347 | |
348 You can also write a sparse6 file by giving an open file-like object:: | |
349 | |
350 >>> with tempfile.NamedTemporaryFile() as f: | |
351 ... nx.write_sparse6(nx.path_graph(2), f) | |
352 ... _ = f.seek(0) | |
353 ... print(f.read()) | |
354 b'>>sparse6<<:An\\n' | |
355 | |
356 See Also | |
357 -------- | |
358 read_sparse6, from_sparse6_bytes | |
359 | |
360 Notes | |
361 ----- | |
362 The format does not support edge or node labels. | |
363 | |
364 References | |
365 ---------- | |
366 .. [1] Sparse6 specification | |
367 <http://users.cecs.anu.edu.au/~bdm/data/formats.html> | |
368 | |
369 """ | |
370 if nodes is not None: | |
371 G = G.subgraph(nodes) | |
372 G = nx.convert_node_labels_to_integers(G, ordering="sorted") | |
373 for b in _generate_sparse6_bytes(G, nodes, header): | |
374 path.write(b) |