BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType > Class Template Reference

#include <BALL/DATATYPE/GRAPH/treeWidth.h>

Public Types
typedef TreeWidth < OriginalGraphType > ::TreeDecomposition	TreeDecomposition
typedef TreeWidth < OriginalGraphType > ::TreeDecompositionBag	TreeDecompositionBag
typedef TreeWidth < OriginalGraphType > ::TreeDecompositionGraph	TreeDecompositionGraph
typedef TreeWidth < OriginalGraphType > ::OriginalVertexType	OriginalVertexType
typedef std::set < OriginalVertexType >	TreeDecompositionContent

Public Member Functions
boost::shared_ptr < TreeDecomposition >	operator() (UndirectedGraph const &graph, EliminationOrder const &permutation)
boost::shared_ptr < TreeDecomposition >	makeNice (boost::shared_ptr< TreeDecompositionGraph > &nice_tree)
TreeDecompositionBag	operator() (TreeDecompositionBag n, typename std::vector< TreeDecompositionBag >::iterator c_i, typename std::vector< TreeDecompositionBag >::iterator c_end)

Protected Member Functions
TreeDecompositionBag	buildRoot_ (TreeDecompositionBag child)
TreeDecompositionBag	buildLeaf_ (TreeDecompositionBag child)
TreeDecompositionBag	buildJoin_ (TreeDecompositionBag node, TreeDecompositionBag left, TreeDecompositionBag right, bool do_forget)
TreeDecompositionBag	buildSingle_ (TreeDecompositionBag node, int node_type, TreeDecompositionBag child)
TreeDecompositionBag	buildLinkage_ (TreeDecompositionBag node, TreeDecompositionBag child)
TreeDecompositionBag	linkWithIntroduceNodes_ (TreeDecompositionContent parent_set, TreeDecompositionBag child)
TreeDecompositionBag	linkWithForgetNodes_ (TreeDecompositionContent parent_set, TreeDecompositionBag child)
TreeDecompositionBag	branch_ (TreeDecompositionBag node, int node_type, typename std::vector< TreeDecompositionBag >::iterator begin, typename std::vector< TreeDecompositionBag >::iterator end)

Protected Attributes
boost::shared_ptr < TreeDecomposition >	tree_
boost::shared_ptr < TreeDecompositionGraph >	tree_graph_
boost::shared_ptr < TreeDecompositionGraph >	nice_tree_
TreeDecompositionBag	root_

Detailed Description

template<class EditableGraph>
template<class OriginalGraphType>
class BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >

Definition at line 448 of file treeWidth.h.

Member Typedef Documentation

template<class EditableGraph >

template<class OriginalGraphType >

typedef TreeWidth<OriginalGraphType>::OriginalVertexType BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::OriginalVertexType

Definition at line 455 of file treeWidth.h.

template<class EditableGraph >

template<class OriginalGraphType >

typedef TreeWidth<OriginalGraphType>::TreeDecomposition BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::TreeDecomposition

Definition at line 451 of file treeWidth.h.

template<class EditableGraph >

template<class OriginalGraphType >

typedef TreeWidth<OriginalGraphType>::TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::TreeDecompositionBag

Definition at line 452 of file treeWidth.h.

template<class EditableGraph >

template<class OriginalGraphType >

typedef std::set<OriginalVertexType> BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::TreeDecompositionContent

Definition at line 457 of file treeWidth.h.

template<class EditableGraph >

template<class OriginalGraphType >

typedef TreeWidth<OriginalGraphType>::TreeDecompositionGraph BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::TreeDecompositionGraph

Definition at line 453 of file treeWidth.h.

Member Function Documentation

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::branch_ ( TreeDecompositionBag  node, int  node_type, typename std::vector< TreeDecompositionBag >::iterator  begin, typename std::vector< TreeDecompositionBag >::iterator  end  )

protected

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildJoin_ ( TreeDecompositionBag  node, TreeDecompositionBag  left, TreeDecompositionBag  right, bool  do_forget  )

protected

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildLeaf_ ( TreeDecompositionBag  child )

protected

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildLinkage_ ( TreeDecompositionBag  node, TreeDecompositionBag  child  )

protected

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildRoot_ ( TreeDecompositionBag  child )

protected

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildSingle_ ( TreeDecompositionBag  node, int  node_type, TreeDecompositionBag  child  )

protected

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::linkWithForgetNodes_ ( TreeDecompositionContent  parent_set, TreeDecompositionBag  child  )

protected

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::linkWithIntroduceNodes_ ( TreeDecompositionContent  parent_set, TreeDecompositionBag  child  )

protected

template<class EditableGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecomposition> BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::makeNice

(

boost::shared_ptr< TreeDecompositionGraph > &

nice_tree

)

Converts the TreeDecomposition into a NiceTreeDecomposition A nice tree decomposition is a binary tree with five vertex types:

• Introduce-nodes, which have one child and one more inner vertex than their child
• Forget-nodes, which have one child and one inner vertex less than their child
• Join-nodes, which have two childs and the same inner vertices as their childs
• Leaf-nodes, which have no childs and exactly one inner vertex
• Root-nodes, which have one child and no inner vertices

template<class EditableGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecomposition> BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::operator()	(	UndirectedGraph const &	graph,
		EliminationOrder const &	permutation
	)

Builds a tree decomposition by the given elimination order

Parameters

graph	The source graph for which the tree decomposition is built
permutation	the elimination order which is used to build the tree

Returns

tree_decomposition an empty TreeNodeList which is filled with instances of TreeDecompositionBag

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::operator()	(	TreeDecompositionBag	n,
		typename std::vector< TreeDecompositionBag >::iterator	c_i,
		typename std::vector< TreeDecompositionBag >::iterator	c_end
	)

Member Data Documentation

template<class EditableGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecompositionGraph> BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::nice_tree_

protected

Definition at line 501 of file treeWidth.h.

template<class EditableGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::root_

protected

Definition at line 503 of file treeWidth.h.

template<class EditableGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecomposition> BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::tree_

protected

Definition at line 499 of file treeWidth.h.

template<class EditableGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecompositionGraph> BALL::TreeWidthImplementation< EditableGraph >::TreeDecompositionBuilder< OriginalGraphType >::tree_graph_

protected

Definition at line 500 of file treeWidth.h.