### annotate env/lib/python3.9/site-packages/networkx/algorithms/approximation/treewidth.py @ 0:4f3585e2f14bdraftdefaulttip

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