### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/clique.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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
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