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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"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