(prefix_tree_fn)
| 8 | |
| 9 | @pytest.mark.parametrize("prefix_tree_fn", (nx.prefix_tree, nx.prefix_tree_recursive)) |
| 10 | def test_basic_prefix_tree(prefix_tree_fn): |
| 11 | # This example is from the Wikipedia article "Trie" |
| 12 | # <https://en.wikipedia.org/wiki/Trie>. |
| 13 | strings = ["a", "to", "tea", "ted", "ten", "i", "in", "inn"] |
| 14 | T = prefix_tree_fn(strings) |
| 15 | root, NIL = 0, -1 |
| 16 | |
| 17 | def source_label(v): |
| 18 | return T.nodes[v]["source"] |
| 19 | |
| 20 | # First, we check that the tree has the expected |
| 21 | # structure. Recall that each node that corresponds to one of |
| 22 | # the input strings has an edge to the NIL node. |
| 23 | # |
| 24 | # Consider the three children at level 1 in the trie. |
| 25 | a, i, t = sorted(T[root], key=source_label) |
| 26 | # Check the 'a' branch. |
| 27 | assert len(T[a]) == 1 |
| 28 | nil = arbitrary_element(T[a]) |
| 29 | assert len(T[nil]) == 0 |
| 30 | # Check the 'i' branch. |
| 31 | assert len(T[i]) == 2 |
| 32 | nil, in_ = sorted(T[i], key=source_label) |
| 33 | assert len(T[nil]) == 0 |
| 34 | assert len(T[in_]) == 2 |
| 35 | nil, inn = sorted(T[in_], key=source_label) |
| 36 | assert len(T[nil]) == 0 |
| 37 | assert len(T[inn]) == 1 |
| 38 | nil = arbitrary_element(T[inn]) |
| 39 | assert len(T[nil]) == 0 |
| 40 | # Check the 't' branch. |
| 41 | te, to = sorted(T[t], key=source_label) |
| 42 | assert len(T[to]) == 1 |
| 43 | nil = arbitrary_element(T[to]) |
| 44 | assert len(T[nil]) == 0 |
| 45 | tea, ted, ten = sorted(T[te], key=source_label) |
| 46 | assert len(T[tea]) == 1 |
| 47 | assert len(T[ted]) == 1 |
| 48 | assert len(T[ten]) == 1 |
| 49 | nil = arbitrary_element(T[tea]) |
| 50 | assert len(T[nil]) == 0 |
| 51 | nil = arbitrary_element(T[ted]) |
| 52 | assert len(T[nil]) == 0 |
| 53 | nil = arbitrary_element(T[ten]) |
| 54 | assert len(T[nil]) == 0 |
| 55 | |
| 56 | # Next, we check that the "sources" of each of the nodes is the |
| 57 | # rightmost letter in the string corresponding to the path to |
| 58 | # that node. |
| 59 | assert source_label(root) is None |
| 60 | assert source_label(a) == "a" |
| 61 | assert source_label(i) == "i" |
| 62 | assert source_label(t) == "t" |
| 63 | assert source_label(in_) == "n" |
| 64 | assert source_label(inn) == "n" |
| 65 | assert source_label(to) == "o" |
| 66 | assert source_label(te) == "e" |
| 67 | assert source_label(tea) == "a" |
nothing calls this directly
no test coverage detected
searching dependent graphs…