BALL::TreeWidth< UndirectedGraph > Class Template Reference

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

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

template<class UndirectedGraph>

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

Definition at line 96 of file treeWidth.h.

template<class UndirectedGraph>

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

Definition at line 97 of file treeWidth.h.

template<class UndirectedGraph>

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

Definition at line 112 of file treeWidth.h.

template<class UndirectedGraph>

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

Definition at line 107 of file treeWidth.h.

template<class UndirectedGraph>

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

Definition at line 99 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 105 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 111 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 65 of file treeWidth.h.

Constructor & Destructor Documentation

template<class UndirectedGraph>

BALL::TreeWidth< UndirectedGraph >::TreeWidth

(

UndirectedGraph const &

input

)

Member Function Documentation

template<class UndirectedGraph>

static 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

template<class UndirectedGraph>

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

inline

Definition at line 126 of file treeWidth.h.

template<class UndirectedGraph>

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

inline

Definition at line 127 of file treeWidth.h.

template<class UndirectedGraph>

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

Write a tree decomposition in graphviz format.

Member Data Documentation

template<class UndirectedGraph>

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

protected

Definition at line 170 of file treeWidth.h.

template<class UndirectedGraph>

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

protected

Definition at line 168 of file treeWidth.h.

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.

template<class UndirectedGraph>

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

protected

Definition at line 172 of file treeWidth.h.