Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (8.74 KB)

1
#!/usr/bin/env python
2
from nose.tools import *
3
import networkx as nx
4
from networkx import convert_node_labels_to_integers as cnlti
5

    
6

    
7
class TestCliques:
8

    
9
    def setUp(self):
10
        z = [3, 4, 3, 4, 2, 4, 2, 1, 1, 1, 1]
11
        self.G = cnlti(nx.generators.havel_hakimi_graph(z), first_label=1)
12
        self.cl = list(nx.find_cliques(self.G))
13
        H = nx.complete_graph(6)
14
        H = nx.relabel_nodes(H, dict([(i, i + 1) for i in range(6)]))
15
        H.remove_edges_from([(2, 6), (2, 5), (2, 4), (1, 3), (5, 3)])
16
        self.H = H
17

    
18
    def test_find_cliques1(self):
19
        cl = list(nx.find_cliques(self.G))
20
        rcl = nx.find_cliques_recursive(self.G)
21
        expected = [[2, 6, 1, 3], [2, 6, 4], [5, 4, 7], [8, 9], [10, 11]]
22
        assert_equal(sorted(map(sorted, cl)), sorted(map(sorted, rcl)))
23
        assert_equal(sorted(map(sorted, cl)), sorted(map(sorted, expected)))
24

    
25
    def test_selfloops(self):
26
        self.G.add_edge(1, 1)
27
        cl = list(nx.find_cliques(self.G))
28
        rcl = nx.find_cliques_recursive(self.G)
29
        assert_equal(sorted(map(sorted, cl)), sorted(map(sorted, rcl)))
30
        assert_equal(cl,
31
                     [[2, 6, 1, 3], [2, 6, 4], [5, 4, 7], [8, 9], [10, 11]])
32

    
33
    def test_find_cliques2(self):
34
        hcl = list(nx.find_cliques(self.H))
35
        assert_equal(sorted(map(sorted, hcl)),
36
                     [[1, 2], [1, 4, 5, 6], [2, 3], [3, 4, 6]])
37

    
38
    def test_clique_number(self):
39
        G = self.G
40
        assert_equal(nx.graph_clique_number(G), 4)
41
        assert_equal(nx.graph_clique_number(G, cliques=self.cl), 4)
42

    
43
    def test_clique_number2(self):
44
        G = nx.Graph()
45
        G.add_nodes_from([1, 2, 3])
46
        assert_equal(nx.graph_clique_number(G), 1)
47

    
48
    def test_clique_number3(self):
49
        G = nx.Graph()
50
        assert_equal(nx.graph_clique_number(G), 0)
51

    
52
    def test_number_of_cliques(self):
53
        G = self.G
54
        assert_equal(nx.graph_number_of_cliques(G), 5)
55
        assert_equal(nx.graph_number_of_cliques(G, cliques=self.cl), 5)
56
        assert_equal(nx.number_of_cliques(G, 1), 1)
57
        assert_equal(list(nx.number_of_cliques(G, [1]).values()), [1])
58
        assert_equal(list(nx.number_of_cliques(G, [1, 2]).values()), [1, 2])
59
        assert_equal(nx.number_of_cliques(G, [1, 2]), {1: 1, 2: 2})
60
        assert_equal(nx.number_of_cliques(G, 2), 2)
61
        assert_equal(nx.number_of_cliques(G),
62
                     {1: 1, 2: 2, 3: 1, 4: 2, 5: 1,
63
                      6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1})
64
        assert_equal(nx.number_of_cliques(G, nodes=list(G)),
65
                     {1: 1, 2: 2, 3: 1, 4: 2, 5: 1,
66
                      6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1})
67
        assert_equal(nx.number_of_cliques(G, nodes=[2, 3, 4]),
68
                     {2: 2, 3: 1, 4: 2})
69
        assert_equal(nx.number_of_cliques(G, cliques=self.cl),
70
                     {1: 1, 2: 2, 3: 1, 4: 2, 5: 1,
71
                      6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1})
72
        assert_equal(nx.number_of_cliques(G, list(G), cliques=self.cl),
73
                     {1: 1, 2: 2, 3: 1, 4: 2, 5: 1,
74
                      6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1})
75

    
76
    def test_node_clique_number(self):
77
        G = self.G
78
        assert_equal(nx.node_clique_number(G, 1), 4)
79
        assert_equal(list(nx.node_clique_number(G, [1]).values()), [4])
80
        assert_equal(list(nx.node_clique_number(G, [1, 2]).values()), [4, 4])
81
        assert_equal(nx.node_clique_number(G, [1, 2]), {1: 4, 2: 4})
82
        assert_equal(nx.node_clique_number(G, 1), 4)
83
        assert_equal(nx.node_clique_number(G),
84
                     {1: 4, 2: 4, 3: 4, 4: 3, 5: 3, 6: 4,
85
                      7: 3, 8: 2, 9: 2, 10: 2, 11: 2})
86
        assert_equal(nx.node_clique_number(G, cliques=self.cl),
87
                     {1: 4, 2: 4, 3: 4, 4: 3, 5: 3, 6: 4,
88
                      7: 3, 8: 2, 9: 2, 10: 2, 11: 2})
89

    
90
    def test_cliques_containing_node(self):
91
        G = self.G
92
        assert_equal(nx.cliques_containing_node(G, 1),
93
                     [[2, 6, 1, 3]])
