Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_chains.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 chain decomposition functions.""" | |
2 from itertools import cycle | |
3 from itertools import islice | |
4 | |
5 import networkx as nx | |
6 | |
7 | |
8 def cycles(seq): | |
9 """Yields cyclic permutations of the given sequence. | |
10 | |
11 For example:: | |
12 | |
13 >>> list(cycles("abc")) | |
14 [('a', 'b', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b')] | |
15 | |
16 """ | |
17 n = len(seq) | |
18 cycled_seq = cycle(seq) | |
19 for x in seq: | |
20 yield tuple(islice(cycled_seq, n)) | |
21 next(cycled_seq) | |
22 | |
23 | |
24 def cyclic_equals(seq1, seq2): | |
25 """Decide whether two sequences are equal up to cyclic permutations. | |
26 | |
27 For example:: | |
28 | |
29 >>> cyclic_equals("xyz", "zxy") | |
30 True | |
31 >>> cyclic_equals("xyz", "zyx") | |
32 False | |
33 | |
34 """ | |
35 # Cast seq2 to a tuple since `cycles()` yields tuples. | |
36 seq2 = tuple(seq2) | |
37 return any(x == tuple(seq2) for x in cycles(seq1)) | |
38 | |
39 | |
40 class TestChainDecomposition: | |
41 """Unit tests for the chain decomposition function.""" | |
42 | |
43 def assertContainsChain(self, chain, expected): | |
44 # A cycle could be expressed in two different orientations, one | |
45 # forward and one backward, so we need to check for cyclic | |
46 # equality in both orientations. | |
47 reversed_chain = list(reversed([tuple(reversed(e)) for e in chain])) | |
48 for candidate in expected: | |
49 if cyclic_equals(chain, candidate): | |
50 break | |
51 if cyclic_equals(reversed_chain, candidate): | |
52 break | |
53 else: | |
54 self.fail("chain not found") | |
55 | |
56 def test_decomposition(self): | |
57 edges = [ | |
58 # DFS tree edges. | |
59 (1, 2), | |
60 (2, 3), | |
61 (3, 4), | |
62 (3, 5), | |
63 (5, 6), | |
64 (6, 7), | |
65 (7, 8), | |
66 (5, 9), | |
67 (9, 10), | |
68 # Nontree edges. | |
69 (1, 3), | |
70 (1, 4), | |
71 (2, 5), | |
72 (5, 10), | |
73 (6, 8), | |
74 ] | |
75 G = nx.Graph(edges) | |
76 expected = [ | |
77 [(1, 3), (3, 2), (2, 1)], | |
78 [(1, 4), (4, 3)], | |
79 [(2, 5), (5, 3)], | |
80 [(5, 10), (10, 9), (9, 5)], | |
81 [(6, 8), (8, 7), (7, 6)], | |
82 ] | |
83 chains = list(nx.chain_decomposition(G, root=1)) | |
84 assert len(chains) == len(expected) | |
85 | |
86 # This chain decomposition isn't unique | |
87 # for chain in chains: | |
88 # print(chain) | |
89 # self.assertContainsChain(chain, expected) | |
90 | |
91 def test_barbell_graph(self): | |
92 # The (3, 0) barbell graph has two triangles joined by a single edge. | |
93 G = nx.barbell_graph(3, 0) | |
94 chains = list(nx.chain_decomposition(G, root=0)) | |
95 expected = [[(0, 1), (1, 2), (2, 0)], [(3, 4), (4, 5), (5, 3)]] | |
96 assert len(chains) == len(expected) | |
97 for chain in chains: | |
98 self.assertContainsChain(chain, expected) | |
99 | |
100 def test_disconnected_graph(self): | |
101 """Test for a graph with multiple connected components.""" | |
102 G = nx.barbell_graph(3, 0) | |
103 H = nx.barbell_graph(3, 0) | |
104 mapping = dict(zip(range(6), "abcdef")) | |
105 nx.relabel_nodes(H, mapping, copy=False) | |
106 G = nx.union(G, H) | |
107 chains = list(nx.chain_decomposition(G)) | |
108 expected = [ | |
109 [(0, 1), (1, 2), (2, 0)], | |
110 [(3, 4), (4, 5), (5, 3)], | |
111 [("a", "b"), ("b", "c"), ("c", "a")], | |
112 [("d", "e"), ("e", "f"), ("f", "d")], | |
113 ] | |
114 assert len(chains) == len(expected) | |
115 for chain in chains: | |
116 self.assertContainsChain(chain, expected) | |
117 | |
118 def test_disconnected_graph_root_node(self): | |
119 """Test for a single component of a disconnected graph.""" | |
120 G = nx.barbell_graph(3, 0) | |
121 H = nx.barbell_graph(3, 0) | |
122 mapping = dict(zip(range(6), "abcdef")) | |
123 nx.relabel_nodes(H, mapping, copy=False) | |
124 G = nx.union(G, H) | |
125 chains = list(nx.chain_decomposition(G, root="a")) | |
126 expected = [ | |
127 [("a", "b"), ("b", "c"), ("c", "a")], | |
128 [("d", "e"), ("e", "f"), ("f", "d")], | |
129 ] | |
130 assert len(chains) == len(expected) | |
131 for chain in chains: | |
132 self.assertContainsChain(chain, expected) |