Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/tests/test_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 import networkx as nx | |
2 from networkx.algorithms.approximation import treewidth_min_degree | |
3 from networkx.algorithms.approximation import treewidth_min_fill_in | |
4 from networkx.algorithms.approximation.treewidth import min_fill_in_heuristic | |
5 from networkx.algorithms.approximation.treewidth import MinDegreeHeuristic | |
6 import itertools | |
7 | |
8 | |
9 def is_tree_decomp(graph, decomp): | |
10 """Check if the given tree decomposition is valid.""" | |
11 for x in graph.nodes(): | |
12 appear_once = False | |
13 for bag in decomp.nodes(): | |
14 if x in bag: | |
15 appear_once = True | |
16 break | |
17 assert appear_once | |
18 | |
19 # Check if each connected pair of nodes are at least once together in a bag | |
20 for (x, y) in graph.edges(): | |
21 appear_together = False | |
22 for bag in decomp.nodes(): | |
23 if x in bag and y in bag: | |
24 appear_together = True | |
25 break | |
26 assert appear_together | |
27 | |
28 # Check if the nodes associated with vertex v form a connected subset of T | |
29 for v in graph.nodes(): | |
30 subset = [] | |
31 for bag in decomp.nodes(): | |
32 if v in bag: | |
33 subset.append(bag) | |
34 sub_graph = decomp.subgraph(subset) | |
35 assert nx.is_connected(sub_graph) | |
36 | |
37 | |
38 class TestTreewidthMinDegree: | |
39 """Unit tests for the min_degree function""" | |
40 | |
41 @classmethod | |
42 def setup_class(cls): | |
43 """Setup for different kinds of trees""" | |
44 cls.complete = nx.Graph() | |
45 cls.complete.add_edge(1, 2) | |
46 cls.complete.add_edge(2, 3) | |
47 cls.complete.add_edge(1, 3) | |
48 | |
49 cls.small_tree = nx.Graph() | |
50 cls.small_tree.add_edge(1, 3) | |
51 cls.small_tree.add_edge(4, 3) | |
52 cls.small_tree.add_edge(2, 3) | |
53 cls.small_tree.add_edge(3, 5) | |
54 cls.small_tree.add_edge(5, 6) | |
55 cls.small_tree.add_edge(5, 7) | |
56 cls.small_tree.add_edge(6, 7) | |
57 | |
58 cls.deterministic_graph = nx.Graph() | |
59 cls.deterministic_graph.add_edge(0, 1) # deg(0) = 1 | |
60 | |
61 cls.deterministic_graph.add_edge(1, 2) # deg(1) = 2 | |
62 | |
63 cls.deterministic_graph.add_edge(2, 3) | |
64 cls.deterministic_graph.add_edge(2, 4) # deg(2) = 3 | |
65 | |
66 cls.deterministic_graph.add_edge(3, 4) | |
67 cls.deterministic_graph.add_edge(3, 5) | |
68 cls.deterministic_graph.add_edge(3, 6) # deg(3) = 4 | |
69 | |
70 cls.deterministic_graph.add_edge(4, 5) | |
71 cls.deterministic_graph.add_edge(4, 6) | |
72 cls.deterministic_graph.add_edge(4, 7) # deg(4) = 5 | |
73 | |
74 cls.deterministic_graph.add_edge(5, 6) | |
75 cls.deterministic_graph.add_edge(5, 7) | |
76 cls.deterministic_graph.add_edge(5, 8) | |
77 cls.deterministic_graph.add_edge(5, 9) # deg(5) = 6 | |
78 | |
79 cls.deterministic_graph.add_edge(6, 7) | |
80 cls.deterministic_graph.add_edge(6, 8) | |
81 cls.deterministic_graph.add_edge(6, 9) # deg(6) = 6 | |
82 | |
83 cls.deterministic_graph.add_edge(7, 8) | |
84 cls.deterministic_graph.add_edge(7, 9) # deg(7) = 5 | |
85 | |
86 cls.deterministic_graph.add_edge(8, 9) # deg(8) = 4 | |
87 | |
88 def test_petersen_graph(self): | |
89 """Test Petersen graph tree decomposition result""" | |
90 G = nx.petersen_graph() | |
91 _, decomp = treewidth_min_degree(G) | |
92 is_tree_decomp(G, decomp) | |
93 | |
94 def test_small_tree_treewidth(self): | |
95 """Test small tree | |
96 | |
97 Test if the computed treewidth of the known self.small_tree is 2. | |
98 As we know which value we can expect from our heuristic, values other | |
99 than two are regressions | |
100 """ | |
101 G = self.small_tree | |
102 # the order of removal should be [1,2,4]3[5,6,7] | |
103 # (with [] denoting any order of the containing nodes) | |
104 # resulting in treewidth 2 for the heuristic | |
105 treewidth, _ = treewidth_min_fill_in(G) | |
106 assert treewidth == 2 | |
107 | |
108 def test_heuristic_abort(self): | |
109 """Test heuristic abort condition for fully connected graph""" | |
110 graph = {} | |
111 for u in self.complete: | |
112 graph[u] = set() | |
113 for v in self.complete[u]: | |
114 if u != v: # ignore self-loop | |
115 graph[u].add(v) | |
116 | |
117 deg_heuristic = MinDegreeHeuristic(graph) | |
118 node = deg_heuristic.best_node(graph) | |
119 if node is None: | |
120 pass | |
121 else: | |
122 assert False | |
123 | |
124 def test_empty_graph(self): | |
125 """Test empty graph""" | |
126 G = nx.Graph() | |
127 _, _ = treewidth_min_degree(G) | |
128 | |
129 def test_two_component_graph(self): | |
130 """Test empty graph""" | |
131 G = nx.Graph() | |
132 G.add_node(1) | |
133 G.add_node(2) | |
134 treewidth, _ = treewidth_min_degree(G) | |
135 assert treewidth == 0 | |
136 | |
137 def test_heuristic_first_steps(self): | |
138 """Test first steps of min_degree heuristic""" | |
139 graph = { | |
140 n: set(self.deterministic_graph[n]) - {n} for n in self.deterministic_graph | |
141 } | |
142 deg_heuristic = MinDegreeHeuristic(graph) | |
143 elim_node = deg_heuristic.best_node(graph) | |
144 print(f"Graph {graph}:") | |
145 steps = [] | |
146 | |
147 while elim_node is not None: | |
148 print(f"Removing {elim_node}:") | |
149 steps.append(elim_node) | |
150 nbrs = graph[elim_node] | |
151 | |
152 for u, v in itertools.permutations(nbrs, 2): | |
153 if v not in graph[u]: | |
154 graph[u].add(v) | |
155 | |
156 for u in graph: | |
157 if elim_node in graph[u]: | |
158 graph[u].remove(elim_node) | |
159 | |
160 del graph[elim_node] | |
161 print(f"Graph {graph}:") | |
162 elim_node = deg_heuristic.best_node(graph) | |
163 | |
164 # check only the first 5 elements for equality | |
165 assert steps[:5] == [0, 1, 2, 3, 4] | |
166 | |
167 | |
168 class TestTreewidthMinFillIn: | |
169 """Unit tests for the treewidth_min_fill_in function.""" | |
170 | |
171 @classmethod | |
172 def setup_class(cls): | |
173 """Setup for different kinds of trees""" | |
174 cls.complete = nx.Graph() | |
175 cls.complete.add_edge(1, 2) | |
176 cls.complete.add_edge(2, 3) | |
177 cls.complete.add_edge(1, 3) | |
178 | |
179 cls.small_tree = nx.Graph() | |
180 cls.small_tree.add_edge(1, 2) | |
181 cls.small_tree.add_edge(2, 3) | |
182 cls.small_tree.add_edge(3, 4) | |
183 cls.small_tree.add_edge(1, 4) | |
184 cls.small_tree.add_edge(2, 4) | |
185 cls.small_tree.add_edge(4, 5) | |
186 cls.small_tree.add_edge(5, 6) | |
187 cls.small_tree.add_edge(5, 7) | |
188 cls.small_tree.add_edge(6, 7) | |
189 | |
190 cls.deterministic_graph = nx.Graph() | |
191 cls.deterministic_graph.add_edge(1, 2) | |
192 cls.deterministic_graph.add_edge(1, 3) | |
193 cls.deterministic_graph.add_edge(3, 4) | |
194 cls.deterministic_graph.add_edge(2, 4) | |
195 cls.deterministic_graph.add_edge(3, 5) | |
196 cls.deterministic_graph.add_edge(4, 5) | |
197 cls.deterministic_graph.add_edge(3, 6) | |
198 cls.deterministic_graph.add_edge(5, 6) | |
199 | |
200 def test_petersen_graph(self): | |
201 """Test Petersen graph tree decomposition result""" | |
202 G = nx.petersen_graph() | |
203 _, decomp = treewidth_min_fill_in(G) | |
204 is_tree_decomp(G, decomp) | |
205 | |
206 def test_small_tree_treewidth(self): | |
207 """Test if the computed treewidth of the known self.small_tree is 2""" | |
208 G = self.small_tree | |
209 # the order of removal should be [1,2,4]3[5,6,7] | |
210 # (with [] denoting any order of the containing nodes) | |
211 # resulting in treewidth 2 for the heuristic | |
212 treewidth, _ = treewidth_min_fill_in(G) | |
213 assert treewidth == 2 | |
214 | |
215 def test_heuristic_abort(self): | |
216 """Test if min_fill_in returns None for fully connected graph""" | |
217 graph = {} | |
218 for u in self.complete: | |
219 graph[u] = set() | |
220 for v in self.complete[u]: | |
221 if u != v: # ignore self-loop | |
222 graph[u].add(v) | |
223 next_node = min_fill_in_heuristic(graph) | |
224 if next_node is None: | |
225 pass | |
226 else: | |
227 assert False | |
228 | |
229 def test_empty_graph(self): | |
230 """Test empty graph""" | |
231 G = nx.Graph() | |
232 _, _ = treewidth_min_fill_in(G) | |
233 | |
234 def test_two_component_graph(self): | |
235 """Test empty graph""" | |
236 G = nx.Graph() | |
237 G.add_node(1) | |
238 G.add_node(2) | |
239 treewidth, _ = treewidth_min_fill_in(G) | |
240 assert treewidth == 0 | |
241 | |
242 def test_heuristic_first_steps(self): | |
243 """Test first steps of min_fill_in heuristic""" | |
244 graph = { | |
245 n: set(self.deterministic_graph[n]) - {n} for n in self.deterministic_graph | |
246 } | |
247 print(f"Graph {graph}:") | |
248 elim_node = min_fill_in_heuristic(graph) | |
249 steps = [] | |
250 | |
251 while elim_node is not None: | |
252 print(f"Removing {elim_node}:") | |
253 steps.append(elim_node) | |
254 nbrs = graph[elim_node] | |
255 | |
256 for u, v in itertools.permutations(nbrs, 2): | |
257 if v not in graph[u]: | |
258 graph[u].add(v) | |
259 | |
260 for u in graph: | |
261 if elim_node in graph[u]: | |
262 graph[u].remove(elim_node) | |
263 | |
264 del graph[elim_node] | |
265 print(f"Graph {graph}:") | |
266 elim_node = min_fill_in_heuristic(graph) | |
267 | |
268 # check only the first 2 elements for equality | |
269 assert steps[:2] == [6, 5] |