Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/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 """Functions for computing large cliques.""" | |
2 import networkx as nx | |
3 from networkx.utils import not_implemented_for | |
4 from networkx.algorithms.approximation import ramsey | |
5 | |
6 __all__ = ["clique_removal", "max_clique", "large_clique_size"] | |
7 | |
8 | |
9 def max_clique(G): | |
10 r"""Find the Maximum Clique | |
11 | |
12 Finds the $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set | |
13 in the worst case. | |
14 | |
15 Parameters | |
16 ---------- | |
17 G : NetworkX graph | |
18 Undirected graph | |
19 | |
20 Returns | |
21 ------- | |
22 clique : set | |
23 The apx-maximum clique of the graph | |
24 | |
25 Notes | |
26 ------ | |
27 A clique in an undirected graph G = (V, E) is a subset of the vertex set | |
28 `C \subseteq V` such that for every two vertices in C there exists an edge | |
29 connecting the two. This is equivalent to saying that the subgraph | |
30 induced by C is complete (in some cases, the term clique may also refer | |
31 to the subgraph). | |
32 | |
33 A maximum clique is a clique of the largest possible size in a given graph. | |
34 The clique number `\omega(G)` of a graph G is the number of | |
35 vertices in a maximum clique in G. The intersection number of | |
36 G is the smallest number of cliques that together cover all edges of G. | |
37 | |
38 https://en.wikipedia.org/wiki/Maximum_clique | |
39 | |
40 References | |
41 ---------- | |
42 .. [1] Boppana, R., & Halldórsson, M. M. (1992). | |
43 Approximating maximum independent sets by excluding subgraphs. | |
44 BIT Numerical Mathematics, 32(2), 180–196. Springer. | |
45 doi:10.1007/BF01994876 | |
46 """ | |
47 if G is None: | |
48 raise ValueError("Expected NetworkX graph!") | |
49 | |
50 # finding the maximum clique in a graph is equivalent to finding | |
51 # the independent set in the complementary graph | |
52 cgraph = nx.complement(G) | |
53 iset, _ = clique_removal(cgraph) | |
54 return iset | |
55 | |
56 | |
57 def clique_removal(G): | |
58 r""" Repeatedly remove cliques from the graph. | |
59 | |
60 Results in a $O(|V|/(\log |V|)^2)$ approximation of maximum clique | |
61 and independent set. Returns the largest independent set found, along | |
62 with found maximal cliques. | |
63 | |
64 Parameters | |
65 ---------- | |
66 G : NetworkX graph | |
67 Undirected graph | |
68 | |
69 Returns | |
70 ------- | |
71 max_ind_cliques : (set, list) tuple | |
72 2-tuple of Maximal Independent Set and list of maximal cliques (sets). | |
73 | |
74 References | |
75 ---------- | |
76 .. [1] Boppana, R., & Halldórsson, M. M. (1992). | |
77 Approximating maximum independent sets by excluding subgraphs. | |
78 BIT Numerical Mathematics, 32(2), 180–196. Springer. | |
79 """ | |
80 graph = G.copy() | |
81 c_i, i_i = ramsey.ramsey_R2(graph) | |
82 cliques = [c_i] | |
83 isets = [i_i] | |
84 while graph: | |
85 graph.remove_nodes_from(c_i) | |
86 c_i, i_i = ramsey.ramsey_R2(graph) | |
87 if c_i: | |
88 cliques.append(c_i) | |
89 if i_i: | |
90 isets.append(i_i) | |
91 # Determine the largest independent set as measured by cardinality. | |
92 maxiset = max(isets, key=len) | |
93 return maxiset, cliques | |
94 | |
95 | |
96 @not_implemented_for("directed") | |
97 @not_implemented_for("multigraph") | |
98 def large_clique_size(G): | |
99 """Find the size of a large clique in a graph. | |
100 | |
101 A *clique* is a subset of nodes in which each pair of nodes is | |
102 adjacent. This function is a heuristic for finding the size of a | |
103 large clique in the graph. | |
104 | |
105 Parameters | |
106 ---------- | |
107 G : NetworkX graph | |
108 | |
109 Returns | |
110 ------- | |
111 int | |
112 The size of a large clique in the graph. | |
113 | |
114 Notes | |
115 ----- | |
116 This implementation is from [1]_. Its worst case time complexity is | |
117 :math:`O(n d^2)`, where *n* is the number of nodes in the graph and | |
118 *d* is the maximum degree. | |
119 | |
120 This function is a heuristic, which means it may work well in | |
121 practice, but there is no rigorous mathematical guarantee on the | |
122 ratio between the returned number and the actual largest clique size | |
123 in the graph. | |
124 | |
125 References | |
126 ---------- | |
127 .. [1] Pattabiraman, Bharath, et al. | |
128 "Fast Algorithms for the Maximum Clique Problem on Massive Graphs | |
129 with Applications to Overlapping Community Detection." | |
130 *Internet Mathematics* 11.4-5 (2015): 421--448. | |
131 <https://doi.org/10.1080/15427951.2014.986778> | |
132 | |
133 See also | |
134 -------- | |
135 | |
136 :func:`networkx.algorithms.approximation.clique.max_clique` | |
137 A function that returns an approximate maximum clique with a | |
138 guarantee on the approximation ratio. | |
139 | |
140 :mod:`networkx.algorithms.clique` | |
141 Functions for finding the exact maximum clique in a graph. | |
142 | |
143 """ | |
144 degrees = G.degree | |
145 | |
146 def _clique_heuristic(G, U, size, best_size): | |
147 if not U: | |
148 return max(best_size, size) | |
149 u = max(U, key=degrees) | |
150 U.remove(u) | |
151 N_prime = {v for v in G[u] if degrees[v] >= best_size} | |
152 return _clique_heuristic(G, U & N_prime, size + 1, best_size) | |
153 | |
154 best_size = 0 | |
155 nodes = (u for u in G if degrees[u] >= best_size) | |
156 for u in nodes: | |
157 neighbors = {v for v in G[u] if degrees[v] >= best_size} | |
158 best_size = _clique_heuristic(G, neighbors, 1, best_size) | |
159 return best_size |