BALL 1.5.0
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
BALL::TreeWidthImplementation< UndirectedGraph >::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< OriginalVertexTypeTreeDecompositionContent
 

Public Member Functions

boost::shared_ptr< TreeDecompositionoperator() (UndirectedGraph const &graph, EliminationOrder const &permutation)
 
boost::shared_ptr< TreeDecompositionmakeNice (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< TreeDecompositiontree_
 
boost::shared_ptr< TreeDecompositionGraphtree_graph_
 
boost::shared_ptr< TreeDecompositionGraphnice_tree_
 
TreeDecompositionBag root_
 

Detailed Description

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

Definition at line 448 of file treeWidth.h.

Member Typedef Documentation

◆ OriginalVertexType

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

Definition at line 455 of file treeWidth.h.

◆ TreeDecomposition

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

Definition at line 451 of file treeWidth.h.

◆ TreeDecompositionBag

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

Definition at line 452 of file treeWidth.h.

◆ TreeDecompositionContent

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

Definition at line 457 of file treeWidth.h.

◆ TreeDecompositionGraph

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

Definition at line 453 of file treeWidth.h.

Member Function Documentation

◆ branch_()

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

◆ buildJoin_()

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

◆ buildLeaf_()

template<class UndirectedGraph >
template<class OriginalGraphType >
TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildLeaf_ ( TreeDecompositionBag  child)
protected

◆ buildLinkage_()

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

◆ buildRoot_()

template<class UndirectedGraph >
template<class OriginalGraphType >
TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::buildRoot_ ( TreeDecompositionBag  child)
protected

◆ buildSingle_()

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

◆ linkWithForgetNodes_()

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

◆ linkWithIntroduceNodes_()

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

◆ makeNice()

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

◆ operator()() [1/2]

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 
)

◆ operator()() [2/2]

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
graphThe source graph for which the tree decomposition is built
permutationthe elimination order which is used to build the tree
Returns
tree_decomposition an empty TreeNodeList which is filled with instances of TreeDecompositionBag

Member Data Documentation

◆ nice_tree_

template<class UndirectedGraph >
template<class OriginalGraphType >
boost::shared_ptr<TreeDecompositionGraph> BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::nice_tree_
protected

Definition at line 501 of file treeWidth.h.

◆ root_

template<class UndirectedGraph >
template<class OriginalGraphType >
TreeDecompositionBag BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::root_
protected

Definition at line 503 of file treeWidth.h.

◆ tree_

template<class UndirectedGraph >
template<class OriginalGraphType >
boost::shared_ptr<TreeDecomposition> BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::tree_
protected

Definition at line 499 of file treeWidth.h.

◆ tree_graph_

template<class UndirectedGraph >
template<class OriginalGraphType >
boost::shared_ptr<TreeDecompositionGraph> BALL::TreeWidthImplementation< UndirectedGraph >::TreeDecompositionBuilder< OriginalGraphType >::tree_graph_
protected

Definition at line 500 of file treeWidth.h.