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 http://www.ics.uci.edu/~eppstein/PADS/ is public domain.
3"""Functions for reading and writing graphs in the *graph6* format.
5The *graph6* file format is suitable for small graphs or large dense
6graphs. For large sparse graphs, use the *sparse6* format.
8For more information, see the `graph6`_ homepage.
10.. _graph6: http://users.cecs.anu.edu.au/~bdm/data/formats.html
12"""
14from itertools import islice
16import networkx as nx
17from networkx.exception import NetworkXError
18from networkx.utils import not_implemented_for, open_file
20__all__ = ["from_graph6_bytes", "read_graph6", "to_graph6_bytes", "write_graph6"]
23def _generate_graph6_bytes(G, nodes, header):
24 """Yield bytes in the graph6 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'>>graph6<<'`` 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 "graph6 is only defined if number of nodes is less than 2 ** 36"
48 )
49 if header:
50 yield b">>graph6<<"
51 for d in n_to_data(n):
52 yield str.encode(chr(d + 63))
53 # This generates the same as `(v in G[u] for u, v in combinations(G, 2))`,
54 # but in "column-major" order instead of "row-major" order.
55 bits = (nodes[j] in G[nodes[i]] for j in range(1, n) for i in range(j))
56 chunk = list(islice(bits, 6))
57 while chunk:
58 d = sum(b << 5 - i for i, b in enumerate(chunk))
59 yield str.encode(chr(d + 63))
60 chunk = list(islice(bits, 6))
61 yield b"\n"
64@nx._dispatchable(graphs=None, returns_graph=True)
65def from_graph6_bytes(bytes_in):
66 """Read a simple undirected graph in graph6 format from bytes.
68 Parameters
69 ----------
70 bytes_in : bytes
71 Data in graph6 format
73 Returns
74 -------
75 G : Graph
77 Raises
78 ------
79 NetworkXError
80 If `bytes_in` is unable to be parsed in graph6 format
82 ValueError
83 If any character ``c`` in bytes_in does not satisfy
84 ``63 <= ord(c) < 127``.
86 Examples
87 --------
88 >>> G = nx.from_graph6_bytes(b"A_")
89 >>> sorted(G.edges())
90 [(0, 1)]
92 Notes
93 -----
94 Per the graph6 spec, the header (e.g. ``b'>>graph6<<'``) must not be
95 followed by a newline character.
97 See Also
98 --------
99 read_graph6, write_graph6
101 References
102 ----------
103 .. [1] Graph6 specification
104 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
106 """
108 def bits():
109 """Returns sequence of individual bits from 6-bit-per-value
110 list of data values."""
111 for d in data:
112 for i in [5, 4, 3, 2, 1, 0]:
113 yield (d >> i) & 1
115 # Ignore trailing newline
116 bytes_in = bytes_in.rstrip(b"\n")
118 if bytes_in.startswith(b">>graph6<<"):
119 bytes_in = bytes_in[10:]
121 data = [c - 63 for c in bytes_in]
122 if any(c > 63 for c in data):
123 raise ValueError("each input character must be in range(63, 127)")
125 n, data = data_to_n(data)
126 nd = (n * (n - 1) // 2 + 5) // 6
127 if len(data) != nd:
128 raise NetworkXError(
129 f"Expected {n * (n - 1) // 2} bits but got {len(data) * 6} in graph6"
130 )
132 G = nx.Graph()
133 G.add_nodes_from(range(n))
134 for (i, j), b in zip(((i, j) for j in range(1, n) for i in range(j)), bits()):
135 if b:
136 G.add_edge(i, j)
138 return G
141@not_implemented_for("directed")
142@not_implemented_for("multigraph")
143def to_graph6_bytes(G, nodes=None, header=True):
144 """Convert a simple undirected graph to bytes in graph6 format.
146 Parameters
147 ----------
148 G : Graph (undirected)
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.
154 header: bool
155 If True add '>>graph6<<' bytes to head of data.
157 Raises
158 ------
159 NetworkXNotImplemented
160 If the graph is directed or is a multigraph.
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``.
166 Examples
167 --------
168 >>> nx.to_graph6_bytes(nx.path_graph(2))
169 b'>>graph6<<A_\\n'
171 See Also
172 --------
173 from_graph6_bytes, read_graph6, write_graph6_bytes
175 Notes
176 -----
177 The returned bytes end with a newline character.
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.
182 References
183 ----------
184 .. [1] Graph6 specification
185 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
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))
195@open_file(0, mode="rb")
196@nx._dispatchable(graphs=None, returns_graph=True)
197def read_graph6(path):
198 """Read simple undirected graphs in graph6 format from path.
200 Parameters
201 ----------
202 path : file or string
203 Filename or file handle to read.
204 Filenames ending in .gz or .bz2 will be decompressed.
206 Returns
207 -------
208 G : Graph or list of Graphs
209 If the file contains multiple lines then a list of graphs is returned
211 Raises
212 ------
213 NetworkXError
214 If the string is unable to be parsed in graph6 format
216 Examples
217 --------
218 You can read a graph6 file by giving the path to the file::
220 >>> import tempfile
221 >>> with tempfile.NamedTemporaryFile(delete=False) as f:
222 ... _ = f.write(b">>graph6<<A_\\n")
223 ... _ = f.seek(0)
224 ... G = nx.read_graph6(f.name)
225 >>> list(G.edges())
226 [(0, 1)]
228 You can also read a graph6 file by giving an open file-like object::
230 >>> import tempfile
231 >>> with tempfile.NamedTemporaryFile() as f:
232 ... _ = f.write(b">>graph6<<A_\\n")
233 ... _ = f.seek(0)
234 ... G = nx.read_graph6(f)
235 >>> list(G.edges())
236 [(0, 1)]
238 See Also
239 --------
240 from_graph6_bytes, write_graph6
242 References
243 ----------
244 .. [1] Graph6 specification
245 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
247 """
248 glist = []
249 for line in path:
250 line = line.strip()
251 if not len(line):
252 continue
253 glist.append(from_graph6_bytes(line))
254 if len(glist) == 1:
255 return glist[0]
256 else:
257 return glist
260@not_implemented_for("directed")
261@not_implemented_for("multigraph")
262@open_file(1, mode="wb")
263def write_graph6(G, path, nodes=None, header=True):
264 """Write a simple undirected graph to a path in graph6 format.
266 Parameters
267 ----------
268 G : Graph (undirected)
270 path : file or string
271 File or filename to write.
272 Filenames ending in .gz or .bz2 will be compressed.
274 nodes: list or iterable
275 Nodes are labeled 0...n-1 in the order provided. If None the ordering
276 given by ``G.nodes()`` is used.
278 header: bool
279 If True add '>>graph6<<' string to head of data
281 Raises
282 ------
283 NetworkXNotImplemented
284 If the graph is directed or is a multigraph.
286 ValueError
287 If the graph has at least ``2 ** 36`` nodes; the graph6 format
288 is only defined for graphs of order less than ``2 ** 36``.
290 Examples
291 --------
292 You can write a graph6 file by giving the path to a file::
294 >>> import tempfile
295 >>> with tempfile.NamedTemporaryFile(delete=False) as f:
296 ... nx.write_graph6(nx.path_graph(2), f.name)
297 ... _ = f.seek(0)
298 ... print(f.read())
299 b'>>graph6<<A_\\n'
301 See Also
302 --------
303 from_graph6_bytes, read_graph6
305 Notes
306 -----
307 The function writes a newline character after writing the encoding
308 of the graph.
310 The format does not support edge or node labels, parallel edges or
311 self loops. If self loops are present they are silently ignored.
313 References
314 ----------
315 .. [1] Graph6 specification
316 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
318 """
319 return write_graph6_file(G, path, nodes=nodes, header=header)
322@not_implemented_for("directed")
323@not_implemented_for("multigraph")
324def write_graph6_file(G, f, nodes=None, header=True):
325 """Write a simple undirected graph to a file-like object in graph6 format.
327 Parameters
328 ----------
329 G : Graph (undirected)
331 f : file-like object
332 The file to write.
334 nodes: list or iterable
335 Nodes are labeled 0...n-1 in the order provided. If None the ordering
336 given by ``G.nodes()`` is used.
338 header: bool
339 If True add '>>graph6<<' string to head of data
341 Raises
342 ------
343 NetworkXNotImplemented
344 If the graph is directed or is a multigraph.
346 ValueError
347 If the graph has at least ``2 ** 36`` nodes; the graph6 format
348 is only defined for graphs of order less than ``2 ** 36``.
350 Examples
351 --------
352 You can write a graph6 file by giving an open file-like object::
354 >>> import tempfile
355 >>> with tempfile.NamedTemporaryFile() as f:
356 ... nx.write_graph6(nx.path_graph(2), f)
357 ... _ = f.seek(0)
358 ... print(f.read())
359 b'>>graph6<<A_\\n'
361 See Also
362 --------
363 from_graph6_bytes, read_graph6
365 Notes
366 -----
367 The function writes a newline character after writing the encoding
368 of the graph.
370 The format does not support edge or node labels, parallel edges or
371 self loops. If self loops are present they are silently ignored.
373 References
374 ----------
375 .. [1] Graph6 specification
376 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>
378 """
379 if nodes is not None:
380 G = G.subgraph(nodes)
381 H = nx.convert_node_labels_to_integers(G)
382 nodes = sorted(H.nodes())
383 for b in _generate_graph6_bytes(H, nodes, header):
384 f.write(b)
387def data_to_n(data):
388 """Read initial one-, four- or eight-unit value from graph6
389 integer sequence.
391 Return (value, rest of seq.)"""
392 if data[0] <= 62:
393 return data[0], data[1:]
394 if data[1] <= 62:
395 return (data[1] << 12) + (data[2] << 6) + data[3], data[4:]
396 return (
397 (data[2] << 30)
398 + (data[3] << 24)
399 + (data[4] << 18)
400 + (data[5] << 12)
401 + (data[6] << 6)
402 + data[7],
403 data[8:],
404 )
407def n_to_data(n):
408 """Convert an integer to one-, four- or eight-unit graph6 sequence.
410 This function is undefined if `n` is not in ``range(2 ** 36)``.
412 """
413 if n <= 62:
414 return [n]
415 elif n <= 258047:
416 return [63, (n >> 12) & 0x3F, (n >> 6) & 0x3F, n & 0x3F]
417 else: # if n <= 68719476735:
418 return [
419 63,
420 63,
421 (n >> 30) & 0x3F,
422 (n >> 24) & 0x3F,
423 (n >> 18) & 0x3F,
424 (n >> 12) & 0x3F,
425 (n >> 6) & 0x3F,
426 n & 0x3F,
427 ]