chordal_graph_treewidth¶

chordal_graph_treewidth(G)[source]¶

Returns the treewidth of the chordal graph G.

Parameters:	G : graph A NetworkX graph
Returns:	treewidth : int The size of the largest clique in the graph minus one.
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.

References

[R195]

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

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