CODEWITHSUNDEEP
pythonnetworkxdecomposition
Shaharg
Shaharg

Reputation: 1029

Create a nice tree decomposition in python

I know that networkx has a function for creating a tree decomposition:

import networkx as nx
from networkx.algorithms.approximation import treewidth_min_degree

G = createGraph() # an arbitrary function returning a networkx graph
width,decomposition = treewidth_min_degree(G)

Is there a function transforming this tree into a nice tree decomposition.

Edit: A "nice" tree decomposition is a rooted binary tree with four different types of nodes:

  1. Leaf nodes have no children and bag size
  2. Introduce nodes have one child. The child has the same vertices as the parent with one deleted.
  3. Forget nodes have one child. The child has the same vertices as the parent with one added.
  4. Join nodes have two children, End edit.

I know there is a linear algorithm doing this, but I wonder if this is already implemented somewhere.

Upvotes: 1

Views: 535

Answers (0)

Related Questions