Coverage for /opt/conda/lib/python3.12/site-packages/medil/ecc_algorithms.py: 92%
116 statements
« prev ^ index » next coverage.py v7.8.0, created at 2025-04-25 05:42 +0000
1"""Implementations of edge clique clover finding algorithms."""
3from collections import deque
5import numpy as np
7from .graph import UndirectedDependenceGraph
10def find_clique_min_cover(graph, verbose=False):
11 """Returns the clique-minimum edge clique cover.
13 Parameters
14 ----------
15 graph : np.array
16 Adjacency matrix for undirected graph.
18 verbose : bool, optional
19 Wether or not to print verbose output.
21 Returns
22 -------
23 the_cover: np.array
24 Biadjacency matrix representing edge clique cover.
26 See Also
27 --------
28 graph.UndirectedDependenceGraph : Defines auxilliary data structure
29 and reduction rules used by this
30 algorithm.
32 Notes
33 -----
34 This is an implementation of the algorithm described in
35 :cite:`Gramm_2009`.
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
45 num_cliques = 1
46 the_cover = None
47 if True: # 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 True: # 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
65 return add_isolated_verts(the_cover)
68def branch(graph, k_num_cliques, the_cover, iteration, iteration_max):
69 """Helper function for `find_clique_min_cover()`.
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.
74 Parameters
75 ----------
76 graph : UndirectedDependenceGraph()
77 Class for representing undirected graph and auxilliary data used in edge clique cover algorithm.
79 k_num_cliques : int
80 Current depth of search; number of cliques in cover being testet for solution.
82 the_cover : np.array
83 Biadjacency matrix representing (possibly partial) edge clique cover.
85 iteration: current iteration
87 iteration_max: maximum number of iteration_max
89 Returns
90 -------
91 2d numpy array or None
92 Biadjacency matrix representing (complete) edge clique cover or None if cover is only partial.
94 """
96 iteration = iteration + 1
97 branch_graph = graph.reducible_copy()
98 # if the_cover is not None:
99 # print(the_cover)
100 # for clique in the_cover: # this might not be necessary, since the_cover_prime is only +1 clique
101 # print('clique: {}'.format(clique))
102 # branch_graph.the_cover = [clique]
103 # branch_graph.cover_edges() # only works one clique at a time, or on a list of edges
104 branch_graph.the_cover = the_cover
105 branch_graph.cover_edges()
107 if branch_graph.num_edges == 0:
108 return branch_graph.reconstruct_cover(the_cover)
110 # branch_graph.the_cover = the_cover
112 branch_graph.reduzieren(k_num_cliques)
113 k_num_cliques = branch_graph.k_num_cliques
115 if k_num_cliques < 0:
116 return None
118 if branch_graph.num_edges == 0: # equiv to len(branch_graph.extant_edges_idx)==0
119 return (
120 branch_graph.the_cover
121 ) # not in paper, but speeds it up slightly; or rather return None?
123 chosen_nbrhood = branch_graph.choose_nbrhood()
124 # print("num cliques: {}".format(len([x for x in max_cliques(chosen_nbrhood)])))
125 for clique_nodes in max_cliques(chosen_nbrhood):
126 if len(clique_nodes) == 1: # then this vert has been rmed; quirk of max_cliques
127 continue
128 clique = np.zeros(branch_graph.unreduced.num_vertices, dtype=int)
129 clique[clique_nodes] = 1
130 union = (
131 clique.reshape(1, -1)
132 if branch_graph.the_cover is None
133 else np.vstack((branch_graph.the_cover, clique))
134 )
136 # print(iteration)
137 if iteration > iteration_max:
138 return branch_graph.the_cover
140 the_cover_prime = branch(
141 branch_graph,
142 k_num_cliques - 1,
143 union,
144 iteration,
145 iteration_max=iteration_max,
146 )
147 if the_cover_prime is not None:
148 return the_cover_prime
149 return None
152def max_cliques(nbrhood):
153 """Adaptation of NetworkX code for finding all maximal cliques.
155 Parameters
156 ----------
157 nbrhood : np.array
158 Adjacency matrix for undirected (sub)graph.
160 Returns
161 -------
162 generator
163 set of all maximal cliques
165 Notes
166 -----
167 Pieced together from nx.from_numpy_array and nx.find_cliques, which
168 is output sensitive.
170 """
172 if len(nbrhood) == 0:
173 return
175 # convert adjacency matrix to nx style graph
176 adj = {
177 u: {v for v in np.nonzero(nbrhood[u])[0] if v != u} for u in range(len(nbrhood))
178 }
179 Q = [None]
181 subg = set(range(len(nbrhood)))
182 cand = set(range(len(nbrhood)))
183 u = max(subg, key=lambda u: len(cand & adj[u]))
184 ext_u = cand - adj[u]
185 stack = []
187 try:
188 while True:
189 if ext_u:
190 q = ext_u.pop()
191 cand.remove(q)
192 Q[-1] = q
193 adj_q = adj[q]
194 subg_q = subg & adj_q
195 if not subg_q:
196 yield Q[:]
197 else:
198 cand_q = cand & adj_q
199 if cand_q:
200 stack.append((subg, cand, ext_u))
201 Q.append(None)
202 subg = subg_q
203 cand = cand_q
204 u = max(subg, key=lambda u: len(cand & adj[u]))
205 ext_u = cand - adj[u]
206 else:
207 Q.pop()
208 subg, cand, ext_u = stack.pop()
209 except IndexError:
210 pass
211 # note: max_cliques is a generator, so it's consumed after being
212 # looped through once
215def add_isolated_verts(cover):
216 cover = cover.astype(bool)
217 iso_vert_idx = np.flatnonzero(cover.sum(0) == 0)
218 num_rows = len(iso_vert_idx)
219 num_cols = cover.shape[1]
220 iso_vert_cover = np.zeros((num_rows, num_cols), bool)
221 iso_vert_cover[np.arange(num_rows), iso_vert_idx] = True
222 return np.vstack((cover, iso_vert_cover))
225def find_heuristic_1pc(graph):
226 num_meas = len(graph)
228 # nx_graph = nx.from_numpy_array(graph)
229 # indep_set =
230 # list(nx.approximation.maximum_independent_set(nx_graph))
232 indep_sets = max_cliques(np.logical_not(graph))
233 max_indep_set = next(indep_sets)
234 for indep_set in indep_sets:
235 if len(indep_set) > len(max_indep_set):
236 max_indep_set = indep_set
238 num_latents = len(max_indep_set)
240 the_cover = np.zeros((num_latents, num_meas), bool)
241 the_cover[np.arange(num_latents), max_indep_set] = True
243 for idx, node in enumerate(max_indep_set):
244 nbrs = np.flatnonzero(graph[node])
245 the_cover[idx, nbrs] = True
247 uncovered_edges = deque(
248 {
249 tuple(edge)
250 for edge in np.argwhere(np.triu(graph, 1))
251 if not np.logical_and(the_cover[:, edge[0]], the_cover[:, edge[1]]).any()
252 }
253 )
255 while bool(uncovered_edges):
256 u, v = uncovered_edges.popleft()
257 if the_cover[:, u].any():
258 the_cover[np.argmax(the_cover[:, u]), v] = True
259 elif the_cover[:, v].any():
260 the_cover[np.argmax(the_cover[:, v]), u] = True
261 else:
262 uncovered_edges.append((u, v))
264 recon = the_cover.T @ the_cover
265 if np.logical_not(graph <= recon).any():
266 raise Exception(f"Problem with `find_hueristic_1pc()` for input {graph}")
268 return the_cover