aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_chains.py
blob: 09b4c734535f501b14f9d1f6eb94452d38170e50 (about) (plain)
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)