complete_to_chordal_graph#
- complete_to_chordal_graph(G)[source]#
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).
- Parameters:
- GNetworkX graph
Undirected graph
- Returns:
- HNetworkX graph
The chordal enhancement of G
- alphaDictionary
The elimination ordering of nodes of G
Notes
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.
https://en.wikipedia.org/wiki/Chordal_graph
References
[1]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.
Examples
>>> from networkx.algorithms.chordal import complete_to_chordal_graph >>> G = nx.wheel_graph(10) >>> H, alpha = complete_to_chordal_graph(G)