File size: 4,363 Bytes
f911107 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
"""Unit tests for the chain decomposition functions."""
from itertools import cycle, islice
import pytest
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)
def test_chain_decomposition_root_not_in_G(self):
"""Test chain decomposition when root is not in graph"""
G = nx.Graph()
G.add_nodes_from([1, 2, 3])
with pytest.raises(nx.NodeNotFound):
nx.has_bridges(G, root=6)
|