Coverage for /opt/conda/lib/python3.14/site-packages/medil/_ecc_algorithms.py: 86%

1"""Implementations of edge clique cover finding algorithms.""" 

2 

3from collections import deque 

4 

5import numpy as np 

6 

7from ._graph import UndirectedDependenceGraph 

8 

9 

10def _find_clique_min_cover(graph, verbose=False): 

11 """Returns the clique-minimum edge clique cover. 

12 

13 Parameters 

14 ---------- 

15 graph : np.array 

16 Adjacency matrix for undirected graph. 

17 

18 verbose : bool, optional 

19 Wether or not to print verbose output. 

20 

21 Returns 

22 ------- 

23 the_cover: np.array 

24 Biadjacency matrix representing edge clique cover. 

25 

26 See Also 

27 -------- 

28 _graph.UndirectedDependenceGraph : Defines auxilliary data structure 

29 and reduction rules used by this 

30 algorithm. 

31 

32 Notes 

33 ----- 

34 This is an implementation of the algorithm described in 

35 :cite:`Gramm_2009`. 

36 

37 """ 

38 graph = UndirectedDependenceGraph(graph, verbose) 

39 try: 

40 graph.make_aux() 

41 except ValueError: 

42 print("The input graph doesn't appear to have any edges!") 

43 return graph.adj_matrix 

44 

45 num_cliques = 1 

46 the_cover = None 

47 if verbose: 

48 # find bound for cliques in solution 

49 max_intersect_num = graph.num_vertices**2 // 4 

50 if max_intersect_num < graph.num_edges: 

51 p = graph.n_choose_2(graph.num_vertices) - graph.num_edges 

52 t = int(np.sqrt(p)) 

53 max_intersect_num = p + t if p > 0 else 1 

54 print("solution has at most {} cliques.".format(max_intersect_num)) 

55 while the_cover is None: 

56 if verbose: 

57 print( 

58 "\ntesting for solutions with {}/{} cliques".format( 

59 num_cliques, max_intersect_num 

60 ) 

61 ) 

62 the_cover = _branch(graph, num_cliques, the_cover, iteration=0, iteration_max=3) 

63 num_cliques += 1 

64 

65 return _add_isolated_verts(the_cover) 

66 

67 

68def _branch(graph, k_num_cliques, the_cover, iteration, iteration_max): 

69 """Helper function for `find_clique_min_cover()`. 

70 

71 Describing the solution search space as a tree. 

72 This function tests whether the given node is a solution, and it branches if not. 

73 

74 Parameters 

75 ---------- 

76 graph : UndirectedDependenceGraph() 

77 Class for representing undirected graph and auxilliary data used in edge clique cover algorithm. 

78 

79 k_num_cliques : int 

80 Current depth of search; number of cliques in cover being testet for solution. 

81 

82 the_cover : np.array 

83 Biadjacency matrix representing (possibly partial) edge clique cover. 

84 

85 iteration: current iteration 

86 

87 iteration_max: maximum number of iteration_max 

88 

89 Returns 

90 ------- 

91 2d numpy array or None 

92 Biadjacency matrix representing (complete) edge clique cover or None if cover is only partial. 

93 

94 """ 

95 

96 iteration = iteration + 1 

97 branch_graph = graph.reducible_copy() 

98 branch_graph.the_cover = the_cover 

99 branch_graph.cover_edges() 

100 

101 if branch_graph.num_edges == 0: 

102 return branch_graph.reconstruct_cover(the_cover) 

103 

104 branch_graph.reduzieren(k_num_cliques) 

105 k_num_cliques = branch_graph.k_num_cliques 

106 

107 if k_num_cliques < 0: 

108 return None 

109 

110 if branch_graph.num_edges == 0: # equiv to len(branch_graph.extant_edges_idx)==0 

111 return ( 

112 branch_graph.the_cover 

113 ) # not in paper, but speeds it up slightly; or rather return None? 

114 

115 chosen_nbrhood = branch_graph.choose_nbrhood() 

116 # print("num cliques: {}".format(len([x for x in _max_cliques(chosen_nbrhood)]))) 

117 for clique_nodes in _max_cliques(chosen_nbrhood): 

118 if len(clique_nodes) == 1: # then this vert has been rmed; quirk of max_cliques 

119 continue 

120 clique = np.zeros(branch_graph.unreduced.num_vertices, dtype=int) 

121 clique[clique_nodes] = 1 

122 union = ( 

123 clique.reshape(1, -1) 

124 if branch_graph.the_cover is None 

125 else np.vstack((branch_graph.the_cover, clique)) 

126 ) 

127 

