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