Spaces:
Running
Running
File size: 2,649 Bytes
6a86ad5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
from sympy.combinatorics.prufer import Prufer
from sympy.testing.pytest import raises
def test_prufer():
# number of nodes is optional
assert Prufer([[0, 1], [0, 2], [0, 3], [0, 4]], 5).nodes == 5
assert Prufer([[0, 1], [0, 2], [0, 3], [0, 4]]).nodes == 5
a = Prufer([[0, 1], [0, 2], [0, 3], [0, 4]])
assert a.rank == 0
assert a.nodes == 5
assert a.prufer_repr == [0, 0, 0]
a = Prufer([[2, 4], [1, 4], [1, 3], [0, 5], [0, 4]])
assert a.rank == 924
assert a.nodes == 6
assert a.tree_repr == [[2, 4], [1, 4], [1, 3], [0, 5], [0, 4]]
assert a.prufer_repr == [4, 1, 4, 0]
assert Prufer.edges([0, 1, 2, 3], [1, 4, 5], [1, 4, 6]) == \
([[0, 1], [1, 2], [1, 4], [2, 3], [4, 5], [4, 6]], 7)
assert Prufer([0]*4).size == Prufer([6]*4).size == 1296
# accept iterables but convert to list of lists
tree = [(0, 1), (1, 5), (0, 3), (0, 2), (2, 6), (4, 7), (2, 4)]
tree_lists = [list(t) for t in tree]
assert Prufer(tree).tree_repr == tree_lists
assert sorted(Prufer(set(tree)).tree_repr) == sorted(tree_lists)
raises(ValueError, lambda: Prufer([[1, 2], [3, 4]])) # 0 is missing
raises(ValueError, lambda: Prufer([[2, 3], [3, 4]])) # 0, 1 are missing
assert Prufer(*Prufer.edges([1, 2], [3, 4])).prufer_repr == [1, 3]
raises(ValueError, lambda: Prufer.edges(
[1, 3], [3, 4])) # a broken tree but edges doesn't care
raises(ValueError, lambda: Prufer.edges([1, 2], [5, 6]))
raises(ValueError, lambda: Prufer([[]]))
a = Prufer([[0, 1], [0, 2], [0, 3]])
b = a.next()
assert b.tree_repr == [[0, 2], [0, 1], [1, 3]]
assert b.rank == 1
def test_round_trip():
def doit(t, b):
e, n = Prufer.edges(*t)
t = Prufer(e, n)
a = sorted(t.tree_repr)
b = [i - 1 for i in b]
assert t.prufer_repr == b
assert sorted(Prufer(b).tree_repr) == a
assert Prufer.unrank(t.rank, n).prufer_repr == b
doit([[1, 2]], [])
doit([[2, 1, 3]], [1])
doit([[1, 3, 2]], [3])
doit([[1, 2, 3]], [2])
doit([[2, 1, 4], [1, 3]], [1, 1])
doit([[3, 2, 1, 4]], [2, 1])
doit([[3, 2, 1], [2, 4]], [2, 2])
doit([[1, 3, 2, 4]], [3, 2])
doit([[1, 4, 2, 3]], [4, 2])
doit([[3, 1, 4, 2]], [4, 1])
doit([[4, 2, 1, 3]], [1, 2])
doit([[1, 2, 4, 3]], [2, 4])
doit([[1, 3, 4, 2]], [3, 4])
doit([[2, 4, 1], [4, 3]], [4, 4])
doit([[1, 2, 3, 4]], [2, 3])
doit([[2, 3, 1], [3, 4]], [3, 3])
doit([[1, 4, 3, 2]], [4, 3])
doit([[2, 1, 4, 3]], [1, 4])
doit([[2, 1, 3, 4]], [1, 3])
doit([[6, 2, 1, 4], [1, 3, 5, 8], [3, 7]], [1, 2, 1, 3, 3, 5])
|