## Mercurial > repos > shellac > sam_consensus_v3

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

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"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 |