Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tests / test_chains.py @ 5cef0f13

History | View | Annotate | Download (4.19 KB)

1
# test_chains.py - unit tests for the chains module
2
#
3
# Copyright 2004-2019 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Unit tests for the chain decomposition functions."""
10
from itertools import cycle
11
from itertools import islice
12
from unittest import TestCase
13

    
14
import networkx as nx
15

    
16

    
17
def cycles(seq):
18
    """Yields cyclic permutations of the given sequence.
19

20
    For example::
21

22
        >>> list(cycles('abc'))
23
        [('a', 'b', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b')]
24

25
    """
26
    n = len(seq)
27
    cycled_seq = cycle(seq)
28
    for x in seq:
29
        yield tuple(islice(cycled_seq, n))
30
        next(cycled_seq)
31

    
32

    
33
def cyclic_equals(seq1, seq2):
34
    """Decide whether two sequences are equal up to cyclic permutations.
35

36
    For example::
37

38
        >>> cyclic_equals('xyz', 'zxy')
39
        True
40
        >>> cyclic_equals('xyz', 'zyx')
41
        False
42

43
    """
44
    # Cast seq2 to a tuple since `cycles()` yields tuples.
45
    seq2 = tuple(seq2)
46
    return any(x == tuple(seq2) for x in cycles(seq1))
47

    
48

    
49
class TestChainDecomposition(TestCase):
50
    """Unit tests for the chain decomposition function."""
51

    
52
    def assertContainsChain(self, chain, expected):
53
        # A cycle could be expressed in two different orientations, one
54
        # forward and one backward, so we need to check for cyclic
55
        # equality in both orientations.
56
        reversed_chain = list(reversed([tuple(reversed(e)) for e in chain]))
57
        for candidate in expected:
58
            if cyclic_equals(chain, candidate):
59
                break
60
            if cyclic_equals(reversed_chain, candidate):
61
                break
62
        else:
63
            self.fail('chain not found')
64

    
65
    def test_decomposition(self):
66
        edges = [
67
            # DFS tree edges.
68
            (1, 2), (2, 3), (3, 4), (3, 5), (5, 6), (6, 7), (7, 8), (5, 9),
69
            (9, 10),
70
            # Nontree edges.
71
            (1, 3), (1, 4), (2, 5), (5, 10), (6, 8)
72
        ]
73
        G = nx.Graph(edges)
74
        expected = [
75
            [(1, 3), (3, 2), (2, 1)],
76
            [(1, 4), (4, 3)],
77
            [(2, 5), (5, 3)],
78
            [(5, 10), (10, 9), (9, 5)],
79
            [(6, 8), (8, 7), (7, 6)],
80
        ]
81
        chains = list(nx.chain_decomposition(G, root=1))
82
        self.assertEqual(len(chains), len(expected))
83
# This chain decomposition isn't unique
84
#        for chain in chains:
85
#            print(chain)
86
#            self.assertContainsChain(chain, expected)
87

    
88
    def test_barbell_graph(self):
89
        # The (3, 0) barbell graph has two triangles joined by a single edge.
90
        G = nx.barbell_graph(3, 0)
91
        chains = list(nx.chain_decomposition(G, root=0))
92
        expected = [
93
            [(0, 1), (1, 2), (2, 0)],
94
            [(3, 4), (4, 5), (5, 3)],
95
        ]
96
        self.assertEqual(len(chains), len(expected))
97
        for chain in chains:
98
            self.assertContainsChain(chain, expected)
99

    
100
    def test_disconnected_graph(self):
101
        """Test for a graph with multiple connected components."""
102
        G = nx.barbell_graph(3, 0)
103
        H = nx.barbell_graph(3, 0)
104
        mapping = dict(zip(range(6), 'abcdef'))
105
        nx.relabel_nodes(H, mapping, copy=False)
106
        G = nx.union(G, H)
107
        chains = list(nx.chain_decomposition(G))
108
        expected = [
109
            [(0, 1), (1, 2), (2, 0)],
110
            [(3, 4), (4, 5), (5, 3)],
111
            [('a', 'b'), ('b', 'c'), ('c', 'a')],
112
            [('d', 'e'), ('e', 'f'), ('f', 'd')],
113
        ]
114
        self.assertEqual(len(chains), len(expected))
115
        for chain in chains:
116
            self.assertContainsChain(chain, expected)
117

    
118
    def test_disconnected_graph_root_node(self):
119
        """Test for a single component of a disconnected graph."""
120
        G = nx.barbell_graph(3, 0)
121
        H = nx.barbell_graph(3, 0)
122
        mapping = dict(zip(range(6), 'abcdef'))
123
        nx.relabel_nodes(H, mapping, copy=False)
124
        G = nx.union(G, H)
125
        chains = list(nx.chain_decomposition(G, root='a'))
126
        expected = [
127
            [('a', 'b'), ('b', 'c'), ('c', 'a')],
128
            [('d', 'e'), ('e', 'f'), ('f', 'd')],
129
        ]
130
        self.assertEqual(len(chains), len(expected))
131
        for chain in chains:
132
            self.assertContainsChain(chain, expected)