Return a copy of G completed to a chordal graph
Adds edges to a copy of G to create a chordal graph. A graph G=(V,E) is called chordal if for each cycle with length bigger than 3, there exist two non-adjacent nodes connected by an edge (called a chord).
- GNetworkX graph
- HNetworkX graph
The chordal enhancement of G
The elimination ordering of nodes of G
There are different approaches to calculate the chordal enhancement of a graph. The algorithm used here is called MCS-M and gives at least minimal (local) triangulation of graph. Note that this triangulation is not necessarily a global minimum.
Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004) Maximum Cardinality Search for Computing Minimal Triangulations of Graphs. Algorithmica. 39. 287-298. 10.1007/s00453-004-1084-3.
>>> from networkx.algorithms.chordal import complete_to_chordal_graph >>> G = nx.wheel_graph(10) >>> H, alpha = complete_to_chordal_graph(G)