## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/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 """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 |