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

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

14import networkx as nx

15from networkx.exception import NetworkXError

16from networkx.readwrite.graph6 import data_to_n, n_to_data

17from networkx.utils import not_implemented_for, open_file

19__all__ = ["from_sparse6_bytes", "read_sparse6", "to_sparse6_bytes", "write_sparse6"]

22def _generate_sparse6_bytes(G, nodes, header):

23 """Yield bytes in the sparse6 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'>>sparse6<<'`` 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 "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))

54 k = 1

55 while 1 << k < n:

56 k += 1

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)]

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

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 ]

99 for d in data:

100 yield str.encode(chr(d + 63))

101 yield b"\n"

102

103

104@nx._dispatch(graphs=None)

105def from_sparse6_bytes(string):

106 """Read an undirected graph in sparse6 format from string.

107

108 Parameters

109 ----------

110 string : string

111 Data in sparse6 format

112

113 Returns

114 -------

115 G : Graph

116

117 Raises

118 ------

119 NetworkXError

120 If the string is unable to be parsed in sparse6 format

121

122 Examples

123 --------

124 >>> G = nx.from_sparse6_bytes(b":A_")

125 >>> sorted(G.edges())

126 [(0, 1), (0, 1), (0, 1)]

127

128 See Also

129 --------

130 read_sparse6, write_sparse6

131

132 References

133 ----------

134 .. [1] Sparse6 specification

135 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>

136

137 """

138 if string.startswith(b">>sparse6<<"):

139 string = string[11:]

140 if not string.startswith(b":"):

141 raise NetworkXError("Expected leading colon in sparse6")

142

143 chars = [c - 63 for c in string[1:]]

144 n, data = data_to_n(chars)

145 k = 1

146 while 1 << k < n:

147 k += 1

148

149 def parseData():

150 """Returns stream of pairs b[i], x[i] for sparse6 format."""

151 chunks = iter(data)

152 d = None # partial data word

153 dLen = 0 # how many unparsed bits are left in d

154

155 while 1:

156 if dLen < 1:

157 try:

158 d = next(chunks)

159 except StopIteration:

160 return

161 dLen = 6

162 dLen -= 1

163 b = (d >> dLen) & 1 # grab top remaining bit

164

165 x = d & ((1 << dLen) - 1) # partially built up value of x

166 xLen = dLen # how many bits included so far in x

167 while xLen < k: # now grab full chunks until we have enough

168 try:

169 d = next(chunks)

170 except StopIteration:

171 return

172 dLen = 6

173 x = (x << 6) + d

174 xLen += 6

175 x = x >> (xLen - k) # shift back the extra bits

176 dLen = xLen - k

177 yield b, x

178

179 v = 0

180

181 G = nx.MultiGraph()

182 G.add_nodes_from(range(n))

183

184 multigraph = False

185 for b, x in parseData():

186 if b == 1:

187 v += 1

188 # padding with ones can cause overlarge number here

189 if x >= n or v >= n:

190 break

191 elif x > v:

192 v = x

193 else:

194 if G.has_edge(x, v):

195 multigraph = True

196 G.add_edge(x, v)

197 if not multigraph:

198 G = nx.Graph(G)

199 return G

200

201

202def to_sparse6_bytes(G, nodes=None, header=True):

203 """Convert an undirected graph to bytes in sparse6 format.

204

205 Parameters

206 ----------

207 G : Graph (undirected)

208

209 nodes: list or iterable

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

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

212

213 header: bool

214 If True add '>>sparse6<<' bytes to head of data.

215

216 Raises

217 ------

218 NetworkXNotImplemented

219 If the graph is directed.

220

221 ValueError

222 If the graph has at least ``2 ** 36`` nodes; the sparse6 format

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

224

225 Examples

226 --------

227 >>> nx.to_sparse6_bytes(nx.path_graph(2))

228 b'>>sparse6<<:An\\n'

229

230 See Also

231 --------

232 to_sparse6_bytes, read_sparse6, write_sparse6_bytes

233

234 Notes

235 -----

236 The returned bytes end with a newline character.

237

238 The format does not support edge or node labels.

239

240 References

241 ----------

242 .. [1] Graph6 specification

243 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>

244

245 """

246 if nodes is not None:

247 G = G.subgraph(nodes)

248 G = nx.convert_node_labels_to_integers(G, ordering="sorted")

249 return b"".join(_generate_sparse6_bytes(G, nodes, header))

250

251

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

253@nx._dispatch(graphs=None)

254def read_sparse6(path):

255 """Read an undirected graph in sparse6 format from path.

256

257 Parameters

258 ----------

259 path : file or string

260 File or filename to write.

261

262 Returns

263 -------

264 G : Graph/Multigraph or list of Graphs/MultiGraphs

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

266

267 Raises

268 ------

269 NetworkXError

270 If the string is unable to be parsed in sparse6 format

271

272 Examples

273 --------

274 You can read a sparse6 file by giving the path to the file::

275

276 >>> import tempfile

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

278 ... _ = f.write(b">>sparse6<<:An\\n")

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

280 ... G = nx.read_sparse6(f.name)

281 >>> list(G.edges())

282 [(0, 1)]

283

284 You can also read a sparse6 file by giving an open file-like object::

285

286 >>> import tempfile

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

288 ... _ = f.write(b">>sparse6<<:An\\n")

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

290 ... G = nx.read_sparse6(f)

291 >>> list(G.edges())

292 [(0, 1)]

293

294 See Also

295 --------

296 read_sparse6, from_sparse6_bytes

297

298 References

299 ----------

300 .. [1] Sparse6 specification

301 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>

302

303 """

304 glist = []

305 for line in path:

306 line = line.strip()

307 if not len(line):

308 continue

309 glist.append(from_sparse6_bytes(line))

310 if len(glist) == 1:

311 return glist[0]

312 else:

313 return glist

314

315

316@not_implemented_for("directed")

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

318def write_sparse6(G, path, nodes=None, header=True):

319 """Write graph G to given path in sparse6 format.

320

321 Parameters

322 ----------

323 G : Graph (undirected)

324

325 path : file or string

326 File or filename to write

327

328 nodes: list or iterable

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

330 given by G.nodes() is used.

331

332 header: bool

333 If True add '>>sparse6<<' string to head of data

334

335 Raises

336 ------

337 NetworkXError

338 If the graph is directed

339

340 Examples

341 --------

342 You can write a sparse6 file by giving the path to the file::

343

344 >>> import tempfile

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

346 ... nx.write_sparse6(nx.path_graph(2), f.name)

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

348 b'>>sparse6<<:An\\n'

349

350 You can also write a sparse6 file by giving an open file-like object::

351

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

353 ... nx.write_sparse6(nx.path_graph(2), f)

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

355 ... print(f.read())

356 b'>>sparse6<<:An\\n'

357

358 See Also

359 --------

360 read_sparse6, from_sparse6_bytes

361

362 Notes

363 -----

364 The format does not support edge or node labels.

365

366 References

367 ----------

368 .. [1] Sparse6 specification

369 <https://users.cecs.anu.edu.au/~bdm/data/formats.html>

370

371 """

372 if nodes is not None:

373 G = G.subgraph(nodes)

374 G = nx.convert_node_labels_to_integers(G, ordering="sorted")

375 for b in _generate_sparse6_bytes(G, nodes, header):

376 path.write(b)