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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
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:

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)
```