Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/treewidth.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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 [1]_ [2]_. | |
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 .. [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 | |
21 | |
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 | |
26 | |
27 .. [3] 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[0][0] | |
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]: | |
205 graph[u].add(v) | |
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()) | |
220 decomp.add_node(first_bag) | |
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 | |
240 nbrs.add(curr_node) | |
241 new_bag = frozenset(nbrs) | |
242 | |
243 # update treewidth | |
244 treewidth = max(treewidth, len(new_bag) - 1) | |
245 | |
246 # add edge to decomposition (implicitly also adds the new node) | |
247 decomp.add_edge(old_bag, new_bag) | |
248 | |
249 return treewidth, decomp |