Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/readwrite/graph6.py: 55%

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"""

13from itertools import islice

15import networkx as nx

16from networkx.exception import NetworkXError

17from networkx.utils import not_implemented_for, open_file

19__all__ = ["from_graph6_bytes", "read_graph6", "to_graph6_bytes", "write_graph6"]

22def _generate_graph6_bytes(G, nodes, header):

23 """Yield bytes in the graph6 encoding of a graph.

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.

31 This function generates `bytes` objects in the following order:

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.

39 This function raises :exc:`ValueError` if the graph is too large for

40 the graph6 format (that is, greater than ``2 ** 36`` nodes).

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"

63@nx._dispatch(graphs=None)

64def from_graph6_bytes(bytes_in):

65 """Read a simple undirected graph in graph6 format from bytes.

67 Parameters

68 ----------

69 bytes_in : bytes

70 Data in graph6 format, without a trailing newline.

72 Returns

73 -------

74 G : Graph

76 Raises

77 ------

78 NetworkXError

79 If bytes_in is unable to be parsed in graph6 format

81 ValueError

82 If any character ``c`` in bytes_in does not satisfy

83 ``63 <= ord(c) < 127``.

85 Examples

86 --------

87 >>> G = nx.from_graph6_bytes(b"A_")

88 >>> sorted(G.edges())

89 [(0, 1)]

91 See Also

92 --------

93 read_graph6, write_graph6

95 References

96 ----------

97 .. [1] Graph6 specification

98 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>

100 """

101

102 def bits():

103 """Returns sequence of individual bits from 6-bit-per-value

104 list of data values."""

105 for d in data:

106 for i in [5, 4, 3, 2, 1, 0]:

107 yield (d >> i) & 1

108

109 if bytes_in.startswith(b">>graph6<<"):

110 bytes_in = bytes_in[10:]

111

112 data = [c - 63 for c in bytes_in]

113 if any(c > 63 for c in data):

114 raise ValueError("each input character must be in range(63, 127)")

115

116 n, data = data_to_n(data)

