# Tree-decompositions class and implementation of two algorithms for computing
# tree-decompositions:
#
# - Robertson-Seymour and Reed's algorithm for computing approximate
#   tree-decompositions by recursively separating the graph
#
# - An algorithm for computing winning strategies for the robber and cops game
#   and transforming it to a tree decomposition
#
# Written by Martin Grohe, 06-06-2006

Modules
		pickle random

Classes
		__builtin__.object Labelled_tree Tree_decomposition   class Labelled_tree(__builtin__.object)     ########################################################################     Methods defined here: __init__(self, label=None, children=[]) __iter__(self) __str__(self) Data and other attributes defined here: __slots__ = ['label', 'children'] children = <member 'children' of 'Labelled_tree' objects> label = <member 'label' of 'Labelled_tree' objects>   class Tree_decomposition(Labelled_tree)     ########################################################################     Method resolution order: Tree_decomposition Labelled_tree __builtin__.object Methods defined here: __init__(self, bag={}, children=[]) add_to_bag(self, v) check(self, G) Check if decomposition is a correct tree decomposition of the graph G. get_bag(self) remove_from_bag(self, v) Data and other attributes defined here: __dict__ = <dictproxy object> dictionary for instance variables (if defined) __weakref__ = <attribute '__weakref__' of 'Tree_decomposition' objects> list of weak references to the object (if defined) not_conn_ex = 'Bags of vertex not Connected' Methods inherited from Labelled_tree: __iter__(self) __str__(self) Data and other attributes inherited from Labelled_tree: __slots__ = ['label', 'children'] children = <member 'children' of 'Labelled_tree' objects> label = <member 'label' of 'Labelled_tree' objects>

Functions
		RS_rec_tree_dec(G, W, k) Main recursive subroutine of the tree decomposition algorithm. RS_tree_dec(G, k=None) Computes approximate tree-decomposition of G of width at most 4tw(G)+1 by recursively separating the graph. boundary(G, S, C) G graph, S,C sets of vertices. Computes neighbours of C in S. ceil(...) ceil(x)   Return the ceiling of x as a float. This is the smallest integral value >= x. create_game_graph(G, k) Creates game graph for the robber and cops game with k+1 cops on G. game_tree_dec(G, k=None) Computes tree decomposition of width at most k through the robber and cops game. partition(W, low, high) Generates all partitions (X,Y) of W such that low <= |X| <= high. separation(G, W, k) G=(V,E) graph, W subset of W of size 3k+1. Method computes separator S of size at most k+1 such that each component of G-S contains at most 2k elements of W. separator(G, X, Y, k=-1) Return set S that separates X from Y of minimum size. Optional argument k is an upper bound for the size of S; if no separator of size at most k exists then 'None' is returned. sublists(X, k) Generates all sublists of size at most k of list X.