Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/chordal.py: 17%

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"""

8import sys

10import networkx as nx

11from networkx.algorithms.components import connected_components

12from networkx.utils import arbitrary_element, not_implemented_for

14__all__ = [

15 "is_chordal",

16 "find_induced_nodes",

17 "chordal_graph_cliques",

18 "chordal_graph_treewidth",

19 "NetworkXTreewidthBoundExceeded",

20 "complete_to_chordal_graph",

21]

24class NetworkXTreewidthBoundExceeded(nx.NetworkXException):

25 """Exception raised when a treewidth bound has been provided and it has

26 been exceeded"""

29@not_implemented_for("directed")

30@not_implemented_for("multigraph")

31@nx._dispatch

32def is_chordal(G):

33 """Checks whether G is a chordal graph.

35 A graph is chordal if every cycle of length at least 4 has a chord

36 (an edge joining two nodes not adjacent in the cycle).

38 Parameters

39 ----------

40 G : graph

41 A NetworkX graph.

43 Returns

44 -------

45 chordal : bool

46 True if G is a chordal graph and False otherwise.

48 Raises

49 ------

50 NetworkXNotImplemented

51 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.

53 Examples

54 --------

55 >>> e = [

56 ... (1, 2),

57 ... (1, 3),

58 ... (2, 3),

59 ... (2, 4),

60 ... (3, 4),

61 ... (3, 5),

62 ... (3, 6),

63 ... (4, 5),

64 ... (4, 6),

65 ... (5, 6),

66 ... ]

67 >>> G = nx.Graph(e)

68 >>> nx.is_chordal(G)

69 True

71 Notes

72 -----

73 The routine tries to go through every node following maximum cardinality

74 search. It returns False when it finds that the separator for any node

75 is not a clique. Based on the algorithms in [1]_.

77 Self loops are ignored.

79 References

80 ----------

81 .. [1] R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms

82 to test chordality of graphs, test acyclicity of hypergraphs, and

83 selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984),

84 pp. 566–579.

85 """

86 if len(G.nodes) <= 3:

87 return True

88 return len(_find_chordality_breaker(G)) == 0

91@nx._dispatch

92def find_induced_nodes(G, s, t, treewidth_bound=sys.maxsize):

93 """Returns the set of induced nodes in the path from s to t.

95 Parameters

96 ----------

97 G : graph

98 A chordal NetworkX graph

99 s : node

100 Source node to look for induced nodes

101 t : node

102 Destination node to look for induced nodes

103 treewidth_bound: float

104 Maximum treewidth acceptable for the graph H. The search

105 for induced nodes will end as soon as the treewidth_bound is exceeded.

106

107 Returns

108 -------

109 induced_nodes : Set of nodes

110 The set of induced nodes in the path from s to t in G

111

112 Raises

113 ------

114 NetworkXError

115 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.

116 If the input graph is an instance of one of these classes, a

117 :exc:`NetworkXError` is raised.

118 The algorithm can only be applied to chordal graphs. If the input

119 graph is found to be non-chordal, a :exc:`NetworkXError` is raised.

120

121 Examples

122 --------

123 >>> G = nx.Graph()

124 >>> G = nx.generators.classic.path_graph(10)

125 >>> induced_nodes = nx.find_induced_nodes(G, 1, 9, 2)

126 >>> sorted(induced_nodes)

127 [1, 2, 3, 4, 5, 6, 7, 8, 9]

128

129 Notes

130 -----

131 G must be a chordal graph and (s,t) an edge that is not in G.

132

133 If a treewidth_bound is provided, the search for induced nodes will end

134 as soon as the treewidth_bound is exceeded.

135

136 The algorithm is inspired by Algorithm 4 in [1]_.

137 A formal definition of induced node can also be found on that reference.

138

139 Self Loops are ignored

140

141 References

142 ----------

143 .. [1] Learning Bounded Treewidth Bayesian Networks.

144 Gal Elidan, Stephen Gould; JMLR, 9(Dec):2699--2731, 2008.

145 http://jmlr.csail.mit.edu/papers/volume9/elidan08a/elidan08a.pdf

