Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/treewidth.py: 21%
94 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Functions for computing treewidth decomposition.
3Treewidth of an undirected graph is a number associated with the graph.
4It can be defined as the size of the largest vertex set (bag) in a tree
5decomposition of the graph minus one.
7`Wikipedia: Treewidth <https://en.wikipedia.org/wiki/Treewidth>`_
9The notions of treewidth and tree decomposition have gained their
10attractiveness partly because many graph and network problems that are
11intractable (e.g., NP-hard) on arbitrary graphs become efficiently
12solvable (e.g., with a linear time algorithm) when the treewidth of the
13input graphs is bounded by a constant [1]_ [2]_.
15There are two different functions for computing a tree decomposition:
16:func:`treewidth_min_degree` and :func:`treewidth_min_fill_in`.
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
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
27.. [3] K. Wang, Z. Lu, and J. Hicks *Treewidth*.
28 https://web.archive.org/web/20210507025929/http://web.eecs.utk.edu/~cphill25/cs594_spring2015_projects/treewidth.pdf
30"""
32import itertools
33import sys
34from heapq import heapify, heappop, heappush
36import networkx as nx
37from networkx.utils import not_implemented_for
39__all__ = ["treewidth_min_degree", "treewidth_min_fill_in"]
42@not_implemented_for("directed")
43@not_implemented_for("multigraph")
44@nx._dispatch
45def treewidth_min_degree(G):
46 """Returns a treewidth decomposition using the Minimum Degree heuristic.
48 The heuristic chooses the nodes according to their degree, i.e., first
49 the node with the lowest degree is chosen, then the graph is updated
50 and the corresponding node is removed. Next, a new node with the lowest
51 degree is chosen, and so on.
53 Parameters
54 ----------
55 G : NetworkX graph
57 Returns
58 -------
59 Treewidth decomposition : (int, Graph) tuple
60 2-tuple with treewidth and the corresponding decomposed tree.
61 """
62 deg_heuristic = MinDegreeHeuristic(G)
63 return treewidth_decomp(G, lambda graph: deg_heuristic.best_node(graph))
66@not_implemented_for("directed")
67@not_implemented_for("multigraph")
68@nx._dispatch
69def treewidth_min_fill_in(G):
70 """Returns a treewidth decomposition using the Minimum Fill-in heuristic.
72 The heuristic chooses a node from the graph, where the number of edges
73 added turning the neighbourhood of the chosen node into clique is as
74 small as possible.
76 Parameters
77 ----------
78 G : NetworkX graph
80 Returns
81 -------
82 Treewidth decomposition : (int, Graph) tuple
83 2-tuple with treewidth and the corresponding decomposed tree.
84 """
85 return treewidth_decomp(G, min_fill_in_heuristic)
88class MinDegreeHeuristic:
89 """Implements the Minimum Degree heuristic.
91 The heuristic chooses the nodes according to their degree
92 (number of neighbours), i.e., first the node with the lowest degree is
93 chosen, then the graph is updated and the corresponding node is
94 removed. Next, a new node with the lowest degree is chosen, and so on.
95 """
97 def __init__(self, graph):
98 self._graph = graph
100 # nodes that have to be updated in the heap before each iteration
101 self._update_nodes = []
103 self._degreeq = [] # a heapq with 3-tuples (degree,unique_id,node)
104 self.count = itertools.count()
106 # build heap with initial degrees
107 for n in graph:
108 self._degreeq.append((len(graph[n]), next(self.count), n))
109 heapify(self._degreeq)
111 def best_node(self, graph):
112 # update nodes in self._update_nodes
113 for n in self._update_nodes:
114 # insert changed degrees into degreeq
115 heappush(self._degreeq, (len(graph[n]), next(self.count), n))
117 # get the next valid (minimum degree) node
118 while self._degreeq:
119 (min_degree, _, elim_node) = heappop(self._degreeq)
120 if elim_node not in graph or len(graph[elim_node]) != min_degree:
121 # outdated entry in degreeq
122 continue
123 elif min_degree == len(graph) - 1:
124 # fully connected: abort condition
125 return None
127 # remember to update nodes in the heap before getting the next node
128 self._update_nodes = graph[elim_node]
129 return elim_node
131 # the heap is empty: abort
132 return None
135def min_fill_in_heuristic(graph):
136 """Implements the Minimum Degree heuristic.
138 Returns the node from the graph, where the number of edges added when
139 turning the neighbourhood of the chosen node into clique is as small as
140 possible. This algorithm chooses the nodes using the Minimum Fill-In
141 heuristic. The running time of the algorithm is :math:`O(V^3)` and it uses
142 additional constant memory."""
144 if len(graph) == 0:
145 return None
147 min_fill_in_node = None
149 min_fill_in = sys.maxsize
151 # sort nodes by degree
152 nodes_by_degree = sorted(graph, key=lambda x: len(graph[x]))
153 min_degree = len(graph[nodes_by_degree[0]])
155 # abort condition (handle complete graph)
156 if min_degree == len(graph) - 1:
157 return None
159 for node in nodes_by_degree:
160 num_fill_in = 0
161 nbrs = graph[node]
162 for nbr in nbrs:
163 # count how many nodes in nbrs current nbr is not connected to
164 # subtract 1 for the node itself
165 num_fill_in += len(nbrs - graph[nbr]) - 1
166 if num_fill_in >= 2 * min_fill_in:
167 break
169 num_fill_in /= 2 # divide by 2 because of double counting
171 if num_fill_in < min_fill_in: # update min-fill-in node
172 if num_fill_in == 0:
173 return node
174 min_fill_in = num_fill_in
175 min_fill_in_node = node
177 return min_fill_in_node
180@nx._dispatch
181def treewidth_decomp(G, heuristic=min_fill_in_heuristic):
182 """Returns a treewidth decomposition using the passed heuristic.
184 Parameters
185 ----------
186 G : NetworkX graph
187 heuristic : heuristic function
189 Returns
190 -------
191 Treewidth decomposition : (int, Graph) tuple
192 2-tuple with treewidth and the corresponding decomposed tree.
193 """
195 # make dict-of-sets structure
196 graph = {n: set(G[n]) - {n} for n in G}
198 # stack containing nodes and neighbors in the order from the heuristic
199 node_stack = []
201 # get first node from heuristic
202 elim_node = heuristic(graph)
203 while elim_node is not None:
204 # connect all neighbours with each other
205 nbrs = graph[elim_node]
206 for u, v in itertools.permutations(nbrs, 2):
207 if v not in graph[u]:
208 graph[u].add(v)
210 # push node and its current neighbors on stack
211 node_stack.append((elim_node, nbrs))
213 # remove node from graph
214 for u in graph[elim_node]:
215 graph[u].remove(elim_node)
217 del graph[elim_node]
218 elim_node = heuristic(graph)
220 # the abort condition is met; put all remaining nodes into one bag
221 decomp = nx.Graph()
222 first_bag = frozenset(graph.keys())
223 decomp.add_node(first_bag)
225 treewidth = len(first_bag) - 1
227 while node_stack:
228 # get node and its neighbors from the stack
229 (curr_node, nbrs) = node_stack.pop()
231 # find a bag all neighbors are in
232 old_bag = None
233 for bag in decomp.nodes:
234 if nbrs <= bag:
235 old_bag = bag
236 break
238 if old_bag is None:
239 # no old_bag was found: just connect to the first_bag
240 old_bag = first_bag
242 # create new node for decomposition
243 nbrs.add(curr_node)
244 new_bag = frozenset(nbrs)
246 # update treewidth
247 treewidth = max(treewidth, len(new_bag) - 1)
249 # add edge to decomposition (implicitly also adds the new node)
250 decomp.add_edge(old_bag, new_bag)
252 return treewidth, decomp