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

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/approximation/treewidth.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,249 @@
+"""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] Hans 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"]
+
+
+@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))
+
+
+@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]) - {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