133 lines
4.0 KiB
Python
133 lines
4.0 KiB
Python
|
"""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)
|