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

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