Loading...
Searching...
No Matches
BALL::TreeWidth< UndirectedGraph > Class Template Reference

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

## Classes

class | ComponentFilter_
class | BagContentWriter

## Public Types

enum | BagType { INTRODUCE_BAG , LEAF_BAG , FORGET_BAG , ROOT_BAG , JOIN_BAG , INNER_BAG , END_BAG }
typedef GRAPH::GraphTraits< UndirectedGraph >::EditableGraph | EditableGraph
typedef boost::graph_traits< UndirectedGraph >::vertex_descriptor | OriginalVertexType
typedef std::set< OriginalVertexType > | TreeDecompositionContent
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS, boost::property< boost::vertex_bag_content_t, std::set< OriginalVertexType >, boost::property< boost::vertex_bag_special_t, OriginalVertexType, boost::property< boost::vertex_bag_type_t, int > > >, boost::no_property > | TreeDecompositionGraph
typedef boost::graph_traits< TreeDecompositionGraph >::vertex_descriptor | TreeDecompositionBag
typedef boost::iterator_property_map< typename std::vector< TreeDecompositionBag >::iterator, typename boost::property_map< TreeDecompositionGraph, boost::vertex_index_t >::type > | TreeDecompositionParentMap
typedef boost::graph_as_tree< TreeDecompositionGraph, TreeDecompositionParentMap > | TreeDecomposition

## Public Member Functions

| TreeWidth (UndirectedGraph const &input)
void | writeGraphvizFile (std::ostream &out, TreeDecomposition const &td)
std::vector< boost::shared_ptr< EditableGraph > > & | getComponents ()
std::vector< boost::shared_ptr< TreeDecomposition > > & | getNiceTreeDecompositions ()

## Static Public Member Functions

static Size | computeTreeWidth (TreeDecomposition const &td)

## Protected Attributes

MolecularGraph const * | input_
std::vector< boost::shared_ptr< EditableGraph > > | components_
std::vector< boost::shared_ptr< TreeDecomposition > > | nice_tree_decompositions_
std::vector< boost::shared_ptr< TreeDecompositionGraph > > | nice_tree_decomposition_graphs_

## Detailed Description

template<class UndirectedGraph>
class BALL::TreeWidth< UndirectedGraph >

This class computes a minimal tree decomposition for the given input graph.

Definition at line 59 of file treeWidth.h.

## Member Typedef Documentation

## EditableGraph

template<class UndirectedGraph>

typedef GRAPH::GraphTraits<UndirectedGraph>::EditableGraph BALL::TreeWidth< UndirectedGraph >::EditableGraph

Definition at line 96 of file treeWidth.h.

## OriginalVertexType

template<class UndirectedGraph>

typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor BALL::TreeWidth< UndirectedGraph >::OriginalVertexType

Definition at line 97 of file treeWidth.h.

## TreeDecomposition

template<class UndirectedGraph>

typedef boost::graph_as_tree<TreeDecompositionGraph, TreeDecompositionParentMap> BALL::TreeWidth< UndirectedGraph >::TreeDecomposition

Definition at line 112 of file treeWidth.h.

## TreeDecompositionBag

template<class UndirectedGraph>

typedef boost::graph_traits<TreeDecompositionGraph>::vertex_descriptor BALL::TreeWidth< UndirectedGraph >::TreeDecompositionBag

Definition at line 107 of file treeWidth.h.

## TreeDecompositionContent

template<class UndirectedGraph>

typedef std::set<OriginalVertexType> BALL::TreeWidth< UndirectedGraph >::TreeDecompositionContent

Definition at line 99 of file treeWidth.h.

## TreeDecompositionGraph

template<class UndirectedGraph>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_bag_content_t, std::set<OriginalVertexType>, boost::property<boost::vertex_bag_special_t, OriginalVertexType, boost::property<boost::vertex_bag_type_t, int> > >, boost::no_property> BALL::TreeWidth< UndirectedGraph >::TreeDecompositionGraph

Definition at line 105 of file treeWidth.h.

## TreeDecompositionParentMap

template<class UndirectedGraph>

typedef boost::iterator_property_map<typename std::vector<TreeDecompositionBag>::iterator, typename boost::property_map<TreeDecompositionGraph, boost::vertex_index_t>::type> BALL::TreeWidth< UndirectedGraph >::TreeDecompositionParentMap

Definition at line 111 of file treeWidth.h.

## Member Enumeration Documentation

## BagType

template<class UndirectedGraph>

enum BALL::TreeWidth::BagType

The type of this bag

Enumerator
INTRODUCE_BAG | Introduce bags differs from their childs in exactly one new vertex
LEAF_BAG | Leaf bags contains just one vertex and have no childs
FORGET_BAG | Forget bags contain one vertex less than their children
ROOT_BAG | Root bags have an empty vertex set
JOIN_BAG | Join bags have two children, which have both the same inner vertices as their parent
INNER_BAG | Inner bags are any kind of inner node in the tree, i.e., JOIN, INTRODUCE, or FORGET nodes
END_BAG | End bags aren't defined, so you can use them as null-value or as placeholder

Definition at line 65 of file treeWidth.h.

## Constructor & Destructor Documentation

## TreeWidth()

template<class UndirectedGraph>

BALL::TreeWidth< UndirectedGraph >::TreeWidth | ( | UndirectedGraph const & | input | ) |

## Member Function Documentation

## computeTreeWidth()

template<class UndirectedGraph>

Size BALL::TreeWidth< UndirectedGraph >::computeTreeWidth | ( | TreeDecomposition const & | td | ) |

static

Compute the tree width of a given tree decomposition. This function iterates over all nodes in the graph to determine the tree width, i.e., the (maximum number of vertices over all bags) - 1

## getComponents()

template<class UndirectedGraph>

std::vector< boost::shared_ptr< EditableGraph > > & BALL::TreeWidth< UndirectedGraph >::getComponents | ( |  | ) |

inline

Definition at line 126 of file treeWidth.h.

## getNiceTreeDecompositions()

template<class UndirectedGraph>

std::vector< boost::shared_ptr< TreeDecomposition > > & BALL::TreeWidth< UndirectedGraph >::getNiceTreeDecompositions | ( |  | ) |

inline

Definition at line 127 of file treeWidth.h.

## writeGraphvizFile()

template<class UndirectedGraph>

void BALL::TreeWidth< UndirectedGraph >::writeGraphvizFile | ( | std::ostream & | out,
|  | TreeDecomposition const & | td )

Write a tree decomposition in graphviz format.

## Member Data Documentation

## components_

template<class UndirectedGraph>

std::vector<boost::shared_ptr<EditableGraph> > BALL::TreeWidth< UndirectedGraph >::components_

protected

Definition at line 170 of file treeWidth.h.

## input_

template<class UndirectedGraph>

MolecularGraph const* BALL::TreeWidth< UndirectedGraph >::input_

protected

Definition at line 168 of file treeWidth.h.

## nice_tree_decomposition_graphs_

template<class UndirectedGraph>

std::vector<boost::shared_ptr<TreeDecompositionGraph> > BALL::TreeWidth< UndirectedGraph >::nice_tree_decomposition_graphs_

protected

Definition at line 173 of file treeWidth.h.

## nice_tree_decompositions_

template<class UndirectedGraph>

std::vector<boost::shared_ptr<TreeDecomposition> > BALL::TreeWidth< UndirectedGraph >::nice_tree_decompositions_

protected

Definition at line 172 of file treeWidth.h.