### comparison env/lib/python3.9/site-packages/networkx/generators/tests/test_trees.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 import networkx as nx
2 from networkx.generators.trees import NIL
3 from networkx.utils import arbitrary_element
4
5
6 class TestPrefixTree:
7 """Unit tests for the prefix tree generator function."""
8
9 def test_basic(self):
10 # This example is from the Wikipedia article "Trie"
11 # <https://en.wikipedia.org/wiki/Trie>.
12 strings = ["a", "to", "tea", "ted", "ten", "i", "in", "inn"]
13 T, root = nx.prefix_tree(strings)
14
15 def source_label(v):
16 return T.nodes[v]["source"]
17
18 # First, we check that the tree has the expected
19 # structure. Recall that each node that corresponds to one of
20 # the input strings has an edge to the NIL node.
21 #
22 # Consider the three children at level 1 in the trie.
23 a, i, t = sorted(T[root], key=source_label)
24 # Check the 'a' branch.
25 assert len(T[a]) == 1
26 nil = arbitrary_element(T[a])
27 assert len(T[nil]) == 0
28 # Check the 'i' branch.
29 assert len(T[i]) == 2
30 nil, in_ = sorted(T[i], key=source_label)
31 assert len(T[nil]) == 0
32 assert len(T[in_]) == 2
33 nil, inn = sorted(T[in_], key=source_label)
34 assert len(T[nil]) == 0
35 assert len(T[inn]) == 1
36 nil = arbitrary_element(T[inn])
37 assert len(T[nil]) == 0
38 # Check the 't' branch.
39 te, to = sorted(T[t], key=source_label)
40 assert len(T[to]) == 1
41 nil = arbitrary_element(T[to])
42 assert len(T[nil]) == 0
43 tea, ted, ten = sorted(T[te], key=source_label)
44 assert len(T[tea]) == 1
45 assert len(T[ted]) == 1
46 assert len(T[ten]) == 1
47 nil = arbitrary_element(T[tea])
48 assert len(T[nil]) == 0
49 nil = arbitrary_element(T[ted])
50 assert len(T[nil]) == 0
51 nil = arbitrary_element(T[ten])
52 assert len(T[nil]) == 0
53
54 # Next, we check that the "sources" of each of the nodes is the
55 # rightmost letter in the string corresponding to the path to
56 # that node.
57 assert source_label(root) is None
58 assert source_label(a) == "a"
59 assert source_label(i) == "i"
60 assert source_label(t) == "t"
61 assert source_label(in_) == "n"
62 assert source_label(inn) == "n"
63 assert source_label(to) == "o"
64 assert source_label(te) == "e"
65 assert source_label(tea) == "a"
66 assert source_label(ted) == "d"
67 assert source_label(ten) == "n"
68 assert source_label(NIL) == NIL
69
70
71 def test_random_tree():
72 """Tests that a random tree is in fact a tree."""
73 T = nx.random_tree(10, seed=1234)
74 assert nx.is_tree(T)