Loading...
Searching...
No Matches
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< 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 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

  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

## 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.