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

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

List of all members.

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 UndirectedGraph>
template<class OriginalGraphType>
class BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >

Definition at line 414 of file treeWidth.h.

---

Member Typedef Documentation

template<class UndirectedGraph >

template<class OriginalGraphType >

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

Definition at line 421 of file treeWidth.h.

template<class UndirectedGraph >

template<class OriginalGraphType >

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

Definition at line 417 of file treeWidth.h.

template<class UndirectedGraph >

template<class OriginalGraphType >

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

Definition at line 418 of file treeWidth.h.

template<class UndirectedGraph >

template<class OriginalGraphType >

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

Definition at line 423 of file treeWidth.h.

template<class UndirectedGraph >

template<class OriginalGraphType >

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

Definition at line 419 of file treeWidth.h.

---

Member Function Documentation

template<class UndirectedGraph >

template<class OriginalGraphType >

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

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildJoin_	(	TreeDecompositionBag	node,
		TreeDecompositionBag	left,
		TreeDecompositionBag	right,
		bool	do_forget
	)		[protected]

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildLeaf_

(

TreeDecompositionBag

child

)

[protected]

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildLinkage_	(	TreeDecompositionBag	node,
		TreeDecompositionBag	child
	)		[protected]

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildRoot_

(

TreeDecompositionBag

child

)

[protected]

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildSingle_	(	TreeDecompositionBag	node,
		int	node_type,
		TreeDecompositionBag	child
	)		[protected]

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::linkWithForgetNodes_	(	TreeDecompositionContent	parent_set,
		TreeDecompositionBag	child
	)		[protected]

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::linkWithIntroduceNodes_	(	TreeDecompositionContent	parent_set,
		TreeDecompositionBag	child
	)		[protected]

template<class UndirectedGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecomposition> BALL::TreeWidthImplementation< UndirectedGraph >::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 UndirectedGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecomposition> BALL::TreeWidthImplementation< UndirectedGraph >::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 UndirectedGraph >

template<class OriginalGraphType >

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

---

Member Data Documentation

template<class UndirectedGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecompositionGraph> BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::nice_tree_ [protected]

Definition at line 467 of file treeWidth.h.

template<class UndirectedGraph >

template<class OriginalGraphType >

TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::root_ [protected]

Definition at line 469 of file treeWidth.h.

template<class UndirectedGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecomposition> BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::tree_ [protected]

Definition at line 465 of file treeWidth.h.

template<class UndirectedGraph >

template<class OriginalGraphType >

boost::shared_ptr<TreeDecompositionGraph> BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::tree_graph_ [protected]

Definition at line 466 of file treeWidth.h.