Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Algorithms for chordal graphs.
4A 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).
6https://en.wikipedia.org/wiki/Chordal_graph
7"""
9import sys
11import networkx as nx
12from networkx.algorithms.components import connected_components
13from networkx.utils import arbitrary_element, not_implemented_for
15__all__ = [
16 "is_chordal",
17 "find_induced_nodes",
18 "chordal_graph_cliques",
19 "chordal_graph_treewidth",
20 "NetworkXTreewidthBoundExceeded",
21 "complete_to_chordal_graph",
22]
25class NetworkXTreewidthBoundExceeded(nx.NetworkXException):
26 """Exception raised when a treewidth bound has been provided and it has
27 been exceeded"""
30@not_implemented_for("directed")
31@not_implemented_for("multigraph")
32@nx._dispatchable
33def is_chordal(G):
34 """Checks whether G is a chordal graph.
36 A graph is chordal if every cycle of length at least 4 has a chord
37 (an edge joining two nodes not adjacent in the cycle).
39 Parameters
40 ----------
41 G : graph
42 A NetworkX graph.
44 Returns
45 -------
46 chordal : bool
47 True if G is a chordal graph and False otherwise.
49 Raises
50 ------
51 NetworkXNotImplemented
52 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
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
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]_.
78 Self loops are ignored.
80 References
81 ----------
82 .. [1] R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms
83 to test chordality of graphs, test acyclicity of hypergraphs, and
84 selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984),
85 pp. 566–579.
86 """
87 if len(G.nodes) <= 3:
88 return True
89 return len(_find_chordality_breaker(G)) == 0
92@nx._dispatchable
93def find_induced_nodes(G, s, t, treewidth_bound=sys.maxsize):
94 """Returns the set of induced nodes in the path from s to t.
96 Parameters
97 ----------
98 G : graph
99 A chordal NetworkX graph
100 s : node
101 Source node to look for induced nodes
102 t : node
103 Destination node to look for induced nodes
104 treewidth_bound: float
105 Maximum treewidth acceptable for the graph H. The search
106 for induced nodes will end as soon as the treewidth_bound is exceeded.
108 Returns
109 -------
110 induced_nodes : Set of nodes
111 The set of induced nodes in the path from s to t in G
113 Raises
114 ------
115 NetworkXError
116 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
117 If the input graph is an instance of one of these classes, a
118 :exc:`NetworkXError` is raised.
119 The algorithm can only be applied to chordal graphs. If the input
120 graph is found to be non-chordal, a :exc:`NetworkXError` is raised.
122 Examples
123 --------
124 >>> G = nx.Graph()
125 >>> G = nx.generators.classic.path_graph(10)
126 >>> induced_nodes = nx.find_induced_nodes(G, 1, 9, 2)
127 >>> sorted(induced_nodes)
128 [1, 2, 3, 4, 5, 6, 7, 8, 9]
130 Notes
131 -----
132 G must be a chordal graph and (s,t) an edge that is not in G.
134 If a treewidth_bound is provided, the search for induced nodes will end
135 as soon as the treewidth_bound is exceeded.
137 The algorithm is inspired by Algorithm 4 in [1]_.
138 A formal definition of induced node can also be found on that reference.
140 Self Loops are ignored
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.")
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
172@nx._dispatchable
173def chordal_graph_cliques(G):
174 """Returns all maximal cliques of a chordal graph.
176 The algorithm breaks the graph in connected components and performs a
177 maximum cardinality search in each component to get the cliques.
179 Parameters
180 ----------
181 G : graph
182 A NetworkX graph
184 Yields
185 ------
186 frozenset of nodes
187 Maximal cliques, each of which is a frozenset of
188 nodes in `G`. The order of cliques is arbitrary.
190 Raises
191 ------
192 NetworkXError
193 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
194 The algorithm can only be applied to chordal graphs. If the input
195 graph is found to be non-chordal, a :exc:`NetworkXError` is raised.
197 Examples
198 --------
199 >>> e = [
200 ... (1, 2),
201 ... (1, 3),
202 ... (2, 3),
203 ... (2, 4),
204 ... (3, 4),
205 ... (3, 5),
206 ... (3, 6),
207 ... (4, 5),
208 ... (4, 6),
209 ... (5, 6),
210 ... (7, 8),
211 ... ]
212 >>> G = nx.Graph(e)
213 >>> G.add_node(9)
214 >>> cliques = [c for c in chordal_graph_cliques(G)]
215 >>> cliques[0]
216 frozenset({1, 2, 3})
217 """
218 for C in (G.subgraph(c).copy() for c in connected_components(G)):
219 if C.number_of_nodes() == 1:
220 if nx.number_of_selfloops(C) > 0:
221 raise nx.NetworkXError("Input graph is not chordal.")
222 yield frozenset(C.nodes())
223 else:
224 unnumbered = set(C.nodes())
225 v = arbitrary_element(C)
226 unnumbered.remove(v)
227 numbered = {v}
228 clique_wanna_be = {v}
229 while unnumbered:
230 v = _max_cardinality_node(C, unnumbered, numbered)
231 unnumbered.remove(v)
232 numbered.add(v)
233 new_clique_wanna_be = set(C.neighbors(v)) & numbered
234 sg = C.subgraph(clique_wanna_be)
235 if _is_complete_graph(sg):
236 new_clique_wanna_be.add(v)
237 if not new_clique_wanna_be >= clique_wanna_be:
238 yield frozenset(clique_wanna_be)
239 clique_wanna_be = new_clique_wanna_be
240 else:
241 raise nx.NetworkXError("Input graph is not chordal.")
242 yield frozenset(clique_wanna_be)
245@nx._dispatchable
246def chordal_graph_treewidth(G):
247 """Returns the treewidth of the chordal graph G.
249 Parameters
250 ----------
251 G : graph
252 A NetworkX graph
254 Returns
255 -------
256 treewidth : int
257 The size of the largest clique in the graph minus one.
259 Raises
260 ------
261 NetworkXError
262 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.
263 The algorithm can only be applied to chordal graphs. If the input
264 graph is found to be non-chordal, a :exc:`NetworkXError` is raised.
266 Examples
267 --------
268 >>> e = [
269 ... (1, 2),
270 ... (1, 3),
271 ... (2, 3),
272 ... (2, 4),
273 ... (3, 4),
274 ... (3, 5),
275 ... (3, 6),
276 ... (4, 5),
277 ... (4, 6),
278 ... (5, 6),
279 ... (7, 8),
280 ... ]
281 >>> G = nx.Graph(e)
282 >>> G.add_node(9)
283 >>> nx.chordal_graph_treewidth(G)
284 3
286 References
287 ----------
288 .. [1] https://en.wikipedia.org/wiki/Tree_decomposition#Treewidth
289 """
290 if not is_chordal(G):
291 raise nx.NetworkXError("Input graph is not chordal.")
293 max_clique = -1
294 for clique in nx.chordal_graph_cliques(G):
295 max_clique = max(max_clique, len(clique))
296 return max_clique - 1
299def _is_complete_graph(G):
300 """Returns True if G is a complete graph."""
301 if nx.number_of_selfloops(G) > 0:
302 raise nx.NetworkXError("Self loop found in _is_complete_graph()")
303 n = G.number_of_nodes()
304 if n < 2:
305 return True
306 e = G.number_of_edges()
307 max_edges = (n * (n - 1)) / 2
308 return e == max_edges
311def _find_missing_edge(G):
312 """Given a non-complete graph G, returns a missing edge."""
313 nodes = set(G)
314 for u in G:
315 missing = nodes - set(list(G[u].keys()) + [u])
316 if missing:
317 return (u, missing.pop())
320def _max_cardinality_node(G, choices, wanna_connect):
321 """Returns a the node in choices that has more connections in G
322 to nodes in wanna_connect.
323 """
324 max_number = -1
325 for x in choices:
326 number = len([y for y in G[x] if y in wanna_connect])
327 if number > max_number:
328 max_number = number
329 max_cardinality_node = x
330 return max_cardinality_node
333def _find_chordality_breaker(G, s=None, treewidth_bound=sys.maxsize):
334 """Given a graph G, starts a max cardinality search
335 (starting from s if s is given and from an arbitrary node otherwise)
336 trying to find a non-chordal cycle.
338 If it does find one, it returns (u,v,w) where u,v,w are the three
339 nodes that together with s are involved in the cycle.
341 It ignores any self loops.
342 """
343 if len(G) == 0:
344 raise nx.NetworkXPointlessConcept("Graph has no nodes.")
345 unnumbered = set(G)
346 if s is None:
347 s = arbitrary_element(G)
348 unnumbered.remove(s)
349 numbered = {s}
350 current_treewidth = -1
351 while unnumbered: # and current_treewidth <= treewidth_bound:
352 v = _max_cardinality_node(G, unnumbered, numbered)
353 unnumbered.remove(v)
354 numbered.add(v)
355 clique_wanna_be = set(G[v]) & numbered
356 sg = G.subgraph(clique_wanna_be)
357 if _is_complete_graph(sg):
358 # The graph seems to be chordal by now. We update the treewidth
359 current_treewidth = max(current_treewidth, len(clique_wanna_be))
360 if current_treewidth > treewidth_bound:
361 raise nx.NetworkXTreewidthBoundExceeded(
362 f"treewidth_bound exceeded: {current_treewidth}"
363 )
364 else:
365 # sg is not a clique,
366 # look for an edge that is not included in sg
367 (u, w) = _find_missing_edge(sg)
368 return (u, v, w)
369 return ()
372@not_implemented_for("directed")
373@nx._dispatchable(returns_graph=True)
374def complete_to_chordal_graph(G):
375 """Return a copy of G completed to a chordal graph
377 Adds edges to a copy of G to create a chordal graph. A graph G=(V,E) is
378 called chordal if for each cycle with length bigger than 3, there exist
379 two non-adjacent nodes connected by an edge (called a chord).
381 Parameters
382 ----------
383 G : NetworkX graph
384 Undirected graph
386 Returns
387 -------
388 H : NetworkX graph
389 The chordal enhancement of G
390 alpha : Dictionary
391 The elimination ordering of nodes of G
393 Notes
394 -----
395 There are different approaches to calculate the chordal
396 enhancement of a graph. The algorithm used here is called
397 MCS-M and gives at least minimal (local) triangulation of graph. Note
398 that this triangulation is not necessarily a global minimum.
400 https://en.wikipedia.org/wiki/Chordal_graph
402 References
403 ----------
404 .. [1] Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004)
405 Maximum Cardinality Search for Computing Minimal Triangulations of
406 Graphs. Algorithmica. 39. 287-298. 10.1007/s00453-004-1084-3.
408 Examples
409 --------
410 >>> from networkx.algorithms.chordal import complete_to_chordal_graph
411 >>> G = nx.wheel_graph(10)
412 >>> H, alpha = complete_to_chordal_graph(G)
413 """
414 H = G.copy()
415 alpha = {node: 0 for node in H}
416 if nx.is_chordal(H):
417 return H, alpha
418 chords = set()
419 weight = {node: 0 for node in H.nodes()}
420 unnumbered_nodes = list(H.nodes())
421 for i in range(len(H.nodes()), 0, -1):
422 # get the node in unnumbered_nodes with the maximum weight
423 z = max(unnumbered_nodes, key=lambda node: weight[node])
424 unnumbered_nodes.remove(z)
425 alpha[z] = i
426 update_nodes = []
427 for y in unnumbered_nodes:
428 if G.has_edge(y, z):
429 update_nodes.append(y)
430 else:
431 # y_weight will be bigger than node weights between y and z
432 y_weight = weight[y]
433 lower_nodes = [
434 node for node in unnumbered_nodes if weight[node] < y_weight
435 ]
436 if nx.has_path(H.subgraph(lower_nodes + [z, y]), y, z):
437 update_nodes.append(y)
438 chords.add((z, y))
439 # during calculation of paths the weights should not be updated
440 for node in update_nodes:
441 weight[node] += 1
442 H.add_edges_from(chords)
443 return H, alpha