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, aNetworkXError
is raised. The algorithm can only be applied to chordal graphs. If the input graph is found to be non-chordal, aNetworkXError
is raised.Examples
>>> import networkx as nx >>> 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