146 """

147 if not is_chordal(G):

148 raise nx.NetworkXError("Input graph is not chordal.")

149

150 H = nx.Graph(G)

151 H.add_edge(s, t)

152 induced_nodes = set()

153 triplet = _find_chordality_breaker(H, s, treewidth_bound)

154 while triplet:

155 (u, v, w) = triplet

156 induced_nodes.update(triplet)

157 for n in triplet:

158 if n != s:

159 H.add_edge(s, n)

160 triplet = _find_chordality_breaker(H, s, treewidth_bound)

161 if induced_nodes:

162 # Add t and the second node in the induced path from s to t.

163 induced_nodes.add(t)

164 for u in G[s]:

165 if len(induced_nodes & set(G[u])) == 2:

166 induced_nodes.add(u)

167 break

168 return induced_nodes

169

170

171@nx._dispatch

172def chordal_graph_cliques(G):

173 """Returns all 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 Yields

184 ------

185 frozenset of nodes

186 Maximal cliques, each of which is a frozenset of

187 nodes in `G`. The order of cliques is arbitrary.

188

189 Raises

190 ------

191 NetworkXError

192 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.

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 >>> cliques = [c for c in chordal_graph_cliques(G)]

214 >>> cliques[0]

215 frozenset({1, 2, 3})

216 """

217 for C in (G.subgraph(c).copy() for c in connected_components(G)):

218 if C.number_of_nodes() == 1:

219 if nx.number_of_selfloops(C) > 0:

220 raise nx.NetworkXError("Input graph is not chordal.")

221 yield frozenset(C.nodes())

222 else:

223 unnumbered = set(C.nodes())

224 v = arbitrary_element(C)

225 unnumbered.remove(v)

226 numbered = {v}

227 clique_wanna_be = {v}

228 while unnumbered:

229 v = _max_cardinality_node(C, unnumbered, numbered)

230 unnumbered.remove(v)

231 numbered.add(v)

232 new_clique_wanna_be = set(C.neighbors(v)) & numbered

233 sg = C.subgraph(clique_wanna_be)

234 if _is_complete_graph(sg):

235 new_clique_wanna_be.add(v)

236 if not new_clique_wanna_be >= clique_wanna_be:

237 yield frozenset(clique_wanna_be)

238 clique_wanna_be = new_clique_wanna_be

239 else:

240 raise nx.NetworkXError("Input graph is not chordal.")

241 yield frozenset(clique_wanna_be)

242

243

244@nx._dispatch

245def chordal_graph_treewidth(G):

246 """Returns the treewidth of the chordal graph G.

247

248 Parameters

249 ----------

250 G : graph

251 A NetworkX graph

252

253 Returns

254 -------

255 treewidth : int

256 The size of the largest clique in the graph minus one.

257

258 Raises

259 ------

260 NetworkXError

261 The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.

262 The algorithm can only be applied to chordal graphs. If the input

263 graph is found to be non-chordal, a :exc:`NetworkXError` is raised.

264

265 Examples

266 --------

267 >>> e = [

268 ... (1, 2),

269 ... (1, 3),

270 ... (2, 3),

271 ... (2, 4),

272 ... (3, 4),

273 ... (3, 5),

274 ... (3, 6),

275 ... (4, 5),

276 ... (4, 6),

277 ... (5, 6),

278 ... (7, 8),

279 ... ]

280 >>> G = nx.Graph(e)

281 >>> G.add_node(9)

282 >>> nx.chordal_graph_treewidth(G)

283 3

284

285 References

286 ----------

287 .. [1] https://en.wikipedia.org/wiki/Tree_decomposition#Treewidth

288 """

289 if not is_chordal(G):

290 raise nx.NetworkXError("Input graph is not chordal.")

291

292 max_clique = -1

293 for clique in nx.chordal_graph_cliques(G):

294 max_clique = max(max_clique, len(clique))

295 return max_clique - 1

296

297

298def _is_complete_graph(G):

299 """Returns True if G is a complete graph."""

300 if nx.number_of_selfloops(G) > 0:

301 raise nx.NetworkXError("Self loop found in _is_complete_graph()")

302 n = G.number_of_nodes()

303 if n < 2:

304 return True

305 e = G.number_of_edges()

306 max_edges = (n * (n - 1)) / 2

307 return e == max_edges

308

309

310def _find_missing_edge(G):

311 """Given a non-complete graph G, returns a missing edge."""

312 nodes = set(G)

313 for u in G:

314 missing = nodes - set(list(G[u].keys()) + [u])

315 if missing:

316 return (u, missing.pop())

317

318

319def _max_cardinality_node(G, choices, wanna_connect):

320 """Returns a the node in choices that has more connections in G

