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)