chordal_graph_treewidth

chordal_graph_treewidth(G)

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