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 # The node from the unnumbered set with the most connections
231 # to nodes in the numbered set
232 v = max(unnumbered, key=lambda n: len(G._adj[n].keys() & numbered))
233 unnumbered.remove(v)
234 numbered.add(v)
235 new_clique_wanna_be = set(C.neighbors(v)) & numbered
236 sg = C.subgraph(clique_wanna_be)
237 if _is_complete_graph(sg):
238 new_clique_wanna_be.add(v)
239 if not new_clique_wanna_be >= clique_wanna_be:
240 yield frozenset(clique_wanna_be)
241 clique_wanna_be = new_clique_wanna_be
242 else:
243 raise nx.NetworkXError("Input graph is not chordal.")
244 yield frozenset(clique_wanna_be)
247@nx._dispatchable
248def chordal_graph_treewidth(G):
249 """Returns the treewidth of the chordal graph `G`.
251 Parameters
252 ----------
253 G : graph
254 A chordal graph.
256 Returns
257 -------
258 treewidth : int
259 The size of the largest clique in the graph minus one.
261 Raises
262 ------
263 NetworkXError
264 If `G` is not chordal.
266 Examples
267 --------
268 >>> G = nx.barbell_graph(4, 6)
269 >>> nx.chordal_graph_treewidth(G)
270 3
272 See Also
273 --------
274 networkx.algorithms.approximation.treewidth.treewidth_min_degree
275 networkx.algorithms.approximation.treewidth.treewidth_min_fill_in
277 References
278 ----------
279 .. [1] https://en.wikipedia.org/wiki/Tree_decomposition#Treewidth
280 """
281 if not is_chordal(G):
282 raise nx.NetworkXError("Input graph is not chordal.")
284 return len(max(nx.chordal_graph_cliques(G), key=len)) - 1
287def _is_complete_graph(G):
288 """Returns True if G is a complete graph."""
289 if nx.number_of_selfloops(G) > 0:
290 raise nx.NetworkXError("Self loop found in _is_complete_graph()")
291 n = G.number_of_nodes()
292 if n < 2:
293 return True
294 e = G.number_of_edges()
295 max_edges = (n * (n - 1)) / 2
296 return e == max_edges
299def _find_missing_edge(G):
300 """Given a non-complete graph G, returns a missing edge."""
301 nodes = set(G)
302 for u in G:
303 missing = nodes - set(list(G[u].keys()) + [u])
304 if missing:
305 return (u, missing.pop())
308def _find_chordality_breaker(G, s=None, treewidth_bound=sys.maxsize):
309 """Given a graph G, starts a max cardinality search
310 (starting from s if s is given and from an arbitrary node otherwise)
311 trying to find a non-chordal cycle.
313 If it does find one, it returns (u,v,w) where u,v,w are the three
314 nodes that together with s are involved in the cycle.
316 It ignores any self loops.
317 """
318 if len(G) == 0:
319 raise nx.NetworkXPointlessConcept("Graph has no nodes.")
320 unnumbered = set(G)
321 if s is None:
322 s = arbitrary_element(G)
323 unnumbered.remove(s)
324 numbered = {s}
325 current_treewidth = -1
326 while unnumbered: # and current_treewidth <= treewidth_bound:
327 # The node from the unnumbered set with the most connections
328 # to nodes in the numbered set
329 v = max(unnumbered, key=lambda n: len(G._adj[n].keys() & numbered))
330 unnumbered.remove(v)
331 numbered.add(v)
332 clique_wanna_be = set(G[v]) & numbered
333 sg = G.subgraph(clique_wanna_be)
334 if _is_complete_graph(sg):
335 # The graph seems to be chordal by now. We update the treewidth
336 current_treewidth = max(current_treewidth, len(clique_wanna_be))
337 if current_treewidth > treewidth_bound:
338 raise nx.NetworkXTreewidthBoundExceeded(
339 f"treewidth_bound exceeded: {current_treewidth}"
340 )
341 else:
342 # sg is not a clique,
343 # look for an edge that is not included in sg
344 (u, w) = _find_missing_edge(sg)
345 return (u, v, w)
346 return ()
349@not_implemented_for("directed")
350@nx._dispatchable(returns_graph=True)
351def complete_to_chordal_graph(G):
352 """Return a copy of G completed to a chordal graph
354 Adds edges to a copy of G to create a chordal graph. A graph G=(V,E) is
355 called chordal if for each cycle with length bigger than 3, there exist
356 two non-adjacent nodes connected by an edge (called a chord).
358 Parameters
359 ----------
360 G : NetworkX graph
361 Undirected graph
363 Returns
364 -------
365 H : NetworkX graph
366 The chordal enhancement of G
367 alpha : Dictionary
368 The elimination ordering of nodes of G
370 Notes
371 -----
372 There are different approaches to calculate the chordal
373 enhancement of a graph. The algorithm used here is called
374 MCS-M and gives at least minimal (local) triangulation of graph. Note
375 that this triangulation is not necessarily a global minimum.
377 https://en.wikipedia.org/wiki/Chordal_graph
379 References
380 ----------
381 .. [1] Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004)
382 Maximum Cardinality Search for Computing Minimal Triangulations of
383 Graphs. Algorithmica. 39. 287-298. 10.1007/s00453-004-1084-3.
385 Examples
386 --------
387 >>> from networkx.algorithms.chordal import complete_to_chordal_graph
388 >>> G = nx.wheel_graph(10)
389 >>> H, alpha = complete_to_chordal_graph(G)
390 """
391 H = G.copy()
392 alpha = {node: 0 for node in H}
393 if nx.is_chordal(H):
394 return H, alpha
395 chords = set()
396 weight = {node: 0 for node in H.nodes()}
397 unnumbered_nodes = list(H.nodes())
398 for i in range(len(H.nodes()), 0, -1):
399 # get the node in unnumbered_nodes with the maximum weight
400 z = max(unnumbered_nodes, key=lambda node: weight[node])
401 unnumbered_nodes.remove(z)
402 alpha[z] = i
403 update_nodes = []
404 for y in unnumbered_nodes:
405 if G.has_edge(y, z):
406 update_nodes.append(y)
407 else:
408 # y_weight will be bigger than node weights between y and z
409 y_weight = weight[y]
410 lower_nodes = [
411 node for node in unnumbered_nodes if weight[node] < y_weight
412 ]
413 if nx.has_path(H.subgraph(lower_nodes + [z, y]), y, z):
414 update_nodes.append(y)
415 chords.add((z, y))
416 # during calculation of paths the weights should not be updated
417 for node in update_nodes:
418 weight[node] += 1
419 H.add_edges_from(chords)
420 return H, alpha