Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/tests/test_clique.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Unit tests for the :mod:`networkx.algorithms.approximation.clique` | |
2 module. | |
3 | |
4 """ | |
5 | |
6 | |
7 import networkx as nx | |
8 from networkx.algorithms.approximation import max_clique | |
9 from networkx.algorithms.approximation import clique_removal | |
10 from networkx.algorithms.approximation import large_clique_size | |
11 | |
12 | |
13 def is_independent_set(G, nodes): | |
14 """Returns True if and only if `nodes` is a clique in `G`. | |
15 | |
16 `G` is a NetworkX graph. `nodes` is an iterable of nodes in | |
17 `G`. | |
18 | |
19 """ | |
20 return G.subgraph(nodes).number_of_edges() == 0 | |
21 | |
22 | |
23 def is_clique(G, nodes): | |
24 """Returns True if and only if `nodes` is an independent set | |
25 in `G`. | |
26 | |
27 `G` is an undirected simple graph. `nodes` is an iterable of | |
28 nodes in `G`. | |
29 | |
30 """ | |
31 H = G.subgraph(nodes) | |
32 n = len(H) | |
33 return H.number_of_edges() == n * (n - 1) // 2 | |
34 | |
35 | |
36 class TestCliqueRemoval: | |
37 """Unit tests for the | |
38 :func:`~networkx.algorithms.approximation.clique_removal` function. | |
39 | |
40 """ | |
41 | |
42 def test_trivial_graph(self): | |
43 G = nx.trivial_graph() | |
44 independent_set, cliques = clique_removal(G) | |
45 assert is_independent_set(G, independent_set) | |
46 assert all(is_clique(G, clique) for clique in cliques) | |
47 # In fact, we should only have 1-cliques, that is, singleton nodes. | |
48 assert all(len(clique) == 1 for clique in cliques) | |
49 | |
50 def test_complete_graph(self): | |
51 G = nx.complete_graph(10) | |
52 independent_set, cliques = clique_removal(G) | |
53 assert is_independent_set(G, independent_set) | |
54 assert all(is_clique(G, clique) for clique in cliques) | |
55 | |
56 def test_barbell_graph(self): | |
57 G = nx.barbell_graph(10, 5) | |
58 independent_set, cliques = clique_removal(G) | |
59 assert is_independent_set(G, independent_set) | |
60 assert all(is_clique(G, clique) for clique in cliques) | |
61 | |
62 | |
63 class TestMaxClique: | |
64 """Unit tests for the :func:`networkx.algorithms.approximation.max_clique` | |
65 function. | |
66 | |
67 """ | |
68 | |
69 def test_null_graph(self): | |
70 G = nx.null_graph() | |
71 assert len(max_clique(G)) == 0 | |
72 | |
73 def test_complete_graph(self): | |
74 graph = nx.complete_graph(30) | |
75 # this should return the entire graph | |
76 mc = max_clique(graph) | |
77 assert 30 == len(mc) | |
78 | |
79 def test_maximal_by_cardinality(self): | |
80 """Tests that the maximal clique is computed according to maximum | |
81 cardinality of the sets. | |
82 | |
83 For more information, see pull request #1531. | |
84 | |
85 """ | |
86 G = nx.complete_graph(5) | |
87 G.add_edge(4, 5) | |
88 clique = max_clique(G) | |
89 assert len(clique) > 1 | |
90 | |
91 G = nx.lollipop_graph(30, 2) | |
92 clique = max_clique(G) | |
93 assert len(clique) > 2 | |
94 | |
95 | |
96 def test_large_clique_size(): | |
97 G = nx.complete_graph(9) | |
98 nx.add_cycle(G, [9, 10, 11]) | |
99 G.add_edge(8, 9) | |
100 G.add_edge(1, 12) | |
101 G.add_node(13) | |
102 | |
103 assert large_clique_size(G) == 9 | |
104 G.remove_node(5) | |
105 assert large_clique_size(G) == 8 | |
106 G.remove_edge(2, 3) | |
107 assert large_clique_size(G) == 7 |