BALL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines
Classes | Public Types | Public Member Functions | Protected Attributes
BALL::TreeWidth< UndirectedGraph > Class Template Reference

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

List of all members.

Classes

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)
std::vector< boost::shared_ptr
< EditableGraph > > & 
getComponents ()
std::vector< boost::shared_ptr
< TreeDecomposition > > & 
getNiceTreeDecompositions ()

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 57 of file treeWidth.h.


Member Typedef Documentation

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

Definition at line 94 of file treeWidth.h.

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

Definition at line 95 of file treeWidth.h.

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

Definition at line 110 of file treeWidth.h.

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

Definition at line 105 of file treeWidth.h.

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

Definition at line 97 of file treeWidth.h.

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 103 of file treeWidth.h.

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 109 of file treeWidth.h.


Member Enumeration Documentation

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 63 of file treeWidth.h.


Constructor & Destructor Documentation

template<class UndirectedGraph>
BALL::TreeWidth< UndirectedGraph >::TreeWidth ( UndirectedGraph const &  input)

Member Function Documentation

template<class UndirectedGraph>
std::vector<boost::shared_ptr<EditableGraph> >& BALL::TreeWidth< UndirectedGraph >::getComponents ( ) [inline]

Definition at line 114 of file treeWidth.h.

template<class UndirectedGraph>
std::vector<boost::shared_ptr<TreeDecomposition> >& BALL::TreeWidth< UndirectedGraph >::getNiceTreeDecompositions ( ) [inline]

Definition at line 115 of file treeWidth.h.


Member Data Documentation

template<class UndirectedGraph>
std::vector<boost::shared_ptr<EditableGraph> > BALL::TreeWidth< UndirectedGraph >::components_ [protected]

Definition at line 139 of file treeWidth.h.

template<class UndirectedGraph>
MolecularGraph const* BALL::TreeWidth< UndirectedGraph >::input_ [protected]

Definition at line 138 of file treeWidth.h.

template<class UndirectedGraph>
std::vector<boost::shared_ptr<TreeDecompositionGraph> > BALL::TreeWidth< UndirectedGraph >::nice_tree_decomposition_graphs_ [protected]

Definition at line 142 of file treeWidth.h.

template<class UndirectedGraph>
std::vector<boost::shared_ptr<TreeDecomposition> > BALL::TreeWidth< UndirectedGraph >::nice_tree_decompositions_ [protected]

Definition at line 141 of file treeWidth.h.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines