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

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

Classes

struct  FillInHeuristic
 
class  GeneralLowerBoundAlgorithm
 Generic lower bound algorithm on graphs. More...
 
class  GreedyX
 
class  MinorMinWidthCriterion
 
class  MinorMinWidthReducer
 
class  QuickBB
 
class  TreeDecompositionBuilder
 

Public Types

typedef boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
 
typedef boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
 
typedef boost::graph_traits< UndirectedGraph >::vertex_iterator VertexIterator
 
typedef std::pair< std::vector< Size >, SizeEliminationOrder
 
typedef GeneralLowerBoundAlgorithm< MinorMinWidthCriterion, MinorMinWidthReducerMinorMinWidth
 
typedef GreedyX< FillInHeuristicGreedyFillIn
 

Detailed Description

template<class UndirectedGraph>
class BALL::TreeWidthImplementation< UndirectedGraph >

Definition at line 177 of file treeWidth.h.

Member Typedef Documentation

◆ EliminationOrder

template<class UndirectedGraph >
std::pair<std::vector<Size>, Size> BALL::TreeWidthImplementation< UndirectedGraph >::EliminationOrder

An EliminationOrder is a permutation of vertices of a graph which can be used to build a Fill-In-Graph. The TreeDecomposition of such a graph is a minimal Tree-Decomposition of the source graph, if the elimination order is perfect. first is the permutation of vertices, second is the tree width of the Three-Decomposition of such a Fill-In graph

Definition at line 191 of file treeWidth.h.

◆ GreedyFillIn

template<class UndirectedGraph >
GreedyX<FillInHeuristic> BALL::TreeWidthImplementation< UndirectedGraph >::GreedyFillIn

An upperbound heuristic which computes an EliminationOrder, which can build a tree decomposition, and a treewidth of a given graph. The basic idea is to add as few as possible edges into the FillInGraph, because this should reduce the treewidth of the FillInGraph. Nevertheless, it's just a heuristic, so there is no guarantee, that the treewidth is minimal.

Exceptions
BALL::GRAPH::UnconnectedGraphExceptionif called on unconnected graphs

Definition at line 445 of file treeWidth.h.

◆ MinorMinWidth

template<class UndirectedGraph >
GeneralLowerBoundAlgorithm<MinorMinWidthCriterion, MinorMinWidthReducer> BALL::TreeWidthImplementation< UndirectedGraph >::MinorMinWidth

Minor-Min-Width is a lowerbound algorithm for computing the treewidth. It contracts in each step a vertex u, which has minimum degree in graph, with a vertex v, which has a minimum degree in u's neighbourhood. The maximum of the minimum degrees is the lowerbound for the treewidth.

The basic idea behind this algorithm is:

  • the treewidth of a graph is never lower than the treewidth of its minor
  • the treewidth of a graph is never lower than the minimum degree of its vertices (because you can always find an optimal tree decomposition which contains a leaf, which has at least one vertex v, which isn't contained in the parents vertex set. For each edge of this vertex v, there must be a vertex in the leaf. So degree(v) is a minimal treewidth of this tree decomposition!)
    Exceptions
    BALL::GRAPH::UnconnectedGraphExceptionif called on unconnected graphs

Definition at line 268 of file treeWidth.h.

◆ NeighbourIterator

template<class UndirectedGraph >
boost::graph_traits<UndirectedGraph>::adjacency_iterator BALL::TreeWidthImplementation< UndirectedGraph >::NeighbourIterator

Definition at line 182 of file treeWidth.h.

◆ VertexIterator

template<class UndirectedGraph >
boost::graph_traits<UndirectedGraph>::vertex_iterator BALL::TreeWidthImplementation< UndirectedGraph >::VertexIterator

Definition at line 183 of file treeWidth.h.

◆ VertexType

template<class UndirectedGraph >
boost::graph_traits<UndirectedGraph>::vertex_descriptor BALL::TreeWidthImplementation< UndirectedGraph >::VertexType

Definition at line 181 of file treeWidth.h.