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

History | View | Annotate | Download (4.19 KB)

1 | 5cef0f13 | tiamilani | ```
# 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)` |