Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/clique.py: 38%
52 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Functions for computing large cliques and maximum independent sets."""
2import networkx as nx
3from networkx.algorithms.approximation import ramsey
4from networkx.utils import not_implemented_for
6__all__ = [
7 "clique_removal",
8 "max_clique",
9 "large_clique_size",
10 "maximum_independent_set",
11]
14@not_implemented_for("directed")
15@not_implemented_for("multigraph")
16@nx._dispatch
17def maximum_independent_set(G):
18 """Returns an approximate maximum independent set.
20 Independent set or stable set is a set of vertices in a graph, no two of
21 which are adjacent. That is, it is a set I of vertices such that for every
22 two vertices in I, there is no edge connecting the two. Equivalently, each
23 edge in the graph has at most one endpoint in I. The size of an independent
24 set is the number of vertices it contains [1]_.
26 A maximum independent set is a largest independent set for a given graph G
27 and its size is denoted $\\alpha(G)$. The problem of finding such a set is called
28 the maximum independent set problem and is an NP-hard optimization problem.
29 As such, it is unlikely that there exists an efficient algorithm for finding
30 a maximum independent set of a graph.
32 The Independent Set algorithm is based on [2]_.
34 Parameters
35 ----------
36 G : NetworkX graph
37 Undirected graph
39 Returns
40 -------
41 iset : Set
42 The apx-maximum independent set
44 Examples
45 --------
46 >>> G = nx.path_graph(10)
47 >>> nx.approximation.maximum_independent_set(G)
48 {0, 2, 4, 6, 9}
50 Raises
51 ------
52 NetworkXNotImplemented
53 If the graph is directed or is a multigraph.
55 Notes
56 -----
57 Finds the $O(|V|/(log|V|)^2)$ apx of independent set in the worst case.
59 References
60 ----------
61 .. [1] `Wikipedia: Independent set
62 <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_
63 .. [2] Boppana, R., & Halldórsson, M. M. (1992).
64 Approximating maximum independent sets by excluding subgraphs.
65 BIT Numerical Mathematics, 32(2), 180–196. Springer.
66 """
67 iset, _ = clique_removal(G)
68 return iset
71@not_implemented_for("directed")
72@not_implemented_for("multigraph")
73@nx._dispatch
74def max_clique(G):
75 r"""Find the Maximum Clique
77 Finds the $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set
78 in the worst case.
80 Parameters
81 ----------
82 G : NetworkX graph
83 Undirected graph
85 Returns
86 -------
87 clique : set
88 The apx-maximum clique of the graph
90 Examples
91 --------
92 >>> G = nx.path_graph(10)
93 >>> nx.approximation.max_clique(G)
94 {8, 9}
96 Raises
97 ------
98 NetworkXNotImplemented
99 If the graph is directed or is a multigraph.
101 Notes
102 -----
103 A clique in an undirected graph G = (V, E) is a subset of the vertex set
104 `C \subseteq V` such that for every two vertices in C there exists an edge
105 connecting the two. This is equivalent to saying that the subgraph
106 induced by C is complete (in some cases, the term clique may also refer
107 to the subgraph).
109 A maximum clique is a clique of the largest possible size in a given graph.
110 The clique number `\omega(G)` of a graph G is the number of
111 vertices in a maximum clique in G. The intersection number of
112 G is the smallest number of cliques that together cover all edges of G.
114 https://en.wikipedia.org/wiki/Maximum_clique
116 References
117 ----------
118 .. [1] Boppana, R., & Halldórsson, M. M. (1992).
119 Approximating maximum independent sets by excluding subgraphs.
120 BIT Numerical Mathematics, 32(2), 180–196. Springer.
121 doi:10.1007/BF01994876
122 """
123 # finding the maximum clique in a graph is equivalent to finding
124 # the independent set in the complementary graph
125 cgraph = nx.complement(G)
126 iset, _ = clique_removal(cgraph)
127 return iset
130@not_implemented_for("directed")
131@not_implemented_for("multigraph")
132@nx._dispatch
133def clique_removal(G):
134 r"""Repeatedly remove cliques from the graph.
136 Results in a $O(|V|/(\log |V|)^2)$ approximation of maximum clique
137 and independent set. Returns the largest independent set found, along
138 with found maximal cliques.
140 Parameters
141 ----------
142 G : NetworkX graph
143 Undirected graph
145 Returns
146 -------
147 max_ind_cliques : (set, list) tuple
148 2-tuple of Maximal Independent Set and list of maximal cliques (sets).
150 Examples
151 --------
152 >>> G = nx.path_graph(10)
153 >>> nx.approximation.clique_removal(G)
154 ({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])
156 Raises
157 ------
158 NetworkXNotImplemented
159 If the graph is directed or is a multigraph.
161 References
162 ----------
163 .. [1] Boppana, R., & Halldórsson, M. M. (1992).
164 Approximating maximum independent sets by excluding subgraphs.
165 BIT Numerical Mathematics, 32(2), 180–196. Springer.
166 """
167 graph = G.copy()
168 c_i, i_i = ramsey.ramsey_R2(graph)
169 cliques = [c_i]
170 isets = [i_i]
171 while graph:
172 graph.remove_nodes_from(c_i)
173 c_i, i_i = ramsey.ramsey_R2(graph)
174 if c_i:
175 cliques.append(c_i)
176 if i_i:
177 isets.append(i_i)
178 # Determine the largest independent set as measured by cardinality.
179 maxiset = max(isets, key=len)
180 return maxiset, cliques
183@not_implemented_for("directed")
184@not_implemented_for("multigraph")
185@nx._dispatch
186def large_clique_size(G):
187 """Find the size of a large clique in a graph.
189 A *clique* is a subset of nodes in which each pair of nodes is
190 adjacent. This function is a heuristic for finding the size of a
191 large clique in the graph.
193 Parameters
194 ----------
195 G : NetworkX graph
197 Returns
198 -------
199 k: integer
200 The size of a large clique in the graph.
202 Examples
203 --------
204 >>> G = nx.path_graph(10)
205 >>> nx.approximation.large_clique_size(G)
206 2
208 Raises
209 ------
210 NetworkXNotImplemented
211 If the graph is directed or is a multigraph.
213 Notes
214 -----
215 This implementation is from [1]_. Its worst case time complexity is
216 :math:`O(n d^2)`, where *n* is the number of nodes in the graph and
217 *d* is the maximum degree.
219 This function is a heuristic, which means it may work well in
220 practice, but there is no rigorous mathematical guarantee on the
221 ratio between the returned number and the actual largest clique size
222 in the graph.
224 References
225 ----------
226 .. [1] Pattabiraman, Bharath, et al.
227 "Fast Algorithms for the Maximum Clique Problem on Massive Graphs
228 with Applications to Overlapping Community Detection."
229 *Internet Mathematics* 11.4-5 (2015): 421--448.
230 <https://doi.org/10.1080/15427951.2014.986778>
232 See also
233 --------
235 :func:`networkx.algorithms.approximation.clique.max_clique`
236 A function that returns an approximate maximum clique with a
237 guarantee on the approximation ratio.
239 :mod:`networkx.algorithms.clique`
240 Functions for finding the exact maximum clique in a graph.
242 """
243 degrees = G.degree
245 def _clique_heuristic(G, U, size, best_size):
246 if not U:
247 return max(best_size, size)
248 u = max(U, key=degrees)
249 U.remove(u)
250 N_prime = {v for v in G[u] if degrees[v] >= best_size}
251 return _clique_heuristic(G, U & N_prime, size + 1, best_size)
253 best_size = 0
254 nodes = (u for u in G if degrees[u] >= best_size)
255 for u in nodes:
256 neighbors = {v for v in G[u] if degrees[v] >= best_size}
257 best_size = _clique_heuristic(G, neighbors, 1, best_size)
258 return best_size