94
        assert_equal(list(nx.cliques_containing_node(G, [1]).values()),
95
                     [[[2, 6, 1, 3]]])
96
        assert_equal(list(nx.cliques_containing_node(G, [1, 2]).values()),
97
                     [[[2, 6, 1, 3]], [[2, 6, 1, 3], [2, 6, 4]]])
98
        assert_equal(nx.cliques_containing_node(G, [1, 2]),
99
                     {1: [[2, 6, 1, 3]], 2: [[2, 6, 1, 3], [2, 6, 4]]})
100
        assert_equal(nx.cliques_containing_node(G, 1),
101
                     [[2, 6, 1, 3]])
102
        assert_equal(nx.cliques_containing_node(G, 2),
103
                     [[2, 6, 1, 3], [2, 6, 4]])
104
        assert_equal(nx.cliques_containing_node(G, 2, cliques=self.cl),
105
                     [[2, 6, 1, 3], [2, 6, 4]])
106
        assert_equal(len(nx.cliques_containing_node(G)), 11)
107

    
108
    def test_make_clique_bipartite(self):
109
        G = self.G
110
        B = nx.make_clique_bipartite(G)
111
        assert_equal(sorted(B),
112
                     [-5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
113
        # Project onto the nodes of the original graph.
114
        H = nx.project(B, range(1, 12))
115
        assert_equal(H.adj, G.adj)
116
        # Project onto the nodes representing the cliques.
117
        H1 = nx.project(B, range(-5, 0))
118
        # Relabel the negative numbers as positive ones.
119
        H1 = nx.relabel_nodes(H1, {-v: v for v in range(1, 6)})
120
        assert_equal(sorted(H1), [1, 2, 3, 4, 5])
121

    
122
    def test_make_max_clique_graph(self):
123
        """Tests that the maximal clique graph is the same as the bipartite
124
        clique graph after being projected onto the nodes representing the
125
        cliques.
126

127
        """
128
        G = self.G
129
        B = nx.make_clique_bipartite(G)
130
        # Project onto the nodes representing the cliques.
131
        H1 = nx.project(B, range(-5, 0))
132
        # Relabel the negative numbers as nonnegative ones, starting at
133
        # 0.
134
        H1 = nx.relabel_nodes(H1, {-v: v - 1 for v in range(1, 6)})
135
        H2 = nx.make_max_clique_graph(G)
136
        assert_equal(H1.adj, H2.adj)
137

    
138
    @raises(nx.NetworkXNotImplemented)
139
    def test_directed(self):
140
        cliques = nx.find_cliques(nx.DiGraph())
141

    
142

    
143
class TestEnumerateAllCliques:
144

    
145
    def test_paper_figure_4(self):
146
        # Same graph as given in Fig. 4 of paper enumerate_all_cliques is
147
        # based on.
148
        # http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1559964&isnumber=33129
149
        G = nx.Graph()
150
        edges_fig_4 = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'),
151
                       ('b', 'c'), ('b', 'd'), ('b', 'e'),
152
                       ('c', 'd'), ('c', 'e'),
153
                       ('d', 'e'),
154
                       ('f', 'b'), ('f', 'c'), ('f', 'g'),
155
                       ('g', 'f'), ('g', 'c'), ('g', 'd'), ('g', 'e')]
156
        G.add_edges_from(edges_fig_4)
157

    
158
        cliques = list(nx.enumerate_all_cliques(G))
159
        clique_sizes = list(map(len, cliques))
160
        assert_equal(sorted(clique_sizes), clique_sizes)
161

    
162
        expected_cliques = [['a'],
163
                            ['b'],
164
                            ['c'],
165
                            ['d'],
166
                            ['e'],
167
                            ['f'],
168
                            ['g'],
169
                            ['a', 'b'],
170
                            ['a', 'b', 'd'],
171
                            ['a', 'b', 'd', 'e'],
172
                            ['a', 'b', 'e'],
173
                            ['a', 'c'],
174
                            ['a', 'c', 'd'],
175
                            ['a', 'c', 'd', 'e'],
176
                            ['a', 'c', 'e'],
177
                            ['a', 'd'],
178
                            ['a', 'd', 'e'],
179
                            ['a', 'e'],
180
                            ['b', 'c'],
181
                            ['b', 'c', 'd'],
182
                            ['b', 'c', 'd', 'e'],
183
                            ['b', 'c', 'e'],
184
                            ['b', 'c', 'f'],
185
                            ['b', 'd'],
186
                            ['b', 'd', 'e'],
187
                            ['b', 'e'],
188
                            ['b', 'f'],
189
                            ['c', 'd'],
190
                            ['c', 'd', 'e'],
191
                            ['c', 'd', 'e', 'g'],
192
                            ['c', 'd', 'g'],
193
                            ['c', 'e'],
194
                            ['c', 'e', 'g'],
195
                            ['c', 'f'],
196
                            ['c', 'f', 'g'],
197
                            ['c', 'g'],
198
                            ['d', 'e'],
199
                            ['d', 'e', 'g'],
200
                            ['d', 'g'],
201
                            ['e', 'g'],
202
                            ['f', 'g'],
203
                            ['a', 'b', 'c'],
204
                            ['a', 'b', 'c', 'd'],
205
                            ['a', 'b', 'c', 'd', 'e'],
206
                            ['a', 'b', 'c', 'e']]
207

    
208
        assert_equal(sorted(map(sorted, cliques)),
209
                     sorted(map(sorted, expected_cliques)))