BALL 1.5.0
|
#include <BALL/DATATYPE/GRAPH/treeWidth.h>
Classes | |
class | BagContentWriter |
class | ComponentFilter_ |
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_ |
This class computes a minimal tree decomposition for the given input graph.
Definition at line 59 of file treeWidth.h.
typedef GRAPH::GraphTraits<UndirectedGraph>::EditableGraph BALL::TreeWidth< UndirectedGraph >::EditableGraph |
Definition at line 96 of file treeWidth.h.
typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor BALL::TreeWidth< UndirectedGraph >::OriginalVertexType |
Definition at line 97 of file treeWidth.h.
typedef boost::graph_as_tree<TreeDecompositionGraph, TreeDecompositionParentMap> BALL::TreeWidth< UndirectedGraph >::TreeDecomposition |
Definition at line 112 of file treeWidth.h.
typedef boost::graph_traits<TreeDecompositionGraph>::vertex_descriptor BALL::TreeWidth< UndirectedGraph >::TreeDecompositionBag |
Definition at line 107 of file treeWidth.h.
typedef std::set<OriginalVertexType> BALL::TreeWidth< UndirectedGraph >::TreeDecompositionContent |
Definition at line 99 of file treeWidth.h.
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.
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.
enum BALL::TreeWidth::BagType |
The type of this bag
Definition at line 65 of file treeWidth.h.
BALL::TreeWidth< UndirectedGraph >::TreeWidth | ( | UndirectedGraph const & | input | ) |
|
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
|
inline |
Definition at line 126 of file treeWidth.h.
|
inline |
Definition at line 127 of file treeWidth.h.
void BALL::TreeWidth< UndirectedGraph >::writeGraphvizFile | ( | std::ostream & | out, |
TreeDecomposition const & | td | ||
) |
Write a tree decomposition in graphviz format.
|
protected |
Definition at line 170 of file treeWidth.h.
|
protected |
Definition at line 168 of file treeWidth.h.
|
protected |
Definition at line 173 of file treeWidth.h.
|
protected |
Definition at line 172 of file treeWidth.h.