dwave_networkx.algorithms.elimination_ordering.elimination_order_width¶

elimination_order_width(G, order)[source]¶

Calculates the width of the tree decomposition induced by a variable elimination order.

Parameters:	G (NetworkX graph) – The graph on which to compute the width of the tree decomposition. order (list) – The elimination order. Must be a list of all of the variables in G.
Returns:	treewidth – The width of the tree decomposition induced by order.
Return type:	int

Examples

This example computes the width of the tree decomposition for the \(K_4\) complete graph induced by an elimination order found through the min-width heuristic.

>>> K_4 = nx.complete_graph(4)
>>> tw, order = dnx.min_width_heuristic(K_4)
>>> print(tw)
3
>>> dnx.elimination_order_width(K_4, order)
3