networkx.algorithms.chordal.chordal_graph_treewidth¶

chordal_graph_treewidth(G)[source]¶

Returns the treewidth of the chordal graph G.

Parameters: G (graph) – A NetworkX graph
Returns: treewidth – The size of the largest clique in the graph minus one.
Return type: int
Raises: NetworkXError – The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. If the input graph is an instance of one of these classes, a NetworkXError is raised. The algorithm can only be applied to chordal graphs. If the input graph is found to be non-chordal, a NetworkXError is raised.

Examples

>>> e = [
...     (1, 2),
...     (1, 3),
...     (2, 3),
...     (2, 4),
...     (3, 4),
...     (3, 5),
...     (3, 6),
...     (4, 5),
...     (4, 6),
...     (5, 6),
...     (7, 8),
... ]
>>> G = nx.Graph(e)
>>> G.add_node(9)
>>> nx.chordal_graph_treewidth(G)
3

References

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