Coverage for /usr/lib/python3/dist-packages/sympy/combinatorics/prufer.py: 23%

1from sympy.core import Basic

2from sympy.core.containers import Tuple

3from sympy.tensor.array import Array

4from sympy.core.sympify import _sympify

5from sympy.utilities.iterables import flatten, iterable

6from sympy.utilities.misc import as_int

8from collections import defaultdict

11class Prufer(Basic):

12 """

13 The Prufer correspondence is an algorithm that describes the

14 bijection between labeled trees and the Prufer code. A Prufer

15 code of a labeled tree is unique up to isomorphism and has

16 a length of n - 2.

18 Prufer sequences were first used by Heinz Prufer to give a

19 proof of Cayley's formula.

21 References

22 ==========

24 .. [1] https://mathworld.wolfram.com/LabeledTree.html

26 """

27 _prufer_repr = None

28 _tree_repr = None

29 _nodes = None

30 _rank = None

32 @property

33 def prufer_repr(self):

34 """Returns Prufer sequence for the Prufer object.

36 This sequence is found by removing the highest numbered vertex,

37 recording the node it was attached to, and continuing until only

38 two vertices remain. The Prufer sequence is the list of recorded nodes.

40 Examples

41 ========

43 >>> from sympy.combinatorics.prufer import Prufer

44 >>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).prufer_repr

45 [3, 3, 3, 4]

46 >>> Prufer([1, 0, 0]).prufer_repr

47 [1, 0, 0]

49 See Also

50 ========

52 to_prufer

54 """

55 if self._prufer_repr is None:

56 self._prufer_repr = self.to_prufer(self._tree_repr[:], self.nodes)

57 return self._prufer_repr

59 @property

60 def tree_repr(self):

61 """Returns the tree representation of the Prufer object.

63 Examples

64 ========

66 >>> from sympy.combinatorics.prufer import Prufer

67 >>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).tree_repr

68 [[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]

69 >>> Prufer([1, 0, 0]).tree_repr

70 [[1, 2], [0, 1], [0, 3], [0, 4]]

72 See Also

73 ========

75 to_tree

77 """

78 if self._tree_repr is None:

79 self._tree_repr = self.to_tree(self._prufer_repr[:])

80 return self._tree_repr

82 @property

83 def nodes(self):

84 """Returns the number of nodes in the tree.

86 Examples

87 ========

89 >>> from sympy.combinatorics.prufer import Prufer

90 >>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).nodes

91 6

92 >>> Prufer([1, 0, 0]).nodes

93 5

95 """

96 return self._nodes

98 @property

99 def rank(self):

100 """Returns the rank of the Prufer sequence.

101

102 Examples

103 ========

104

105 >>> from sympy.combinatorics.prufer import Prufer

106 >>> p = Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]])

107 >>> p.rank

108 778

109 >>> p.next(1).rank

110 779

111 >>> p.prev().rank

112 777

113

114 See Also

115 ========

116

117 prufer_rank, next, prev, size

118

119 """

120 if self._rank is None:

121 self._rank = self.prufer_rank()

122 return self._rank

123

124 @property

125 def size(self):

126 """Return the number of possible trees of this Prufer object.

127

128 Examples

129 ========

130

131 >>> from sympy.combinatorics.prufer import Prufer

132 >>> Prufer([0]*4).size == Prufer([6]*4).size == 1296

133 True

134

135 See Also

136 ========

137

138 prufer_rank, rank, next, prev

139

140 """

141 return self.prev(self.rank).prev().rank + 1

142

143 @staticmethod

144 def to_prufer(tree, n):

145 """Return the Prufer sequence for a tree given as a list of edges where

146 ``n`` is the number of nodes in the tree.

147

148 Examples

149 ========

150

151 >>> from sympy.combinatorics.prufer import Prufer

152 >>> a = Prufer([[0, 1], [0, 2], [0, 3]])

153 >>> a.prufer_repr

154 [0, 0]

155 >>> Prufer.to_prufer([[0, 1], [0, 2], [0, 3]], 4)

156 [0, 0]

157

158 See Also

159 ========

160 prufer_repr: returns Prufer sequence of a Prufer object.

161

162 """

163 d = defaultdict(int)

164 L = []

165 for edge in tree:

166 # Increment the value of the corresponding