117 nd = (n * (n - 1) // 2 + 5) // 6

118 if len(data) != nd:

119 raise NetworkXError(

120 f"Expected {n * (n - 1) // 2} bits but got {len(data) * 6} in graph6"

121 )

122

123 G = nx.Graph()

124 G.add_nodes_from(range(n))

125 for (i, j), b in zip(((i, j) for j in range(1, n) for i in range(j)), bits()):

126 if b:

127 G.add_edge(i, j)

128

129 return G

130

131

132@not_implemented_for("directed")

133@not_implemented_for("multigraph")

134def to_graph6_bytes(G, nodes=None, header=True):

135 """Convert a simple undirected graph to bytes in graph6 format.

136

137 Parameters

138 ----------

139 G : Graph (undirected)

140

141 nodes: list or iterable

142 Nodes are labeled 0...n-1 in the order provided. If None the ordering

143 given by ``G.nodes()`` is used.

144

145 header: bool

146 If True add '>>graph6<<' bytes to head of data.

147

148 Raises

149 ------

150 NetworkXNotImplemented

151 If the graph is directed or is a multigraph.

152

153 ValueError

154 If the graph has at least ``2 ** 36`` nodes; the graph6 format

155 is only defined for graphs of order less than ``2 ** 36``.

156

157 Examples

158 --------

159 >>> nx.to_graph6_bytes(nx.path_graph(2))

160 b'>>graph6<<A_\\n'

161

162 See Also

163 --------

164 from_graph6_bytes, read_graph6, write_graph6_bytes

165

166 Notes

167 -----

168 The returned bytes end with a newline character.

169

170 The format does not support edge or node labels, parallel edges or

171 self loops. If self loops are present they are silently ignored.

172

173 References

174 ----------

175 .. [1] Graph6 specification

176 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>

177

178 """

179 if nodes is not None:

180 G = G.subgraph(nodes)

181 H = nx.convert_node_labels_to_integers(G)

182 nodes = sorted(H.nodes())

183 return b"".join(_generate_graph6_bytes(H, nodes, header))

184

185

186@open_file(0, mode="rb")

187@nx._dispatch(graphs=None)

188def read_graph6(path):

189 """Read simple undirected graphs in graph6 format from path.

190

191 Parameters

192 ----------

193 path : file or string

194 File or filename to write.

195

196 Returns

197 -------

198 G : Graph or list of Graphs

199 If the file contains multiple lines then a list of graphs is returned

200

201 Raises

202 ------

203 NetworkXError

204 If the string is unable to be parsed in graph6 format

205

206 Examples

207 --------

208 You can read a graph6 file by giving the path to the file::

209

210 >>> import tempfile

211 >>> with tempfile.NamedTemporaryFile(delete=False) as f:

212 ... _ = f.write(b">>graph6<<A_\\n")

213 ... _ = f.seek(0)

214 ... G = nx.read_graph6(f.name)

215 >>> list(G.edges())

216 [(0, 1)]

217

218 You can also read a graph6 file by giving an open file-like object::

219

220 >>> import tempfile

221 >>> with tempfile.NamedTemporaryFile() as f:

222 ... _ = f.write(b">>graph6<<A_\\n")

223 ... _ = f.seek(0)

224 ... G = nx.read_graph6(f)

225 >>> list(G.edges())

226 [(0, 1)]

227

228 See Also

229 --------

230 from_graph6_bytes, write_graph6

231

232 References

233 ----------

234 .. [1] Graph6 specification

235 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>

236

237 """

238 glist = []

239 for line in path:

240 line = line.strip()

241 if not len(line):

242 continue

243 glist.append(from_graph6_bytes(line))

244 if len(glist) == 1:

245 return glist[0]

246 else:

247 return glist

248

249

250@not_implemented_for("directed")

251@not_implemented_for("multigraph")

252@open_file(1, mode="wb")

253def write_graph6(G, path, nodes=None, header=True):

254 """Write a simple undirected graph to a path in graph6 format.

255

256 Parameters

257 ----------

258 G : Graph (undirected)

259

260 path : str

261 The path naming the file to which to write the graph.

262

263 nodes: list or iterable

264 Nodes are labeled 0...n-1 in the order provided. If None the ordering

265 given by ``G.nodes()`` is used.

266

267 header: bool

268 If True add '>>graph6<<' string to head of data

269

270 Raises

271 ------

272 NetworkXNotImplemented

273 If the graph is directed or is a multigraph.

274

275 ValueError

276 If the graph has at least ``2 ** 36`` nodes; the graph6 format

277 is only defined for graphs of order less than ``2 ** 36``.

278

279 Examples

280 --------

281 You can write a graph6 file by giving the path to a file::

282

283 >>> import tempfile

284 >>> with tempfile.NamedTemporaryFile(delete=False) as f:

285 ... nx.write_graph6(nx.path_graph(2), f.name)

286 ... _ = f.seek(0)

287 ... print(f.read())

288 b'>>graph6<<A_\\n'

289

290 See Also

291 --------

292 from_graph6_bytes, read_graph6

293

294 Notes

295 -----

296 The function writes a newline character after writing the encoding

297 of the graph.

298

299 The format does not support edge or node labels, parallel edges or

300 self loops. If self loops are present they are silently ignored.

301

302 References

303 ----------

304 .. [1] Graph6 specification

305 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>

306

307 """

308 return write_graph6_file(G, path, nodes=nodes, header=header)

309

310

311@not_implemented_for("directed")

312@not_implemented_for("multigraph")

313def write_graph6_file(G, f, nodes=None, header=True):

314 """Write a simple undirected graph to a file-like object in graph6 format.

315

316 Parameters

317 ----------

318 G : Graph (undirected)

319

320 f : file-like object

321 The file to write.

322

323 nodes: list or iterable

324 Nodes are labeled 0...n-1 in the order provided. If None the ordering

325 given by ``G.nodes()`` is used.

326

327 header: bool

328 If True add '>>graph6<<' string to head of data

329

330 Raises

331 ------

332 NetworkXNotImplemented

333 If the graph is directed or is a multigraph.

334

335 ValueError

336 If the graph has at least ``2 ** 36`` nodes; the graph6 format

337 is only defined for graphs of order less than ``2 ** 36``.

338

339 Examples

340 --------

341 You can write a graph6 file by giving an open file-like object::

342

343 >>> import tempfile

344 >>> with tempfile.NamedTemporaryFile() as f:

345 ... nx.write_graph6(nx.path_graph(2), f)

346 ... _ = f.seek(0)

347 ... print(f.read())

348 b'>>graph6<<A_\\n'

349

350 See Also

351 --------

352 from_graph6_bytes, read_graph6

353

354 Notes

355 -----

356 The function writes a newline character after writing the encoding

357 of the graph.

358

359 The format does not support edge or node labels, parallel edges or

360 self loops. If self loops are present they are silently ignored.

361

362 References

363 ----------

364 .. [1] Graph6 specification

365 <http://users.cecs.anu.edu.au/~bdm/data/formats.html>

366

367 """

368 if nodes is not None:

369 G = G.subgraph(nodes)

370 H = nx.convert_node_labels_to_integers(G)

371 nodes = sorted(H.nodes())

372 for b in _generate_graph6_bytes(H, nodes, header):

373 f.write(b)

374

375

376def data_to_n(data):

377 """Read initial one-, four- or eight-unit value from graph6

378 integer sequence.

379

380 Return (value, rest of seq.)"""

381 if data[0] <= 62:

382 return data[0], data[1:]

383 if data[1] <= 62:

384 return (data[1] << 12) + (data[2] << 6) + data[3], data[4:]

385 return (

386 (data[2] << 30)

387 + (data[3] << 24)

388 + (data[4] << 18)

389 + (data[5] << 12)

390 + (data[6] << 6)

391 + data[7],

392 data[8:],

393 )

394

395

396def n_to_data(n):

397 """Convert an integer to one-, four- or eight-unit graph6 sequence.

398

399 This function is undefined if `n` is not in ``range(2 ** 36)``.

400

401 """

402 if n <= 62:

403 return [n]

404 elif n <= 258047:

405 return [63, (n >> 12) & 0x3F, (n >> 6) & 0x3F, n & 0x3F]

406 else: # if n <= 68719476735:

407 return [

408 63,

409 63,

410 (n >> 30) & 0x3F,

411 (n >> 24) & 0x3F,

412 (n >> 18) & 0x3F,

413 (n >> 12) & 0x3F,

414 (n >> 6) & 0x3F,

415 n & 0x3F,

416 ]