Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for computing large cliques and maximum independent sets."""
3import networkx as nx
4from networkx.algorithms.approximation import ramsey
5from networkx.utils import not_implemented_for
7__all__ = [
8 "clique_removal",
9 "max_clique",
10 "large_clique_size",
11 "maximum_independent_set",
12]
15@not_implemented_for("directed")
16@not_implemented_for("multigraph")
17@nx._dispatchable
18def maximum_independent_set(G):
19 """Returns an approximate maximum independent set.
21 Independent set or stable set is a set of vertices in a graph, no two of
22 which are adjacent. That is, it is a set I of vertices such that for every
23 two vertices in I, there is no edge connecting the two. Equivalently, each
24 edge in the graph has at most one endpoint in I. The size of an independent
25 set is the number of vertices it contains [1]_.
27 A maximum independent set is a largest independent set for a given graph G
28 and its size is denoted $\\alpha(G)$. The problem of finding such a set is called
29 the maximum independent set problem and is an NP-hard optimization problem.
30 As such, it is unlikely that there exists an efficient algorithm for finding
31 a maximum independent set of a graph.
33 The Independent Set algorithm is based on [2]_.
35 Parameters
36 ----------
37 G : NetworkX graph
38 Undirected graph
40 Returns
41 -------
42 iset : Set
43 The apx-maximum independent set
45 Examples
46 --------
47 >>> G = nx.path_graph(10)
48 >>> nx.approximation.maximum_independent_set(G)
49 {0, 2, 4, 6, 9}
51 Raises
52 ------
53 NetworkXNotImplemented
54 If the graph is directed or is a multigraph.
56 Notes
57 -----
58 Finds the $O(|V|/(log|V|)^2)$ apx of independent set in the worst case.
60 References
61 ----------
62 .. [1] `Wikipedia: Independent set
63 <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_
64 .. [2] Boppana, R., & Halldórsson, M. M. (1992).
65 Approximating maximum independent sets by excluding subgraphs.
66 BIT Numerical Mathematics, 32(2), 180–196. Springer.
67 """
68 iset, _ = clique_removal(G)
69 return iset
72@not_implemented_for("directed")
73@not_implemented_for("multigraph")
74@nx._dispatchable
75def max_clique(G):
76 r"""Find the Maximum Clique
78 Finds the $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set
79 in the worst case.
81 Parameters
82 ----------
83 G : NetworkX graph
84 Undirected graph
86 Returns
87 -------
88 clique : set
89 The apx-maximum clique of the graph
91 Examples
92 --------
93 >>> G = nx.path_graph(10)
94 >>> nx.approximation.max_clique(G)
95 {8, 9}
97 Raises
98 ------
99 NetworkXNotImplemented
100 If the graph is directed or is a multigraph.
102 Notes
103 -----
104 A clique in an undirected graph G = (V, E) is a subset of the vertex set
105 `C \subseteq V` such that for every two vertices in C there exists an edge
106 connecting the two. This is equivalent to saying that the subgraph
107 induced by C is complete (in some cases, the term clique may also refer
108 to the subgraph).
110 A maximum clique is a clique of the largest possible size in a given graph.
111 The clique number `\omega(G)` of a graph G is the number of
112 vertices in a maximum clique in G. The intersection number of
113 G is the smallest number of cliques that together cover all edges of G.
115 https://en.wikipedia.org/wiki/Maximum_clique
117 References
118 ----------
119 .. [1] Boppana, R., & Halldórsson, M. M. (1992).
120 Approximating maximum independent sets by excluding subgraphs.
121 BIT Numerical Mathematics, 32(2), 180–196. Springer.
122 doi:10.1007/BF01994876
123 """
124 # finding the maximum clique in a graph is equivalent to finding
125 # the independent set in the complementary graph
126 cgraph = nx.complement(G)
127 iset, _ = clique_removal(cgraph)
128 return iset
131@not_implemented_for("directed")
132@not_implemented_for("multigraph")
133@nx._dispatchable
134def clique_removal(G):
135 r"""Repeatedly remove cliques from the graph.
137 Results in a $O(|V|/(\log |V|)^2)$ approximation of maximum clique
138 and independent set. Returns the largest independent set found, along
139 with found maximal cliques.
141 Parameters
142 ----------
143 G : NetworkX graph
144 Undirected graph
146 Returns
147 -------
148 max_ind_cliques : (set, list) tuple
149 2-tuple of Maximal Independent Set and list of maximal cliques (sets).
151 Examples
152 --------
153 >>> G = nx.path_graph(10)
154 >>> nx.approximation.clique_removal(G)
155 ({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])
157 Raises
158 ------
159 NetworkXNotImplemented
160 If the graph is directed or is a multigraph.
162 References
163 ----------
164 .. [1] Boppana, R., & Halldórsson, M. M. (1992).
165 Approximating maximum independent sets by excluding subgraphs.
166 BIT Numerical Mathematics, 32(2), 180–196. Springer.
167 """
168 graph = G.copy()
169 c_i, i_i = ramsey.ramsey_R2(graph)
170 cliques = [c_i]
171 isets = [i_i]
172 while graph:
173 graph.remove_nodes_from(c_i)
174 c_i, i_i = ramsey.ramsey_R2(graph)
175 if c_i:
176 cliques.append(c_i)
177 if i_i:
178 isets.append(i_i)
179 # Determine the largest independent set as measured by cardinality.
180 maxiset = max(isets, key=len)
181 return maxiset, cliques
184@not_implemented_for("directed")
185@not_implemented_for("multigraph")
186@nx._dispatchable
187def large_clique_size(G):
188 """Find the size of a large clique in a graph.
190 A *clique* is a subset of nodes in which each pair of nodes is
191 adjacent. This function is a heuristic for finding the size of a
192 large clique in the graph.
194 Parameters
195 ----------
196 G : NetworkX graph
198 Returns
199 -------
200 k: integer
201 The size of a large clique in the graph.
203 Examples
204 --------
205 >>> G = nx.path_graph(10)
206 >>> nx.approximation.large_clique_size(G)
207 2
209 Raises
210 ------
211 NetworkXNotImplemented
212 If the graph is directed or is a multigraph.
214 Notes
215 -----
216 This implementation is from [1]_. Its worst case time complexity is
217 :math:`O(n d^2)`, where *n* is the number of nodes in the graph and
218 *d* is the maximum degree.
220 This function is a heuristic, which means it may work well in
221 practice, but there is no rigorous mathematical guarantee on the
222 ratio between the returned number and the actual largest clique size
223 in the graph.
225 References
226 ----------
227 .. [1] Pattabiraman, Bharath, et al.
228 "Fast Algorithms for the Maximum Clique Problem on Massive Graphs
229 with Applications to Overlapping Community Detection."
230 *Internet Mathematics* 11.4-5 (2015): 421--448.
231 <https://doi.org/10.1080/15427951.2014.986778>
233 See also
234 --------
236 :func:`networkx.algorithms.approximation.clique.max_clique`
237 A function that returns an approximate maximum clique with a
238 guarantee on the approximation ratio.
240 :mod:`networkx.algorithms.clique`
241 Functions for finding the exact maximum clique in a graph.
243 """
244 degrees = G.degree
246 def _clique_heuristic(G, U, size, best_size):
247 if not U:
248 return max(best_size, size)
249 u = max(U, key=degrees)
250 U.remove(u)
251 N_prime = {v for v in G[u] if degrees[v] >= best_size}
252 return _clique_heuristic(G, U & N_prime, size + 1, best_size)
254 best_size = 0
255 nodes = (u for u in G if degrees[u] >= best_size)
256 for u in nodes:
257 neighbors = {v for v in G[u] if degrees[v] >= best_size}
258 best_size = _clique_heuristic(G, neighbors, 1, best_size)
259 return best_size