167 # node in the degree list as we encounter an

168 # edge involving it.

169 d[edge[0]] += 1

170 d[edge[1]] += 1

171 for i in range(n - 2):

172 # find the smallest leaf

173 for x in range(n):

174 if d[x] == 1:

175 break

176 # find the node it was connected to

177 y = None

178 for edge in tree:

179 if x == edge[0]:

180 y = edge[1]

181 elif x == edge[1]:

182 y = edge[0]

183 if y is not None:

184 break

185 # record and update

186 L.append(y)

187 for j in (x, y):

188 d[j] -= 1

189 if not d[j]:

190 d.pop(j)

191 tree.remove(edge)

192 return L

193

194 @staticmethod

195 def to_tree(prufer):

196 """Return the tree (as a list of edges) of the given Prufer sequence.

197

198 Examples

199 ========

200

201 >>> from sympy.combinatorics.prufer import Prufer

202 >>> a = Prufer([0, 2], 4)

203 >>> a.tree_repr

204 [[0, 1], [0, 2], [2, 3]]

205 >>> Prufer.to_tree([0, 2])

206 [[0, 1], [0, 2], [2, 3]]

207

208 References

209 ==========

210

211 .. [1] https://hamberg.no/erlend/posts/2010-11-06-prufer-sequence-compact-tree-representation.html

212

213 See Also

214 ========

215 tree_repr: returns tree representation of a Prufer object.

216

217 """

218 tree = []

219 last = []

220 n = len(prufer) + 2

221 d = defaultdict(lambda: 1)

222 for p in prufer:

223 d[p] += 1

224 for i in prufer:

225 for j in range(n):

226 # find the smallest leaf (degree = 1)

227 if d[j] == 1:

228 break

229 # (i, j) is the new edge that we append to the tree

230 # and remove from the degree dictionary

231 d[i] -= 1

232 d[j] -= 1

233 tree.append(sorted([i, j]))

234 last = [i for i in range(n) if d[i] == 1] or [0, 1]

235 tree.append(last)

236

237 return tree

238

239 @staticmethod

240 def edges(*runs):

241 """Return a list of edges and the number of nodes from the given runs

242 that connect nodes in an integer-labelled tree.

243

244 All node numbers will be shifted so that the minimum node is 0. It is

245 not a problem if edges are repeated in the runs; only unique edges are

246 returned. There is no assumption made about what the range of the node

247 labels should be, but all nodes from the smallest through the largest

248 must be present.

249

250 Examples

251 ========

252

253 >>> from sympy.combinatorics.prufer import Prufer

254 >>> Prufer.edges([1, 2, 3], [2, 4, 5]) # a T

255 ([[0, 1], [1, 2], [1, 3], [3, 4]], 5)

256

257 Duplicate edges are removed:

258

259 >>> Prufer.edges([0, 1, 2, 3], [1, 4, 5], [1, 4, 6]) # a K

260 ([[0, 1], [1, 2], [1, 4], [2, 3], [4, 5], [4, 6]], 7)

261

262 """

263 e = set()

264 nmin = runs[0][0]

265 for r in runs:

266 for i in range(len(r) - 1):

267 a, b = r[i: i + 2]

268 if b < a:

269 a, b = b, a

270 e.add((a, b))

271 rv = []

272 got = set()

273 nmin = nmax = None

274 for ei in e:

275 for i in ei:

276 got.add(i)

277 nmin = min(ei[0], nmin) if nmin is not None else ei[0]

278 nmax = max(ei[1], nmax) if nmax is not None else ei[1]

279 rv.append(list(ei))

280 missing = set(range(nmin, nmax + 1)) - got

281 if missing:

282 missing = [i + nmin for i in missing]

283 if len(missing) == 1:

284 msg = 'Node %s is missing.' % missing.pop()

285 else:

286 msg = 'Nodes %s are missing.' % sorted(missing)

287 raise ValueError(msg)

288 if nmin != 0:

289 for i, ei in enumerate(rv):

290 rv[i] = [n - nmin for n in ei]

291 nmax -= nmin

292 return sorted(rv), nmax + 1

293

294 def prufer_rank(self):