128 # print(iteration) 

129 if iteration > iteration_max: 

130 return branch_graph.the_cover 

131 

132 the_cover_prime = _branch( 

133 branch_graph, 

134 k_num_cliques - 1, 

135 union, 

136 iteration, 

137 iteration_max=iteration_max, 

138 ) 

139 if the_cover_prime is not None: 

140 return the_cover_prime 

141 return None 

142 

143 

144def _max_cliques(nbrhood): 

145 """Adaptation of NetworkX code for finding all maximal cliques. 

146 

147 Parameters 

148 ---------- 

149 nbrhood : np.array 

150 Adjacency matrix for undirected (sub)graph. 

151 

152 Returns 

153 ------- 

154 generator 

155 set of all maximal cliques 

156 

157 Notes 

158 ----- 

159 Pieced together from nx.from_numpy_array and nx.find_cliques, which 

160 is output sensitive. 

161 

162 """ 

163 

164 if len(nbrhood) == 0: 

165 return 

166 

167 # convert adjacency matrix to nx style graph 

168 adj = { 

169 u: {v for v in np.nonzero(nbrhood[u])[0] if v != u} for u in range(len(nbrhood)) 

170 } 

171 Q = [None] 

172 

173 subg = set(range(len(nbrhood))) 

174 cand = set(range(len(nbrhood))) 

175 u = max(subg, key=lambda u: len(cand & adj[u])) 

176 ext_u = cand - adj[u] 

177 stack = [] 

178 

179 try: 

180 while True: 

181 if ext_u: 

182 q = ext_u.pop() 

183 cand.remove(q) 

184 Q[-1] = q 

185 adj_q = adj[q] 

186 subg_q = subg & adj_q 

187 if not subg_q: 

188 yield Q[:] 

189 else: 

190 cand_q = cand & adj_q 

191 if cand_q: 

192 stack.append((subg, cand, ext_u)) 

193 Q.append(None) 

194 subg = subg_q 

195 cand = cand_q 

196 u = max(subg, key=lambda u: len(cand & adj[u])) 

197 ext_u = cand - adj[u] 

198 else: 

199 Q.pop() 

200 subg, cand, ext_u = stack.pop() 

201 except IndexError: 

202 pass 

203 # note: max_cliques is a generator, so it's consumed after being 

204 # looped through once 

205 

206 

207def _add_isolated_verts(cover): 

208 cover = cover.astype(bool) 

209 iso_vert_idx = np.flatnonzero(cover.sum(0) == 0) 

210 num_rows = len(iso_vert_idx) 

211 num_cols = cover.shape[1] 

212 iso_vert_cover = np.zeros((num_rows, num_cols), bool) 

213 iso_vert_cover[np.arange(num_rows), iso_vert_idx] = True 

214 return np.vstack((cover, iso_vert_cover)) 

215 

216 

217def _find_heuristic_1pc(graph): 

218 num_meas = len(graph) 

219 

220 # nx_graph = nx.from_numpy_array(graph) 

221 # indep_set = 

222 # list(nx.approximation.maximum_independent_set(nx_graph)) 

223 

224 indep_sets = _max_cliques(np.logical_not(graph)) 

225 max_indep_set = next(indep_sets) 

226 for indep_set in indep_sets: 

227 if len(indep_set) > len(max_indep_set): 

228 max_indep_set = indep_set 

229 

230 num_latents = len(max_indep_set) 

231 

232 the_cover = np.zeros((num_latents, num_meas), bool) 

233 the_cover[np.arange(num_latents), max_indep_set] = True 

234 

235 for idx, node in enumerate(max_indep_set): 

236 nbrs = np.flatnonzero(graph[node]) 

237 the_cover[idx, nbrs] = True 

238 

239 uncovered_edges = deque( 

240 { 

241 tuple(edge) 

242 for edge in np.argwhere(np.triu(graph, 1)) 

243 if not np.logical_and(the_cover[:, edge[0]], the_cover[:, edge[1]]).any() 

244 } 

245 ) 

246 

247 while bool(uncovered_edges): 

248 u, v = uncovered_edges.popleft() 

249 if the_cover[:, u].any(): 

250 the_cover[np.argmax(the_cover[:, u]), v] = True 

251 elif the_cover[:, v].any(): 

252 the_cover[np.argmax(the_cover[:, v]), u] = True 

253 else: 

254 uncovered_edges.append((u, v)) 

255 

256 recon = the_cover.T @ the_cover 

257 if np.logical_not(graph <= recon).any(): 

258 raise Exception(f"Problem with `find_heuristic_1pc()` for input {graph}") 

259 

260 return the_cover