Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for computing treewidth decomposition.
3Treewidth of an undirected graph is a number associated with the graph.
4It can be defined as the size of the largest vertex set (bag) in a tree
5decomposition of the graph minus one.
7`Wikipedia: Treewidth <https://en.wikipedia.org/wiki/Treewidth>`_
9The notions of treewidth and tree decomposition have gained their
10attractiveness partly because many graph and network problems that are
11intractable (e.g., NP-hard) on arbitrary graphs become efficiently
12solvable (e.g., with a linear time algorithm) when the treewidth of the
13input graphs is bounded by a constant [1]_ [2]_.
15There are two different functions for computing a tree decomposition:
16:func:`treewidth_min_degree` and :func:`treewidth_min_fill_in`.
18.. [1] Hans L. Bodlaender and Arie M. C. A. Koster. 2010. "Treewidth
19 computations I.Upper bounds". Inf. Comput. 208, 3 (March 2010),259-275.
20 http://dx.doi.org/10.1016/j.ic.2009.03.008
22.. [2] Hans L. Bodlaender. "Discovering Treewidth". Institute of Information
23 and Computing Sciences, Utrecht University.
24 Technical Report UU-CS-2005-018.
25 http://www.cs.uu.nl
27.. [3] K. Wang, Z. Lu, and J. Hicks *Treewidth*.
28 https://web.archive.org/web/20210507025929/http://web.eecs.utk.edu/~cphill25/cs594_spring2015_projects/treewidth.pdf
30"""
32import itertools
33import sys
34from heapq import heapify, heappop, heappush
36import networkx as nx
37from networkx.utils import not_implemented_for
39__all__ = ["treewidth_min_degree", "treewidth_min_fill_in"]
42@not_implemented_for("directed")
43@not_implemented_for("multigraph")
44@nx._dispatchable(returns_graph=True)
45def treewidth_min_degree(G):
46 """Returns a treewidth decomposition using the Minimum Degree heuristic.
48 The heuristic chooses the nodes according to their degree, i.e., first
49 the node with the lowest degree is chosen, then the graph is updated
50 and the corresponding node is removed. Next, a new node with the lowest
51 degree is chosen, and so on.
53 Parameters
54 ----------
55 G : NetworkX graph
57 Returns
58 -------
59 Treewidth decomposition : (int, Graph) tuple
60 2-tuple with treewidth and the corresponding decomposed tree.
61 """
62 deg_heuristic = MinDegreeHeuristic(G)
63 return treewidth_decomp(G, lambda graph: deg_heuristic.best_node(graph))
66@not_implemented_for("directed")
67@not_implemented_for("multigraph")
68@nx._dispatchable(returns_graph=True)
69def treewidth_min_fill_in(G):
70 """Returns a treewidth decomposition using the Minimum Fill-in heuristic.
72 The heuristic chooses a node from the graph, where the number of edges
73 added turning the neighborhood of the chosen node into clique is as
74 small as possible.
76 Parameters
77 ----------
78 G : NetworkX graph
80 Returns
81 -------
82 Treewidth decomposition : (int, Graph) tuple
83 2-tuple with treewidth and the corresponding decomposed tree.
84 """
85 return treewidth_decomp(G, min_fill_in_heuristic)
88class MinDegreeHeuristic:
89 """Implements the Minimum Degree heuristic.
91 The heuristic chooses the nodes according to their degree
92 (number of neighbors), i.e., first the node with the lowest degree is
93 chosen, then the graph is updated and the corresponding node is
94 removed. Next, a new node with the lowest degree is chosen, and so on.
95 """
97 def __init__(self, graph):
98 self._graph = graph
100 # nodes that have to be updated in the heap before each iteration
101 self._update_nodes = []
103 self._degreeq = [] # a heapq with 3-tuples (degree,unique_id,node)
104 self.count = itertools.count()
106 # build heap with initial degrees
107 for n in graph:
108 self._degreeq.append((len(graph[n]), next(self.count), n))
109 heapify(self._degreeq)
111 def best_node(self, graph):
112 # update nodes in self._update_nodes
113 for n in self._update_nodes:
114 # insert changed degrees into degreeq
115 heappush(self._degreeq, (len(graph[n]), next(self.count), n))
117 # get the next valid (minimum degree) node
118 while self._degreeq:
119 (min_degree, _, elim_node) = heappop(self._degreeq)
120 if elim_node not in graph or len(graph[elim_node]) != min_degree:
121 # outdated entry in degreeq
122 continue
123 elif min_degree == len(graph) - 1:
124 # fully connected: abort condition
125 return None
127 # remember to update nodes in the heap before getting the next node
128 self._update_nodes = graph[elim_node]
129 return elim_node
131 # the heap is empty: abort
132 return None
135def min_fill_in_heuristic(graph_dict):
136 """Implements the Minimum Degree heuristic.
138 graph_dict: dict keyed by node to sets of neighbors (no self-loops)
140 Returns the node from the graph, where the number of edges added when
141 turning the neighborhood of the chosen node into clique is as small as
142 possible. This algorithm chooses the nodes using the Minimum Fill-In
143 heuristic. The running time of the algorithm is :math:`O(V^3)` and it uses
144 additional constant memory.
145 """
147 if len(graph_dict) == 0:
148 return None
150 min_fill_in_node = None
152 min_fill_in = sys.maxsize
154 # sort nodes by degree
155 nodes_by_degree = sorted(graph_dict, key=lambda x: len(graph_dict[x]))
156 min_degree = len(graph_dict[nodes_by_degree[0]])
158 # abort condition (handle complete graph)
159 if min_degree == len(graph_dict) - 1:
160 return None
162 for node in nodes_by_degree:
163 num_fill_in = 0
164 nbrs = graph_dict[node]
165 for nbr in nbrs:
166 # count how many nodes in nbrs current nbr is not connected to
167 # subtract 1 for the node itself
168 num_fill_in += len(nbrs - graph_dict[nbr]) - 1
169 if num_fill_in >= 2 * min_fill_in:
170 break
172 num_fill_in /= 2 # divide by 2 because of double counting
174 if num_fill_in < min_fill_in: # update min-fill-in node
175 if num_fill_in == 0:
176 return node
177 min_fill_in = num_fill_in
178 min_fill_in_node = node
180 return min_fill_in_node
183@nx._dispatchable(returns_graph=True)
184def treewidth_decomp(G, heuristic=min_fill_in_heuristic):
185 """Returns a treewidth decomposition using the passed heuristic.
187 Parameters
188 ----------
189 G : NetworkX graph
190 heuristic : heuristic function
192 Returns
193 -------
194 Treewidth decomposition : (int, Graph) tuple
195 2-tuple with treewidth and the corresponding decomposed tree.
196 """
198 # make dict-of-sets structure
199 graph_dict = {n: set(G[n]) - {n} for n in G}
201 # stack containing nodes and neighbors in the order from the heuristic
202 node_stack = []
204 # get first node from heuristic
205 elim_node = heuristic(graph_dict)
206 while elim_node is not None:
207 # connect all neighbors with each other
208 nbrs = graph_dict[elim_node]
209 for u, v in itertools.permutations(nbrs, 2):
210 if v not in graph_dict[u]:
211 graph_dict[u].add(v)
213 # push node and its current neighbors on stack
214 node_stack.append((elim_node, nbrs))
216 # remove node from graph_dict
217 for u in graph_dict[elim_node]:
218 graph_dict[u].remove(elim_node)
220 del graph_dict[elim_node]
221 elim_node = heuristic(graph_dict)
223 # the abort condition is met; put all remaining nodes into one bag
224 decomp = nx.Graph()
225 first_bag = frozenset(graph_dict.keys())
226 decomp.add_node(first_bag)
228 treewidth = len(first_bag) - 1
230 while node_stack:
231 # get node and its neighbors from the stack
232 (curr_node, nbrs) = node_stack.pop()
234 # find a bag all neighbors are in
235 old_bag = None
236 for bag in decomp.nodes:
237 if nbrs <= bag:
238 old_bag = bag
239 break
241 if old_bag is None:
242 # no old_bag was found: just connect to the first_bag
243 old_bag = first_bag
245 # create new node for decomposition
246 nbrs.add(curr_node)
247 new_bag = frozenset(nbrs)
249 # update treewidth
250 treewidth = max(treewidth, len(new_bag) - 1)
252 # add edge to decomposition (implicitly also adds the new node)
253 decomp.add_edge(old_bag, new_bag)
255 return treewidth, decomp