Statistics
| Branch: | Revision:

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

 1 ```#!/usr/bin/env python ``` ```from nose.tools import * ``` ```import networkx as nx ``` ```from networkx import convert_node_labels_to_integers as cnlti ``` ```class TestCliques: ``` ``` def setUp(self): ``` ``` z = [3, 4, 3, 4, 2, 4, 2, 1, 1, 1, 1] ``` ``` self.G = cnlti(nx.generators.havel_hakimi_graph(z), first_label=1) ``` ``` self.cl = list(nx.find_cliques(self.G)) ``` ``` H = nx.complete_graph(6) ``` ``` H = nx.relabel_nodes(H, dict([(i, i + 1) for i in range(6)])) ``` ``` H.remove_edges_from([(2, 6), (2, 5), (2, 4), (1, 3), (5, 3)]) ``` ``` self.H = H ``` ``` def test_find_cliques1(self): ``` ``` cl = list(nx.find_cliques(self.G)) ``` ``` rcl = nx.find_cliques_recursive(self.G) ``` ``` expected = [[2, 6, 1, 3], [2, 6, 4], [5, 4, 7], [8, 9], [10, 11]] ``` ``` assert_equal(sorted(map(sorted, cl)), sorted(map(sorted, rcl))) ``` ``` assert_equal(sorted(map(sorted, cl)), sorted(map(sorted, expected))) ``` ``` def test_selfloops(self): ``` ``` self.G.add_edge(1, 1) ``` ``` cl = list(nx.find_cliques(self.G)) ``` ``` rcl = nx.find_cliques_recursive(self.G) ``` ``` assert_equal(sorted(map(sorted, cl)), sorted(map(sorted, rcl))) ``` ``` assert_equal(cl, ``` ``` [[2, 6, 1, 3], [2, 6, 4], [5, 4, 7], [8, 9], [10, 11]]) ``` ``` def test_find_cliques2(self): ``` ``` hcl = list(nx.find_cliques(self.H)) ``` ``` assert_equal(sorted(map(sorted, hcl)), ``` ``` [[1, 2], [1, 4, 5, 6], [2, 3], [3, 4, 6]]) ``` ``` def test_clique_number(self): ``` ``` G = self.G ``` ``` assert_equal(nx.graph_clique_number(G), 4) ``` ``` assert_equal(nx.graph_clique_number(G, cliques=self.cl), 4) ``` ``` def test_clique_number2(self): ``` ``` G = nx.Graph() ``` ``` G.add_nodes_from([1, 2, 3]) ``` ``` assert_equal(nx.graph_clique_number(G), 1) ``` ``` def test_clique_number3(self): ``` ``` G = nx.Graph() ``` ``` assert_equal(nx.graph_clique_number(G), 0) ``` ``` def test_number_of_cliques(self): ``` ``` G = self.G ``` ``` assert_equal(nx.graph_number_of_cliques(G), 5) ``` ``` assert_equal(nx.graph_number_of_cliques(G, cliques=self.cl), 5) ``` ``` assert_equal(nx.number_of_cliques(G, 1), 1) ``` ``` assert_equal(list(nx.number_of_cliques(G, [1]).values()), [1]) ``` ``` assert_equal(list(nx.number_of_cliques(G, [1, 2]).values()), [1, 2]) ``` ``` assert_equal(nx.number_of_cliques(G, [1, 2]), {1: 1, 2: 2}) ``` ``` assert_equal(nx.number_of_cliques(G, 2), 2) ``` ``` assert_equal(nx.number_of_cliques(G), ``` ``` {1: 1, 2: 2, 3: 1, 4: 2, 5: 1, ``` ``` 6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1}) ``` ``` assert_equal(nx.number_of_cliques(G, nodes=list(G)), ``` ``` {1: 1, 2: 2, 3: 1, 4: 2, 5: 1, ``` ``` 6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1}) ``` ``` assert_equal(nx.number_of_cliques(G, nodes=[2, 3, 4]), ``` ``` {2: 2, 3: 1, 4: 2}) ``` ``` assert_equal(nx.number_of_cliques(G, cliques=self.cl), ``` ``` {1: 1, 2: 2, 3: 1, 4: 2, 5: 1, ``` ``` 6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1}) ``` ``` assert_equal(nx.number_of_cliques(G, list(G), cliques=self.cl), ``` ``` {1: 1, 2: 2, 3: 1, 4: 2, 5: 1, ``` ``` 6: 2, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1}) ``` ``` def test_node_clique_number(self): ``` ``` G = self.G ``` ``` assert_equal(nx.node_clique_number(G, 1), 4) ``` ``` assert_equal(list(nx.node_clique_number(G, [1]).values()), [4]) ``` ``` assert_equal(list(nx.node_clique_number(G, [1, 2]).values()), [4, 4]) ``` ``` assert_equal(nx.node_clique_number(G, [1, 2]), {1: 4, 2: 4}) ``` ``` assert_equal(nx.node_clique_number(G, 1), 4) ``` ``` assert_equal(nx.node_clique_number(G), ``` ``` {1: 4, 2: 4, 3: 4, 4: 3, 5: 3, 6: 4, ``` ``` 7: 3, 8: 2, 9: 2, 10: 2, 11: 2}) ``` ``` assert_equal(nx.node_clique_number(G, cliques=self.cl), ``` ``` {1: 4, 2: 4, 3: 4, 4: 3, 5: 3, 6: 4, ``` ``` 7: 3, 8: 2, 9: 2, 10: 2, 11: 2}) ``` ``` def test_cliques_containing_node(self): ``` ``` G = self.G ``` ``` assert_equal(nx.cliques_containing_node(G, 1), ``` ``` [[2, 6, 1, 3]]) ``` ``` assert_equal(list(nx.cliques_containing_node(G, [1]).values()), ``` ``` [[[2, 6, 1, 3]]]) ``` ``` assert_equal(list(nx.cliques_containing_node(G, [1, 2]).values()), ``` ``` [[[2, 6, 1, 3]], [[2, 6, 1, 3], [2, 6, 4]]]) ``` ``` assert_equal(nx.cliques_containing_node(G, [1, 2]), ``` ``` {1: [[2, 6, 1, 3]], 2: [[2, 6, 1, 3], [2, 6, 4]]}) ``` ``` assert_equal(nx.cliques_containing_node(G, 1), ``` ``` [[2, 6, 1, 3]]) ``` ``` assert_equal(nx.cliques_containing_node(G, 2), ``` ``` [[2, 6, 1, 3], [2, 6, 4]]) ``` ``` assert_equal(nx.cliques_containing_node(G, 2, cliques=self.cl), ``` ``` [[2, 6, 1, 3], [2, 6, 4]]) ``` ``` assert_equal(len(nx.cliques_containing_node(G)), 11) ``` ``` def test_make_clique_bipartite(self): ``` ``` G = self.G ``` ``` B = nx.make_clique_bipartite(G) ``` ``` assert_equal(sorted(B), ``` ``` [-5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]) ``` ``` # Project onto the nodes of the original graph. ``` ``` H = nx.project(B, range(1, 12)) ``` ``` assert_equal(H.adj, G.adj) ``` ``` # Project onto the nodes representing the cliques. ``` ``` H1 = nx.project(B, range(-5, 0)) ``` ``` # Relabel the negative numbers as positive ones. ``` ``` H1 = nx.relabel_nodes(H1, {-v: v for v in range(1, 6)}) ``` ``` assert_equal(sorted(H1), [1, 2, 3, 4, 5]) ``` ``` def test_make_max_clique_graph(self): ``` ``` """Tests that the maximal clique graph is the same as the bipartite ``` ``` clique graph after being projected onto the nodes representing the ``` ``` cliques. ``` ``` ``` ``` """ ``` ``` G = self.G ``` ``` B = nx.make_clique_bipartite(G) ``` ``` # Project onto the nodes representing the cliques. ``` ``` H1 = nx.project(B, range(-5, 0)) ``` ``` # Relabel the negative numbers as nonnegative ones, starting at ``` ``` # 0. ``` ``` H1 = nx.relabel_nodes(H1, {-v: v - 1 for v in range(1, 6)}) ``` ``` H2 = nx.make_max_clique_graph(G) ``` ``` assert_equal(H1.adj, H2.adj) ``` ``` @raises(nx.NetworkXNotImplemented) ``` ``` def test_directed(self): ``` ``` cliques = nx.find_cliques(nx.DiGraph()) ``` ```class TestEnumerateAllCliques: ``` ``` def test_paper_figure_4(self): ``` ``` # Same graph as given in Fig. 4 of paper enumerate_all_cliques is ``` ``` # based on. ``` ``` # http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1559964&isnumber=33129 ``` ``` G = nx.Graph() ``` ``` edges_fig_4 = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'), ``` ``` ('b', 'c'), ('b', 'd'), ('b', 'e'), ``` ``` ('c', 'd'), ('c', 'e'), ``` ``` ('d', 'e'), ``` ``` ('f', 'b'), ('f', 'c'), ('f', 'g'), ``` ``` ('g', 'f'), ('g', 'c'), ('g', 'd'), ('g', 'e')] ``` ``` G.add_edges_from(edges_fig_4) ``` ``` cliques = list(nx.enumerate_all_cliques(G)) ``` ``` clique_sizes = list(map(len, cliques)) ``` ``` assert_equal(sorted(clique_sizes), clique_sizes) ``` ``` expected_cliques = [['a'], ``` ``` ['b'], ``` ``` ['c'], ``` ``` ['d'], ``` ``` ['e'], ``` ``` ['f'], ``` ``` ['g'], ``` ``` ['a', 'b'], ``` ``` ['a', 'b', 'd'], ``` ``` ['a', 'b', 'd', 'e'], ``` ``` ['a', 'b', 'e'], ``` ``` ['a', 'c'], ``` ``` ['a', 'c', 'd'], ``` ``` ['a', 'c', 'd', 'e'], ``` ``` ['a', 'c', 'e'], ``` ``` ['a', 'd'], ``` ``` ['a', 'd', 'e'], ``` ``` ['a', 'e'], ``` ``` ['b', 'c'], ``` ``` ['b', 'c', 'd'], ``` ``` ['b', 'c', 'd', 'e'], ``` ``` ['b', 'c', 'e'], ``` ``` ['b', 'c', 'f'], ``` ``` ['b', 'd'], ``` ``` ['b', 'd', 'e'], ``` ``` ['b', 'e'], ``` ``` ['b', 'f'], ``` ``` ['c', 'd'], ``` ``` ['c', 'd', 'e'], ``` ``` ['c', 'd', 'e', 'g'], ``` ``` ['c', 'd', 'g'], ``` ``` ['c', 'e'], ``` ``` ['c', 'e', 'g'], ``` ``` ['c', 'f'], ``` ``` ['c', 'f', 'g'], ``` ``` ['c', 'g'], ``` ``` ['d', 'e'], ``` ``` ['d', 'e', 'g'], ``` ``` ['d', 'g'], ``` ``` ['e', 'g'], ``` ``` ['f', 'g'], ``` ``` ['a', 'b', 'c'], ``` ``` ['a', 'b', 'c', 'd'], ``` ``` ['a', 'b', 'c', 'd', 'e'], ``` ``` ['a', 'b', 'c', 'e']] ``` ``` assert_equal(sorted(map(sorted, cliques)), ``` ``` sorted(map(sorted, expected_cliques))) ```