Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tree/tests/test_coding.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 """Unit tests for the :mod:`~networkx.algorithms.tree.coding` module.""" | |
2 from itertools import product | |
3 | |
4 import pytest | |
5 import networkx as nx | |
6 from networkx.testing import assert_nodes_equal | |
7 from networkx.testing import assert_edges_equal | |
8 | |
9 | |
10 class TestPruferSequence: | |
11 """Unit tests for the Prüfer sequence encoding and decoding | |
12 functions. | |
13 | |
14 """ | |
15 | |
16 def test_nontree(self): | |
17 with pytest.raises(nx.NotATree): | |
18 G = nx.cycle_graph(3) | |
19 nx.to_prufer_sequence(G) | |
20 | |
21 def test_null_graph(self): | |
22 with pytest.raises(nx.NetworkXPointlessConcept): | |
23 nx.to_prufer_sequence(nx.null_graph()) | |
24 | |
25 def test_trivial_graph(self): | |
26 with pytest.raises(nx.NetworkXPointlessConcept): | |
27 nx.to_prufer_sequence(nx.trivial_graph()) | |
28 | |
29 def test_bad_integer_labels(self): | |
30 with pytest.raises(KeyError): | |
31 T = nx.Graph(nx.utils.pairwise("abc")) | |
32 nx.to_prufer_sequence(T) | |
33 | |
34 def test_encoding(self): | |
35 """Tests for encoding a tree as a Prüfer sequence using the | |
36 iterative strategy. | |
37 | |
38 """ | |
39 # Example from Wikipedia. | |
40 tree = nx.Graph([(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]) | |
41 sequence = nx.to_prufer_sequence(tree) | |
42 assert sequence == [3, 3, 3, 4] | |
43 | |
44 def test_decoding(self): | |
45 """Tests for decoding a tree from a Prüfer sequence.""" | |
46 # Example from Wikipedia. | |
47 sequence = [3, 3, 3, 4] | |
48 tree = nx.from_prufer_sequence(sequence) | |
49 assert_nodes_equal(list(tree), list(range(6))) | |
50 edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)] | |
51 assert_edges_equal(list(tree.edges()), edges) | |
52 | |
53 def test_decoding2(self): | |
54 # Example from "An Optimal Algorithm for Prufer Codes". | |
55 sequence = [2, 4, 0, 1, 3, 3] | |
56 tree = nx.from_prufer_sequence(sequence) | |
57 assert_nodes_equal(list(tree), list(range(8))) | |
58 edges = [(0, 1), (0, 4), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)] | |
59 assert_edges_equal(list(tree.edges()), edges) | |
60 | |
61 def test_inverse(self): | |
62 """Tests that the encoding and decoding functions are inverses. | |
63 | |
64 """ | |
65 for T in nx.nonisomorphic_trees(4): | |
66 T2 = nx.from_prufer_sequence(nx.to_prufer_sequence(T)) | |
67 assert_nodes_equal(list(T), list(T2)) | |
68 assert_edges_equal(list(T.edges()), list(T2.edges())) | |
69 | |
70 for seq in product(range(4), repeat=2): | |
71 seq2 = nx.to_prufer_sequence(nx.from_prufer_sequence(seq)) | |
72 assert list(seq) == seq2 | |
73 | |
74 | |
75 class TestNestedTuple: | |
76 """Unit tests for the nested tuple encoding and decoding functions. | |
77 | |
78 """ | |
79 | |
80 def test_nontree(self): | |
81 with pytest.raises(nx.NotATree): | |
82 G = nx.cycle_graph(3) | |
83 nx.to_nested_tuple(G, 0) | |
84 | |
85 def test_unknown_root(self): | |
86 with pytest.raises(nx.NodeNotFound): | |
87 G = nx.path_graph(2) | |
88 nx.to_nested_tuple(G, "bogus") | |
89 | |
90 def test_encoding(self): | |
91 T = nx.full_rary_tree(2, 2 ** 3 - 1) | |
92 expected = (((), ()), ((), ())) | |
93 actual = nx.to_nested_tuple(T, 0) | |
94 assert_nodes_equal(expected, actual) | |
95 | |
96 def test_canonical_form(self): | |
97 T = nx.Graph() | |
98 T.add_edges_from([(0, 1), (0, 2), (0, 3)]) | |
99 T.add_edges_from([(1, 4), (1, 5)]) | |
100 T.add_edges_from([(3, 6), (3, 7)]) | |
101 root = 0 | |
102 actual = nx.to_nested_tuple(T, root, canonical_form=True) | |
103 expected = ((), ((), ()), ((), ())) | |
104 assert actual == expected | |
105 | |
106 def test_decoding(self): | |
107 balanced = (((), ()), ((), ())) | |
108 expected = nx.full_rary_tree(2, 2 ** 3 - 1) | |
109 actual = nx.from_nested_tuple(balanced) | |
110 assert nx.is_isomorphic(expected, actual) | |
111 | |
112 def test_sensible_relabeling(self): | |
113 balanced = (((), ()), ((), ())) | |
114 T = nx.from_nested_tuple(balanced, sensible_relabeling=True) | |
115 edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)] | |
116 assert_nodes_equal(list(T), list(range(2 ** 3 - 1))) | |
117 assert_edges_equal(list(T.edges()), edges) |