1"""Functions for computing treewidth decomposition.
2
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.
6
7`Wikipedia: Treewidth <https://en.wikipedia.org/wiki/Treewidth>`_
8
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]_.
14
15There 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      https://web.archive.org/web/20210507025929/http://web.eecs.utk.edu/~cphill25/cs594_spring2015_projects/treewidth.pdf
29
30"""
31
32import sys
33
34import networkx as nx
35from networkx.utils import not_implemented_for
36from heapq import heappush, heappop, heapify
37import itertools
38
39__all__ = ["treewidth_min_degree", "treewidth_min_fill_in"]
40
41
42@not_implemented_for("directed")
43@not_implemented_for("multigraph")
44def 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")
67def 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
86class 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
132def 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
178def 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
250