295 """Computes the rank of a Prufer sequence.

296

297 Examples

298 ========

299

300 >>> from sympy.combinatorics.prufer import Prufer

301 >>> a = Prufer([[0, 1], [0, 2], [0, 3]])

302 >>> a.prufer_rank()

303 0

304

305 See Also

306 ========

307

308 rank, next, prev, size

309

310 """

311 r = 0

312 p = 1

313 for i in range(self.nodes - 3, -1, -1):

314 r += p*self.prufer_repr[i]

315 p *= self.nodes

316 return r

317

318 @classmethod

319 def unrank(self, rank, n):

320 """Finds the unranked Prufer sequence.

321

322 Examples

323 ========

324

325 >>> from sympy.combinatorics.prufer import Prufer

326 >>> Prufer.unrank(0, 4)

327 Prufer([0, 0])

328

329 """

330 n, rank = as_int(n), as_int(rank)

331 L = defaultdict(int)

332 for i in range(n - 3, -1, -1):

333 L[i] = rank % n

334 rank = (rank - L[i])//n

335 return Prufer([L[i] for i in range(len(L))])

336

337 def __new__(cls, *args, **kw_args):

338 """The constructor for the Prufer object.

339

340 Examples

341 ========

342

343 >>> from sympy.combinatorics.prufer import Prufer

344

345 A Prufer object can be constructed from a list of edges:

346

347 >>> a = Prufer([[0, 1], [0, 2], [0, 3]])

348 >>> a.prufer_repr

349 [0, 0]

350

351 If the number of nodes is given, no checking of the nodes will

352 be performed; it will be assumed that nodes 0 through n - 1 are

353 present:

354

355 >>> Prufer([[0, 1], [0, 2], [0, 3]], 4)

356 Prufer([[0, 1], [0, 2], [0, 3]], 4)

357

358 A Prufer object can be constructed from a Prufer sequence:

359

360 >>> b = Prufer([1, 3])

361 >>> b.tree_repr

362 [[0, 1], [1, 3], [2, 3]]

363

364 """

365 arg0 = Array(args[0]) if args[0] else Tuple()

366 args = (arg0,) + tuple(_sympify(arg) for arg in args[1:])

367 ret_obj = Basic.__new__(cls, *args, **kw_args)

368 args = [list(args[0])]

369 if args[0] and iterable(args[0][0]):

370 if not args[0][0]:

371 raise ValueError(

372 'Prufer expects at least one edge in the tree.')

373 if len(args) > 1:

374 nnodes = args[1]

375 else:

376 nodes = set(flatten(args[0]))

377 nnodes = max(nodes) + 1

378 if nnodes != len(nodes):

379 missing = set(range(nnodes)) - nodes

380 if len(missing) == 1:

381 msg = 'Node %s is missing.' % missing.pop()

382 else:

383 msg = 'Nodes %s are missing.' % sorted(missing)

384 raise ValueError(msg)

385 ret_obj._tree_repr = [list(i) for i in args[0]]

386 ret_obj._nodes = nnodes

387 else:

388 ret_obj._prufer_repr = args[0]

389 ret_obj._nodes = len(ret_obj._prufer_repr) + 2

390 return ret_obj

391

392 def next(self, delta=1):

393 """Generates the Prufer sequence that is delta beyond the current one.

394

395 Examples

396 ========

397

398 >>> from sympy.combinatorics.prufer import Prufer

399 >>> a = Prufer([[0, 1], [0, 2], [0, 3]])

400 >>> b = a.next(1) # == a.next()

401 >>> b.tree_repr

402 [[0, 2], [0, 1], [1, 3]]

403 >>> b.rank

404 1

405

406 See Also

407 ========

408

409 prufer_rank, rank, prev, size

410

411 """

412 return Prufer.unrank(self.rank + delta, self.nodes)

413

414 def prev(self, delta=1):

415 """Generates the Prufer sequence that is -delta before the current one.

416

417 Examples

418 ========

419

420 >>> from sympy.combinatorics.prufer import Prufer

421 >>> a = Prufer([[0, 1], [1, 2], [2, 3], [1, 4]])

422 >>> a.rank

423 36

424 >>> b = a.prev()

425 >>> b

426 Prufer([1, 2, 0])

427 >>> b.rank

428 35

429

430 See Also

431 ========

432

433 prufer_rank, rank, next, size

434

435 """

436 return Prufer.unrank(self.rank -delta, self.nodes)