## Mercurial > repos > shellac > sam_consensus_v3

### view env/lib/python3.9/site-packages/networkx/algorithms/tests/test_chains.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

line wrap: on

line source

"""Unit tests for the chain decomposition functions.""" from itertools import cycle from itertools import islice import networkx as nx def cycles(seq): """Yields cyclic permutations of the given sequence. For example:: >>> list(cycles("abc")) [('a', 'b', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b')] """ n = len(seq) cycled_seq = cycle(seq) for x in seq: yield tuple(islice(cycled_seq, n)) next(cycled_seq) def cyclic_equals(seq1, seq2): """Decide whether two sequences are equal up to cyclic permutations. For example:: >>> cyclic_equals("xyz", "zxy") True >>> cyclic_equals("xyz", "zyx") False """ # Cast seq2 to a tuple since `cycles()` yields tuples. seq2 = tuple(seq2) return any(x == tuple(seq2) for x in cycles(seq1)) class TestChainDecomposition: """Unit tests for the chain decomposition function.""" def assertContainsChain(self, chain, expected): # A cycle could be expressed in two different orientations, one # forward and one backward, so we need to check for cyclic # equality in both orientations. reversed_chain = list(reversed([tuple(reversed(e)) for e in chain])) for candidate in expected: if cyclic_equals(chain, candidate): break if cyclic_equals(reversed_chain, candidate): break else: self.fail("chain not found") def test_decomposition(self): edges = [ # DFS tree edges. (1, 2), (2, 3), (3, 4), (3, 5), (5, 6), (6, 7), (7, 8), (5, 9), (9, 10), # Nontree edges. (1, 3), (1, 4), (2, 5), (5, 10), (6, 8), ] G = nx.Graph(edges) expected = [ [(1, 3), (3, 2), (2, 1)], [(1, 4), (4, 3)], [(2, 5), (5, 3)], [(5, 10), (10, 9), (9, 5)], [(6, 8), (8, 7), (7, 6)], ] chains = list(nx.chain_decomposition(G, root=1)) assert len(chains) == len(expected) # This chain decomposition isn't unique # for chain in chains: # print(chain) # self.assertContainsChain(chain, expected) def test_barbell_graph(self): # The (3, 0) barbell graph has two triangles joined by a single edge. G = nx.barbell_graph(3, 0) chains = list(nx.chain_decomposition(G, root=0)) expected = [[(0, 1), (1, 2), (2, 0)], [(3, 4), (4, 5), (5, 3)]] assert len(chains) == len(expected) for chain in chains: self.assertContainsChain(chain, expected) def test_disconnected_graph(self): """Test for a graph with multiple connected components.""" G = nx.barbell_graph(3, 0) H = nx.barbell_graph(3, 0) mapping = dict(zip(range(6), "abcdef")) nx.relabel_nodes(H, mapping, copy=False) G = nx.union(G, H) chains = list(nx.chain_decomposition(G)) expected = [ [(0, 1), (1, 2), (2, 0)], [(3, 4), (4, 5), (5, 3)], [("a", "b"), ("b", "c"), ("c", "a")], [("d", "e"), ("e", "f"), ("f", "d")], ] assert len(chains) == len(expected) for chain in chains: self.assertContainsChain(chain, expected) def test_disconnected_graph_root_node(self): """Test for a single component of a disconnected graph.""" G = nx.barbell_graph(3, 0) H = nx.barbell_graph(3, 0) mapping = dict(zip(range(6), "abcdef")) nx.relabel_nodes(H, mapping, copy=False) G = nx.union(G, H) chains = list(nx.chain_decomposition(G, root="a")) expected = [ [("a", "b"), ("b", "c"), ("c", "a")], [("d", "e"), ("e", "f"), ("f", "d")], ] assert len(chains) == len(expected) for chain in chains: self.assertContainsChain(chain, expected)