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. treewidth – The width of the tree decomposition induced by order. 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