Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/tests/test_trees.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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) |