Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.algorithms.approximation.treewidth

# -*- coding: utf-8 -*-
"""Functions for computing treewidth decomposition.

Treewidth of an undirected graph is a number associated with the graph.
It can be defined as the size of the largest vertex set (bag) in a tree
decomposition of the graph minus one.

`Wikipedia: Treewidth <https://en.wikipedia.org/wiki/Treewidth>`_

The notions of treewidth and tree decomposition have gained their
attractiveness partly because many graph and network problems that are
intractable (e.g., NP-hard) on arbitrary graphs become efficiently
solvable (e.g., with a linear time algorithm) when the treewidth of the
input graphs is bounded by a constant [1]_ [2]_.

There are two different functions for computing a tree decomposition:
:func:`treewidth_min_degree` and :func:`treewidth_min_fill_in`.

.. [1] Hans L. Bodlaender and Arie M. C. A. Koster. 2010. "Treewidth
      computations I.Upper bounds". Inf. Comput. 208, 3 (March 2010),259-275.
      http://dx.doi.org/10.1016/j.ic.2009.03.008

.. [2] Hand L. Bodlaender. "Discovering Treewidth". Institute of Information
      and Computing Sciences, Utrecht University.
      Technical Report UU-CS-2005-018.
      http://www.cs.uu.nl

.. [3] K. Wang, Z. Lu, and J. Hicks *Treewidth*.
      http://web.eecs.utk.edu/~cphillip/cs594_spring2015_projects/treewidth.pdf

"""

import sys

import networkx as nx
from networkx.utils import not_implemented_for
from heapq import heappush, heappop, heapify
import itertools

__all__ = ["treewidth_min_degree", "treewidth_min_fill_in"]


[docs]@not_implemented_for('directed') @not_implemented_for('multigraph') def treewidth_min_degree(G): """ Returns a treewidth decomposition using the Minimum Degree heuristic. The heuristic chooses the nodes according to their degree, i.e., first the node with the lowest degree is chosen, then the graph is updated and the corresponding node is removed. Next, a new node with the lowest degree is chosen, and so on. Parameters ---------- G : NetworkX graph Returns ------- Treewidth decomposition : (int, Graph) tuple 2-tuple with treewidth and the corresponding decomposed tree. """ deg_heuristic = MinDegreeHeuristic(G) return treewidth_decomp(G, lambda graph: deg_heuristic.best_node(graph))
[docs]@not_implemented_for('directed') @not_implemented_for('multigraph') def treewidth_min_fill_in(G): """ Returns a treewidth decomposition using the Minimum Fill-in heuristic. The heuristic chooses a node from the graph, where the number of edges added turning the neighbourhood of the chosen node into clique is as small as possible. Parameters ---------- G : NetworkX graph Returns ------- Treewidth decomposition : (int, Graph) tuple 2-tuple with treewidth and the corresponding decomposed tree. """ return treewidth_decomp(G, min_fill_in_heuristic)
class MinDegreeHeuristic: """ Implements the Minimum Degree heuristic. The heuristic chooses the nodes according to their degree (number of neighbours), i.e., first the node with the lowest degree is chosen, then the graph is updated and the corresponding node is removed. Next, a new node with the lowest degree is chosen, and so on. """ def __init__(self, graph): self._graph = graph # nodes that have to be updated in the heap before each iteration self._update_nodes = [] self._degreeq = [] # a heapq with 2-tuples (degree,node) # build heap with initial degrees for n in graph: self._degreeq.append((len(graph[n]), n)) heapify(self._degreeq) def best_node(self, graph): # update nodes in self._update_nodes for n in self._update_nodes: # insert changed degrees into degreeq heappush(self._degreeq, (len(graph[n]), n)) # get the next valid (minimum degree) node while self._degreeq: (min_degree, elim_node) = heappop(self._degreeq) if elim_node not in graph or len(graph[elim_node]) != min_degree: # outdated entry in degreeq continue elif min_degree == len(graph) - 1: # fully connected: abort condition return None # remember to update nodes in the heap before getting the next node self._update_nodes = graph[elim_node] return elim_node # the heap is empty: abort return None def min_fill_in_heuristic(graph): """ Implements the Minimum Degree heuristic. Returns the node from the graph, where the number of edges added when turning the neighbourhood of the chosen node into clique is as small as possible. This algorithm chooses the nodes using the Minimum Fill-In heuristic. The running time of the algorithm is :math:`O(V^3)` and it uses additional constant memory.""" if len(graph) == 0: return None min_fill_in_node = None min_fill_in = sys.maxsize # create sorted list of (degree, node) degree_list = [(len(graph[node]), node) for node in graph] degree_list.sort() # abort condition min_degree = degree_list[0][0] if min_degree == len(graph) - 1: return None for (_, node) in degree_list: num_fill_in = 0 nbrs = graph[node] for nbr in nbrs: # count how many nodes in nbrs current nbr is not connected to # subtract 1 for the node itself num_fill_in += len(nbrs - graph[nbr]) - 1 if num_fill_in >= 2 * min_fill_in: break num_fill_in /= 2 # divide by 2 because of double counting if num_fill_in < min_fill_in: # update min-fill-in node if num_fill_in == 0: return node min_fill_in = num_fill_in min_fill_in_node = node return min_fill_in_node def treewidth_decomp(G, heuristic=min_fill_in_heuristic): """ Returns a treewidth decomposition using the passed heuristic. Parameters ---------- G : NetworkX graph heuristic : heuristic function Returns ------- Treewidth decomposition : (int, Graph) tuple 2-tuple with treewidth and the corresponding decomposed tree. """ # make dict-of-sets structure graph = {n: set(G[n]) - set([n]) for n in G} # stack containing nodes and neighbors in the order from the heuristic node_stack = [] # get first node from heuristic elim_node = heuristic(graph) while elim_node is not None: # connect all neighbours with each other nbrs = graph[elim_node] for u, v in itertools.permutations(nbrs, 2): if v not in graph[u]: graph[u].add(v) # push node and its current neighbors on stack node_stack.append((elim_node, nbrs)) # remove node from graph for u in graph[elim_node]: graph[u].remove(elim_node) del graph[elim_node] elim_node = heuristic(graph) # the abort condition is met; put all remaining nodes into one bag decomp = nx.Graph() first_bag = frozenset(graph.keys()) decomp.add_node(first_bag) treewidth = len(first_bag) - 1 while node_stack: # get node and its neighbors from the stack (curr_node, nbrs) = node_stack.pop() # find a bag all neighbors are in old_bag = None for bag in decomp.nodes: if nbrs <= bag: old_bag = bag break if old_bag is None: # no old_bag was found: just connect to the first_bag old_bag = first_bag # create new node for decomposition nbrs.add(curr_node) new_bag = frozenset(nbrs) # update treewidth treewidth = max(treewidth, len(new_bag) - 1) # add edge to decomposition (implicitly also adds the new node) decomp.add_edge(old_bag, new_bag) return treewidth, decomp