Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/chordal.py @ 0:4f3585e2f14b draft default tip
"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 """ | |
2 Algorithms for chordal graphs. | |
3 | |
4 A graph is chordal if every cycle of length at least 4 has a chord | |
5 (an edge joining two nodes not adjacent in the cycle). | |
6 https://en.wikipedia.org/wiki/Chordal_graph | |
7 """ | |
8 import sys | |
9 import warnings | |
10 | |
11 import networkx as nx | |
12 from networkx.algorithms.components import connected_components | |
13 from networkx.utils import arbitrary_element, not_implemented_for | |
14 | |
15 | |
16 __all__ = [ | |
17 "is_chordal", | |
18 "find_induced_nodes", | |
19 "chordal_graph_cliques", | |
20 "chordal_graph_treewidth", | |
21 "NetworkXTreewidthBoundExceeded", | |
22 "complete_to_chordal_graph", | |
23 ] | |
24 | |
25 | |
26 class NetworkXTreewidthBoundExceeded(nx.NetworkXException): | |
27 """Exception raised when a treewidth bound has been provided and it has | |
28 been exceeded""" | |
29 | |
30 | |
31 def is_chordal(G): | |
32 """Checks whether G is a chordal graph. | |
33 | |
34 A graph is chordal if every cycle of length at least 4 has a chord | |
35 (an edge joining two nodes not adjacent in the cycle). | |
36 | |
37 Parameters | |
38 ---------- | |
39 G : graph | |
40 A NetworkX graph. | |
41 | |
42 Returns | |
43 ------- | |
44 chordal : bool | |
45 True if G is a chordal graph and False otherwise. | |
46 | |
47 Raises | |
48 ------ | |
49 NetworkXError | |
50 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. | |
51 If the input graph is an instance of one of these classes, a | |
52 :exc:`NetworkXError` is raised. | |
53 | |
54 Examples | |
55 -------- | |
56 >>> e = [ | |
57 ... (1, 2), | |
58 ... (1, 3), | |
59 ... (2, 3), | |
60 ... (2, 4), | |
61 ... (3, 4), | |
62 ... (3, 5), | |
63 ... (3, 6), | |
64 ... (4, 5), | |
65 ... (4, 6), | |
66 ... (5, 6), | |
67 ... ] | |
68 >>> G = nx.Graph(e) | |
69 >>> nx.is_chordal(G) | |
70 True | |
71 | |
72 Notes | |
73 ----- | |
74 The routine tries to go through every node following maximum cardinality | |
75 search. It returns False when it finds that the separator for any node | |
76 is not a clique. Based on the algorithms in [1]_. | |
77 | |
78 References | |
79 ---------- | |
80 .. [1] R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms | |
81 to test chordality of graphs, test acyclicity of hypergraphs, and | |
82 selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), | |
83 pp. 566–579. | |
84 """ | |
85 if G.is_directed(): | |
86 raise nx.NetworkXError("Directed graphs not supported") | |
87 if G.is_multigraph(): | |
88 raise nx.NetworkXError("Multiply connected graphs not supported.") | |
89 if len(_find_chordality_breaker(G)) == 0: | |
90 return True | |
91 else: | |
92 return False | |
93 | |
94 | |
95 def find_induced_nodes(G, s, t, treewidth_bound=sys.maxsize): | |
96 """Returns the set of induced nodes in the path from s to t. | |
97 | |
98 Parameters | |
99 ---------- | |
100 G : graph | |
101 A chordal NetworkX graph | |
102 s : node | |
103 Source node to look for induced nodes | |
104 t : node | |
105 Destination node to look for induced nodes | |
106 treewith_bound: float | |
107 Maximum treewidth acceptable for the graph H. The search | |
108 for induced nodes will end as soon as the treewidth_bound is exceeded. | |
109 | |
110 Returns | |
111 ------- | |
112 Induced_nodes : Set of nodes | |
113 The set of induced nodes in the path from s to t in G | |
114 | |
115 Raises | |
116 ------ | |
117 NetworkXError | |
118 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. | |
119 If the input graph is an instance of one of these classes, a | |
120 :exc:`NetworkXError` is raised. | |
121 The algorithm can only be applied to chordal graphs. If the input | |
122 graph is found to be non-chordal, a :exc:`NetworkXError` is raised. | |
123 | |
124 Examples | |
125 -------- | |
126 >>> G = nx.Graph() | |
127 >>> G = nx.generators.classic.path_graph(10) | |
128 >>> induced_nodes = nx.find_induced_nodes(G, 1, 9, 2) | |
129 >>> sorted(induced_nodes) | |
130 [1, 2, 3, 4, 5, 6, 7, 8, 9] | |
131 | |
132 Notes | |
133 ----- | |
134 G must be a chordal graph and (s,t) an edge that is not in G. | |
135 | |
136 If a treewidth_bound is provided, the search for induced nodes will end | |
137 as soon as the treewidth_bound is exceeded. | |
138 | |
139 The algorithm is inspired by Algorithm 4 in [1]_. | |
140 A formal definition of induced node can also be found on that reference. | |
141 | |
142 References | |
143 ---------- | |
144 .. [1] Learning Bounded Treewidth Bayesian Networks. | |
145 Gal Elidan, Stephen Gould; JMLR, 9(Dec):2699--2731, 2008. | |
146 http://jmlr.csail.mit.edu/papers/volume9/elidan08a/elidan08a.pdf | |
147 """ | |
148 if not is_chordal(G): | |
149 raise nx.NetworkXError("Input graph is not chordal.") | |
150 | |
151 H = nx.Graph(G) | |
152 H.add_edge(s, t) | |
153 Induced_nodes = set() | |
154 triplet = _find_chordality_breaker(H, s, treewidth_bound) | |
155 while triplet: | |
156 (u, v, w) = triplet | |
157 Induced_nodes.update(triplet) | |
158 for n in triplet: | |
159 if n != s: | |
160 H.add_edge(s, n) | |
161 triplet = _find_chordality_breaker(H, s, treewidth_bound) | |
162 if Induced_nodes: | |
163 # Add t and the second node in the induced path from s to t. | |
164 Induced_nodes.add(t) | |
165 for u in G[s]: | |
166 if len(Induced_nodes & set(G[u])) == 2: | |
167 Induced_nodes.add(u) | |
168 break | |
169 return Induced_nodes | |
170 | |
171 | |
172 def chordal_graph_cliques(G): | |
173 """Returns the set of maximal cliques of a chordal graph. | |
174 | |
175 The algorithm breaks the graph in connected components and performs a | |
176 maximum cardinality search in each component to get the cliques. | |
177 | |
178 Parameters | |
179 ---------- | |
180 G : graph | |
181 A NetworkX graph | |
182 | |
183 Returns | |
184 ------- | |
185 cliques : A set containing the maximal cliques in G. | |
186 | |
187 Raises | |
188 ------ | |
189 NetworkXError | |
190 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. | |
191 If the input graph is an instance of one of these classes, a | |
192 :exc:`NetworkXError` is raised. | |
193 The algorithm can only be applied to chordal graphs. If the input | |
194 graph is found to be non-chordal, a :exc:`NetworkXError` is raised. | |
195 | |
196 Examples | |
197 -------- | |
198 >>> e = [ | |
199 ... (1, 2), | |
200 ... (1, 3), | |
201 ... (2, 3), | |
202 ... (2, 4), | |
203 ... (3, 4), | |
204 ... (3, 5), | |
205 ... (3, 6), | |
206 ... (4, 5), | |
207 ... (4, 6), | |
208 ... (5, 6), | |
209 ... (7, 8), | |
210 ... ] | |
211 >>> G = nx.Graph(e) | |
212 >>> G.add_node(9) | |
213 >>> setlist = nx.chordal_graph_cliques(G) | |
214 """ | |
215 msg = "This will return a generator in 3.0." | |
216 warnings.warn(msg, DeprecationWarning) | |
217 return {c for c in _chordal_graph_cliques(G)} | |
218 | |
219 | |
220 def chordal_graph_treewidth(G): | |
221 """Returns the treewidth of the chordal graph G. | |
222 | |
223 Parameters | |
224 ---------- | |
225 G : graph | |
226 A NetworkX graph | |
227 | |
228 Returns | |
229 ------- | |
230 treewidth : int | |
231 The size of the largest clique in the graph minus one. | |
232 | |
233 Raises | |
234 ------ | |
235 NetworkXError | |
236 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. | |
237 If the input graph is an instance of one of these classes, a | |
238 :exc:`NetworkXError` is raised. | |
239 The algorithm can only be applied to chordal graphs. If the input | |
240 graph is found to be non-chordal, a :exc:`NetworkXError` is raised. | |
241 | |
242 Examples | |
243 -------- | |
244 >>> e = [ | |
245 ... (1, 2), | |
246 ... (1, 3), | |
247 ... (2, 3), | |
248 ... (2, 4), | |
249 ... (3, 4), | |
250 ... (3, 5), | |
251 ... (3, 6), | |
252 ... (4, 5), | |
253 ... (4, 6), | |
254 ... (5, 6), | |
255 ... (7, 8), | |
256 ... ] | |
257 >>> G = nx.Graph(e) | |
258 >>> G.add_node(9) | |
259 >>> nx.chordal_graph_treewidth(G) | |
260 3 | |
261 | |
262 References | |
263 ---------- | |
264 .. [1] https://en.wikipedia.org/wiki/Tree_decomposition#Treewidth | |
265 """ | |
266 if not is_chordal(G): | |
267 raise nx.NetworkXError("Input graph is not chordal.") | |
268 | |
269 max_clique = -1 | |
270 for clique in nx.chordal_graph_cliques(G): | |
271 max_clique = max(max_clique, len(clique)) | |
272 return max_clique - 1 | |
273 | |
274 | |
275 def _is_complete_graph(G): | |
276 """Returns True if G is a complete graph.""" | |
277 if nx.number_of_selfloops(G) > 0: | |
278 raise nx.NetworkXError("Self loop found in _is_complete_graph()") | |
279 n = G.number_of_nodes() | |
280 if n < 2: | |
281 return True | |
282 e = G.number_of_edges() | |
283 max_edges = (n * (n - 1)) / 2 | |
284 return e == max_edges | |
285 | |
286 | |
287 def _find_missing_edge(G): | |
288 """ Given a non-complete graph G, returns a missing edge.""" | |
289 nodes = set(G) | |
290 for u in G: | |
291 missing = nodes - set(list(G[u].keys()) + [u]) | |
292 if missing: | |
293 return (u, missing.pop()) | |
294 | |
295 | |
296 def _max_cardinality_node(G, choices, wanna_connect): | |
297 """Returns a the node in choices that has more connections in G | |
298 to nodes in wanna_connect. | |
299 """ | |
300 max_number = -1 | |
301 for x in choices: | |
302 number = len([y for y in G[x] if y in wanna_connect]) | |
303 if number > max_number: | |
304 max_number = number | |
305 max_cardinality_node = x | |
306 return max_cardinality_node | |
307 | |
308 | |
309 def _find_chordality_breaker(G, s=None, treewidth_bound=sys.maxsize): | |
310 """ Given a graph G, starts a max cardinality search | |
311 (starting from s if s is given and from an arbitrary node otherwise) | |
312 trying to find a non-chordal cycle. | |
313 | |
314 If it does find one, it returns (u,v,w) where u,v,w are the three | |
315 nodes that together with s are involved in the cycle. | |
316 """ | |
317 | |
318 unnumbered = set(G) | |
319 if s is None: | |
320 s = arbitrary_element(G) | |
321 unnumbered.remove(s) | |
322 numbered = {s} | |
323 current_treewidth = -1 | |
324 while unnumbered: # and current_treewidth <= treewidth_bound: | |
325 v = _max_cardinality_node(G, unnumbered, numbered) | |
326 unnumbered.remove(v) | |
327 numbered.add(v) | |
328 clique_wanna_be = set(G[v]) & numbered | |
329 sg = G.subgraph(clique_wanna_be) | |
330 if _is_complete_graph(sg): | |
331 # The graph seems to be chordal by now. We update the treewidth | |
332 current_treewidth = max(current_treewidth, len(clique_wanna_be)) | |
333 if current_treewidth > treewidth_bound: | |
334 raise nx.NetworkXTreewidthBoundExceeded( | |
335 f"treewidth_bound exceeded: {current_treewidth}" | |
336 ) | |
337 else: | |
338 # sg is not a clique, | |
339 # look for an edge that is not included in sg | |
340 (u, w) = _find_missing_edge(sg) | |
341 return (u, v, w) | |
342 return () | |
343 | |
344 | |
345 def _chordal_graph_cliques(G): | |
346 """Returns all maximal cliques of a chordal graph. | |
347 | |
348 The algorithm breaks the graph in connected components and performs a | |
349 maximum cardinality search in each component to get the cliques. | |
350 | |
351 Parameters | |
352 ---------- | |
353 G : graph | |
354 A NetworkX graph | |
355 | |
356 Returns | |
357 ------- | |
358 iterator | |
359 An iterator over maximal cliques, each of which is a frozenset of | |
360 nodes in `G`. The order of cliques is arbitrary. | |
361 | |
362 Raises | |
363 ------ | |
364 NetworkXError | |
365 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. | |
366 If the input graph is an instance of one of these classes, a | |
367 :exc:`NetworkXError` is raised. | |
368 The algorithm can only be applied to chordal graphs. If the input | |
369 graph is found to be non-chordal, a :exc:`NetworkXError` is raised. | |
370 | |
371 Examples | |
372 -------- | |
373 >>> e = [ | |
374 ... (1, 2), | |
375 ... (1, 3), | |
376 ... (2, 3), | |
377 ... (2, 4), | |
378 ... (3, 4), | |
379 ... (3, 5), | |
380 ... (3, 6), | |
381 ... (4, 5), | |
382 ... (4, 6), | |
383 ... (5, 6), | |
384 ... (7, 8), | |
385 ... ] | |
386 >>> G = nx.Graph(e) | |
387 >>> G.add_node(9) | |
388 >>> cliques = [c for c in _chordal_graph_cliques(G)] | |
389 >>> cliques[0] | |
390 frozenset({1, 2, 3}) | |
391 """ | |
392 if not is_chordal(G): | |
393 raise nx.NetworkXError("Input graph is not chordal.") | |
394 | |
395 for C in (G.subgraph(c).copy() for c in connected_components(G)): | |
396 if C.number_of_nodes() == 1: | |
397 yield frozenset(C.nodes()) | |
398 else: | |
399 unnumbered = set(C.nodes()) | |
400 v = arbitrary_element(C) | |
401 unnumbered.remove(v) | |
402 numbered = {v} | |
403 clique_wanna_be = {v} | |
404 while unnumbered: | |
405 v = _max_cardinality_node(C, unnumbered, numbered) | |
406 unnumbered.remove(v) | |
407 numbered.add(v) | |
408 new_clique_wanna_be = set(C.neighbors(v)) & numbered | |
409 sg = C.subgraph(clique_wanna_be) | |
410 if _is_complete_graph(sg): | |
411 new_clique_wanna_be.add(v) | |
412 if not new_clique_wanna_be >= clique_wanna_be: | |
413 yield frozenset(clique_wanna_be) | |
414 clique_wanna_be = new_clique_wanna_be | |
415 else: | |
416 raise nx.NetworkXError("Input graph is not chordal.") | |
417 yield frozenset(clique_wanna_be) | |
418 | |
419 | |
420 @not_implemented_for("directed") | |
421 def complete_to_chordal_graph(G): | |
422 """Return a copy of G completed to a chordal graph | |
423 | |
424 Adds edges to a copy of G to create a chordal graph. A graph G=(V,E) is | |
425 called chordal if for each cycle with length bigger than 3, there exist | |
426 two non-adjacent nodes connected by an edge (called a chord). | |
427 | |
428 Parameters | |
429 ---------- | |
430 G : NetworkX graph | |
431 Undirected graph | |
432 | |
433 Returns | |
434 ------- | |
435 H : NetworkX graph | |
436 The chordal enhancement of G | |
437 alpha : Dictionary | |
438 The elimination ordering of nodes of G | |
439 | |
440 Notes | |
441 ------ | |
442 There are different approaches to calculate the chordal | |
443 enhancement of a graph. The algorithm used here is called | |
444 MCS-M and gives at least minimal (local) triangulation of graph. Note | |
445 that this triangulation is not necessarily a global minimum. | |
446 | |
447 https://en.wikipedia.org/wiki/Chordal_graph | |
448 | |
449 References | |
450 ---------- | |
451 .. [1] Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004) | |
452 Maximum Cardinality Search for Computing Minimal Triangulations of | |
453 Graphs. Algorithmica. 39. 287-298. 10.1007/s00453-004-1084-3. | |
454 | |
455 Examples | |
456 -------- | |
457 >>> from networkx.algorithms.chordal import complete_to_chordal_graph | |
458 >>> G = nx.wheel_graph(10) | |
459 >>> H, alpha = complete_to_chordal_graph(G) | |
460 """ | |
461 H = G.copy() | |
462 alpha = {node: 0 for node in H} | |
463 if nx.is_chordal(H): | |
464 return H, alpha | |
465 chords = set() | |
466 weight = {node: 0 for node in H.nodes()} | |
467 unnumbered_nodes = list(H.nodes()) | |
468 for i in range(len(H.nodes()), 0, -1): | |
469 # get the node in unnumbered_nodes with the maximum weight | |
470 z = max(unnumbered_nodes, key=lambda node: weight[node]) | |
471 unnumbered_nodes.remove(z) | |
472 alpha[z] = i | |
473 update_nodes = [] | |
474 for y in unnumbered_nodes: | |
475 if G.has_edge(y, z): | |
476 update_nodes.append(y) | |
477 else: | |
478 # y_weight will be bigger than node weights between y and z | |
479 y_weight = weight[y] | |
480 lower_nodes = [ | |
481 node for node in unnumbered_nodes if weight[node] < y_weight | |
482 ] | |
483 if nx.has_path(H.subgraph(lower_nodes + [z, y]), y, z): | |
484 update_nodes.append(y) | |
485 chords.add((z, y)) | |
486 # during calculation of paths the weights should not be updated | |
487 for node in update_nodes: | |
488 weight[node] += 1 | |
489 H.add_edges_from(chords) | |
490 return H, alpha |