321 to nodes in wanna_connect.

322 """

323 max_number = -1

324 for x in choices:

325 number = len([y for y in G[x] if y in wanna_connect])

326 if number > max_number:

327 max_number = number

328 max_cardinality_node = x

329 return max_cardinality_node

330

331

332def _find_chordality_breaker(G, s=None, treewidth_bound=sys.maxsize):

333 """Given a graph G, starts a max cardinality search

334 (starting from s if s is given and from an arbitrary node otherwise)

335 trying to find a non-chordal cycle.

336

337 If it does find one, it returns (u,v,w) where u,v,w are the three

338 nodes that together with s are involved in the cycle.

339

340 It ignores any self loops.

341 """

342 unnumbered = set(G)

343 if s is None:

344 s = arbitrary_element(G)

345 unnumbered.remove(s)

346 numbered = {s}

347 current_treewidth = -1

348 while unnumbered: # and current_treewidth <= treewidth_bound:

349 v = _max_cardinality_node(G, unnumbered, numbered)

350 unnumbered.remove(v)

351 numbered.add(v)

352 clique_wanna_be = set(G[v]) & numbered

353 sg = G.subgraph(clique_wanna_be)

354 if _is_complete_graph(sg):

355 # The graph seems to be chordal by now. We update the treewidth

356 current_treewidth = max(current_treewidth, len(clique_wanna_be))

357 if current_treewidth > treewidth_bound:

358 raise nx.NetworkXTreewidthBoundExceeded(

359 f"treewidth_bound exceeded: {current_treewidth}"

360 )

361 else:

362 # sg is not a clique,

363 # look for an edge that is not included in sg

364 (u, w) = _find_missing_edge(sg)

365 return (u, v, w)

366 return ()

367

368

369@not_implemented_for("directed")

370@nx._dispatch

371def complete_to_chordal_graph(G):

372 """Return a copy of G completed to a chordal graph

373

374 Adds edges to a copy of G to create a chordal graph. A graph G=(V,E) is

375 called chordal if for each cycle with length bigger than 3, there exist

376 two non-adjacent nodes connected by an edge (called a chord).

377

378 Parameters

379 ----------

380 G : NetworkX graph

381 Undirected graph

382

383 Returns

384 -------

385 H : NetworkX graph

386 The chordal enhancement of G

387 alpha : Dictionary

388 The elimination ordering of nodes of G

389

390 Notes

391 -----

392 There are different approaches to calculate the chordal

393 enhancement of a graph. The algorithm used here is called

394 MCS-M and gives at least minimal (local) triangulation of graph. Note

395 that this triangulation is not necessarily a global minimum.

396

397 https://en.wikipedia.org/wiki/Chordal_graph

398

399 References

400 ----------

401 .. [1] Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004)

402 Maximum Cardinality Search for Computing Minimal Triangulations of

403 Graphs. Algorithmica. 39. 287-298. 10.1007/s00453-004-1084-3.

404

405 Examples

406 --------

407 >>> from networkx.algorithms.chordal import complete_to_chordal_graph

408 >>> G = nx.wheel_graph(10)

409 >>> H, alpha = complete_to_chordal_graph(G)

410 """

411 H = G.copy()

412 alpha = {node: 0 for node in H}

413 if nx.is_chordal(H):

414 return H, alpha

415 chords = set()

416 weight = {node: 0 for node in H.nodes()}

417 unnumbered_nodes = list(H.nodes())

418 for i in range(len(H.nodes()), 0, -1):

419 # get the node in unnumbered_nodes with the maximum weight

420 z = max(unnumbered_nodes, key=lambda node: weight[node])

421 unnumbered_nodes.remove(z)

422 alpha[z] = i

423 update_nodes = []

424 for y in unnumbered_nodes:

425 if G.has_edge(y, z):

426 update_nodes.append(y)

427 else:

428 # y_weight will be bigger than node weights between y and z

429 y_weight = weight[y]

430 lower_nodes = [

431 node for node in unnumbered_nodes if weight[node] < y_weight

432 ]

433 if nx.has_path(H.subgraph(lower_nodes + [z, y]), y, z):

434 update_nodes.append(y)

435 chords.add((z, y))

436 # during calculation of paths the weights should not be updated

437 for node in update_nodes:

438 weight[node] += 1

439 H.add_edges_from(chords)

440 return H, alpha