Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# Original author: D. Eppstein, UC Irvine, August 12, 2003.
2# The original code at https://www.ics.uci.edu/~eppstein/PADS/ is public domain.
3"""Functions for reading and writing graphs in the *sparse6* format.
5The *sparse6* file format is a space-efficient format for large sparse
6graphs. For small graphs or large dense graphs, use the *graph6* file
7format.
9For more information, see the `sparse6`_ homepage.
11.. _sparse6: https://users.cecs.anu.edu.au/~bdm/data/formats.html
13"""
15import networkx as nx
16from networkx.exception import NetworkXError
17from networkx.readwrite.graph6 import data_to_n, n_to_data
18from networkx.utils import not_implemented_for, open_file
20__all__ = ["from_sparse6_bytes", "read_sparse6", "to_sparse6_bytes", "write_sparse6"]
23def _generate_sparse6_bytes(G, nodes, header):
24 """Yield bytes in the sparse6 encoding of a graph.
26 `G` is an undirected simple graph. `nodes` is the list of nodes for
27 which the node-induced subgraph will be encoded; if `nodes` is the
28 list of all nodes in the graph, the entire graph will be
29 encoded. `header` is a Boolean that specifies whether to generate
30 the header ``b'>>sparse6<<'`` before the remaining data.
32 This function generates `bytes` objects in the following order:
34 1. the header (if requested),
35 2. the encoding of the number of nodes,
36 3. each character, one-at-a-time, in the encoding of the requested
37 node-induced subgraph,
38 4. a newline character.
40 This function raises :exc:`ValueError` if the graph is too large for
41 the graph6 format (that is, greater than ``2 ** 36`` nodes).
43 """
44 n = len(G)
45 if n >= 2**36:
46 raise ValueError(
47 "sparse6 is only defined if number of nodes is less than 2 ** 36"
48 )
49 if header:
50 yield b">>sparse6<<"
51 yield b":"
52 for d in n_to_data(n):
53 yield str.encode(chr(d + 63))
55 k = 1
56 while 1 << k < n:
57 k += 1
59 def enc(x):
60 """Big endian k-bit encoding of x"""
61 return [1 if (x & 1 << (k - 1 - i)) else 0 for i in range(k)]
63 edges = sorted((max(u, v), min(u, v)) for u, v in G.edges())
64 bits = []
65 curv = 0
66 for v, u in edges:
67 if v == curv: # current vertex edge
68 bits.append(0)
69 bits.extend(enc(u))
70 elif v == curv + 1: # next vertex edge
71 curv += 1
72 bits.append(1)
73 bits.extend(enc(u))
74 else: # skip to vertex v and then add edge to u
75 curv = v
76 bits.append(1)
77 bits.extend(enc(v))
78 bits.append(0)
79 bits.extend(enc(u))
80 if k < 6 and n == (1 << k) and ((-len(bits)) % 6) >= k and curv < (n - 1):
81 # Padding special case: small k, n=2^k,
82 # more than k bits of padding needed,
83 # current vertex is not (n-1) --
84 # appending 1111... would add a loop on (n-1)
85 bits.append(0)
86 bits.extend([1] * ((-len(bits)) % 6))
87 else:
88 bits.extend([1] * ((-len(bits)) % 6))
90 data = [
91 (bits[i + 0] << 5)
92 + (bits[i + 1] << 4)
93 + (bits[i + 2] << 3)
94 + (bits[i + 3] << 2)
95 + (bits[i + 4] << 1)
96 + (bits[i + 5] << 0)
97 for i in range(0, len(bits), 6)
98 ]
100 for d in data:
101 yield str.encode(chr(d + 63))
102 yield b"\n"
105@nx._dispatchable(graphs=None, returns_graph=True)
106def from_sparse6_bytes(string):
107 """Read an undirected graph in sparse6 format from string.
109 Parameters
110 ----------
111 string : string
112 Data in sparse6 format
114 Returns
115 -------
116 G : Graph
118 Raises
119 ------
120 NetworkXError
121 If the string is unable to be parsed in sparse6 format
123 Examples
124 --------
125 >>> G = nx.from_sparse6_bytes(b":A_")
126 >>> sorted(G.edges())
127 [(0, 1), (0, 1), (0, 1)]
129 See Also
130 --------
131 read_sparse6, write_sparse6
133 References
134 ----------
135 .. [1] Sparse6 specification
136 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>
138 """
139 if string.startswith(b">>sparse6<<"):
140 string = string[11:]
141 if not string.startswith(b":"):
142 raise NetworkXError("Expected leading colon in sparse6")
144 chars = [c - 63 for c in string[1:]]
145 n, data = data_to_n(chars)
146 k = 1
147 while 1 << k < n:
148 k += 1
150 def parseData():
151 """Returns stream of pairs b[i], x[i] for sparse6 format."""
152 chunks = iter(data)
153 d = None # partial data word
154 dLen = 0 # how many unparsed bits are left in d
156 while 1:
157 if dLen < 1:
158 try:
159 d = next(chunks)
160 except StopIteration:
161 return
162 dLen = 6
163 dLen -= 1
164 b = (d >> dLen) & 1 # grab top remaining bit
166 x = d & ((1 << dLen) - 1) # partially built up value of x
167 xLen = dLen # how many bits included so far in x
168 while xLen < k: # now grab full chunks until we have enough
169 try:
170 d = next(chunks)
171 except StopIteration:
172 return
173 dLen = 6
174 x = (x << 6) + d
175 xLen += 6
176 x = x >> (xLen - k) # shift back the extra bits
177 dLen = xLen - k
178 yield b, x
180 v = 0
182 G = nx.MultiGraph()
183 G.add_nodes_from(range(n))
185 multigraph = False
186 for b, x in parseData():
187 if b == 1:
188 v += 1
189 # padding with ones can cause overlarge number here
190 if x >= n or v >= n:
191 break
192 elif x > v:
193 v = x
194 else:
195 if G.has_edge(x, v):
196 multigraph = True
197 G.add_edge(x, v)
198 if not multigraph:
199 G = nx.Graph(G)
200 return G
203def to_sparse6_bytes(G, nodes=None, header=True):
204 """Convert an undirected graph to bytes in sparse6 format.
206 Parameters
207 ----------
208 G : Graph (undirected)
210 nodes: list or iterable
211 Nodes are labeled 0...n-1 in the order provided. If None the ordering
212 given by ``G.nodes()`` is used.
214 header: bool
215 If True add '>>sparse6<<' bytes to head of data.
217 Raises
218 ------
219 NetworkXNotImplemented
220 If the graph is directed.
222 ValueError
223 If the graph has at least ``2 ** 36`` nodes; the sparse6 format
224 is only defined for graphs of order less than ``2 ** 36``.
226 Examples
227 --------
228 >>> nx.to_sparse6_bytes(nx.path_graph(2))
229 b'>>sparse6<<:An\\n'
231 See Also
232 --------
233 to_sparse6_bytes, read_sparse6, write_sparse6_bytes
235 Notes
236 -----
237 The returned bytes end with a newline character.
239 The format does not support edge or node labels.
241 References
242 ----------
243 .. [1] Graph6 specification
244 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>
246 """
247 if nodes is not None:
248 G = G.subgraph(nodes)
249 G = nx.convert_node_labels_to_integers(G, ordering="sorted")
250 return b"".join(_generate_sparse6_bytes(G, nodes, header))
253@open_file(0, mode="rb")
254@nx._dispatchable(graphs=None, returns_graph=True)
255def read_sparse6(path):
256 """Read an undirected graph in sparse6 format from path.
258 Parameters
259 ----------
260 path : file or string
261 Filename or file handle to read.
262 Filenames ending in .gz or .bz2 will be decompressed.
264 Returns
265 -------
266 G : Graph/Multigraph or list of Graphs/MultiGraphs
267 If the file contains multiple lines then a list of graphs is returned
269 Raises
270 ------
271 NetworkXError
272 If the string is unable to be parsed in sparse6 format
274 Examples
275 --------
276 You can read a sparse6 file by giving the path to the file::
278 >>> import tempfile
279 >>> with tempfile.NamedTemporaryFile(delete=False) as f:
280 ... _ = f.write(b">>sparse6<<:An\\n")
281 ... _ = f.seek(0)
282 ... G = nx.read_sparse6(f.name)
283 >>> list(G.edges())
284 [(0, 1)]
286 You can also read a sparse6 file by giving an open file-like object::
288 >>> import tempfile
289 >>> with tempfile.NamedTemporaryFile() as f:
290 ... _ = f.write(b">>sparse6<<:An\\n")
291 ... _ = f.seek(0)
292 ... G = nx.read_sparse6(f)
293 >>> list(G.edges())
294 [(0, 1)]
296 See Also
297 --------
298 read_sparse6, from_sparse6_bytes
300 References
301 ----------
302 .. [1] Sparse6 specification
303 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>
305 """
306 glist = []
307 for line in path:
308 line = line.strip()
309 if not len(line):
310 continue
311 glist.append(from_sparse6_bytes(line))
312 if len(glist) == 1:
313 return glist[0]
314 else:
315 return glist
318@not_implemented_for("directed")
319@open_file(1, mode="wb")
320def write_sparse6(G, path, nodes=None, header=True):
321 """Write graph G to given path in sparse6 format.
323 Parameters
324 ----------
325 G : Graph (undirected)
327 path : file or string
328 File or filename to write.
329 Filenames ending in .gz or .bz2 will be compressed.
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.
335 header: bool
336 If True add '>>sparse6<<' string to head of data
338 Raises
339 ------
340 NetworkXError
341 If the graph is directed
343 Examples
344 --------
345 You can write a sparse6 file by giving the path to the file::
347 >>> import tempfile
348 >>> with tempfile.NamedTemporaryFile(delete=False) as f:
349 ... nx.write_sparse6(nx.path_graph(2), f.name)
350 ... print(f.read())
351 b'>>sparse6<<:An\\n'
353 You can also write a sparse6 file by giving an open file-like object::
355 >>> with tempfile.NamedTemporaryFile() as f:
356 ... nx.write_sparse6(nx.path_graph(2), f)
357 ... _ = f.seek(0)
358 ... print(f.read())
359 b'>>sparse6<<:An\\n'
361 See Also
362 --------
363 read_sparse6, from_sparse6_bytes
365 Notes
366 -----
367 The format does not support edge or node labels.
369 References
370 ----------
371 .. [1] Sparse6 specification
372 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>
374 """
375 if nodes is not None:
376 G = G.subgraph(nodes)
377 G = nx.convert_node_labels_to_integers(G, ordering="sorted")
378 for b in _generate_sparse6_bytes(G, nodes, header):
379 path.write(b)