BALL::TreeWidthImplementation< EditableGraph >::GreedyX< Criterion > Class Template Reference

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

Inheritance diagram for BALL::TreeWidthImplementation< EditableGraph >::GreedyX< Criterion >:

Public Member Functions
EliminationOrder	operator() (UndirectedGraph &original_graph)

Additional Inherited Members
Public Types inherited from BALL::UnaryFunctor< UndirectedGraph, std::pair< std::vector< boost::graph_traits< UndirectedGraph::vertex_descriptor > >, Size > >
typedef std::pair< std::vector < boost::graph_traits < UndirectedGraph::vertex_descriptor > >, Size >	result_type
typedef UndirectedGraph	argument_type
typedef UndirectedGraph &	argument_reference
typedef const UndirectedGraph &	const_argument_reference
typedef UndirectedGraph *	argument_pointer
typedef const UndirectedGraph *	const_argument_pointer

Detailed Description

template<class EditableGraph>
template<class Criterion>
class BALL::TreeWidthImplementation< EditableGraph >::GreedyX< Criterion >

Algorithm which can be extended to different upperbound heuristics which follow the same procedure: Finding a vertex v by a special criterium, insert this vertex in the elimination order and then eliminate it in the graph.

The basic idea is to build a Fill-In-Graph. Such a Fill-In-Graph can be produced by eliminating the vertices of a graph and adding the edges, which appear by eliminating, into the Fill-In-Graph. If the vertices were eliminated in the correct order, the tree decomposition of the Fill-In-Graph is also the optimal tree decomposition of the source graph. Otherwise, it's a tree decomposition with higher treewidth which can be used as upperbound. The order of eliminating is called EliminationOrder. Each GreedyX algorithm returns the EliminationOrder with the vertex permuation and the treewidth. This vertex permutation can be used to build a tree decomposition of the source graph.

Template Parameters

Criterion

the criterium which chooses the next vertex to eliminate

Exceptions

BALL::GRAPH::UnconnectedGraphException

if called on unconnected graphs

Definition at line 287 of file treeWidth.h.

Member Function Documentation

template<class EditableGraph >

template<class Criterion >

EliminationOrder BALL::TreeWidthImplementation< EditableGraph >::GreedyX< Criterion >::operator()

(

UndirectedGraph &

original_graph

)