networkx.algorithms.chordal.chordal_graph_treewidth

chordal_graph_treewidth(G)[source]

Returns the treewidth of the chordal graph G.

Parameters
Ggraph

A NetworkX graph

Returns
treewidthint

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

Raises
NetworkXError

The algorithm does not support DiGraph, MultiGraph and MultiDiGraph. The algorithm can only be applied to chordal graphs. If the input graph is found to be non-chordal, a NetworkXError is raised.

References

1

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

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