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

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

List of all members.

Classes

struct  QuickBBState

Public Types

enum  SIMPLICIAL_TYPE { NOT_SIMPLICIAL, ALMOST_SIMPLICIAL, IS_SIMPLICIAL }

Public Member Functions

 QuickBB (UndirectedGraph const &graph)
EliminationOrder compute ()
SIMPLICIAL_TYPE isSimplicial (VertexType &vertex) const

Protected Types

typedef std::map< VertexType,
bool
BitSet
typedef std::map< BitSet, SizeGraphMap
typedef std::pair< typename
GraphMap::iterator, bool
MapPos
typedef std::pair< BitSet, SizeMapEntry

Protected Member Functions

void branchAndBound (QuickBBState &nstate)
void prune (QuickBBState &)
BitSet buildBitset () const

Protected Attributes

UndirectedGraph graph_
QuickBBState state
EliminationOrder greedy_solution
EliminationOrder own_solution
GraphMap visitedSubgraphs
Size upper_bound

Detailed Description

template<class UndirectedGraph>
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
class BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >

This algorithm computes a perfect elimination order in a branch and bound approach. First it computes a greedy solution. Then it tries each vertex permutation and uses a lower bound algorithm to check, if this branch can be better than either the best found solution or a found permutation of the same vertices but in a different order. If not, the branch is bounded and the algorithm tries another permutation.

Template Parameters:
Lowerboundthe lowerbound algorithm which should be used by this branch and bound algorithm
Upperboundthe greedy algorithm which is used to compute a initial solution

Definition at line 285 of file treeWidth.h.


Member Typedef Documentation

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
typedef std::map<VertexType, bool> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::BitSet [protected]

Definition at line 339 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
typedef std::map<BitSet, Size> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::GraphMap [protected]

Definition at line 340 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
typedef std::pair<BitSet, Size> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::MapEntry [protected]

Definition at line 342 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
typedef std::pair<typename GraphMap::iterator, bool> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::MapPos [protected]

Definition at line 341 of file treeWidth.h.


Member Enumeration Documentation

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
enum BALL::TreeWidthImplementation::QuickBB::SIMPLICIAL_TYPE

A vertex IS simplicial, if its neighbourhood induces a clique. A vertex is ALMOST simplicial, it all but one of its neighbours induces a clique.

Enumerator:
NOT_SIMPLICIAL 
ALMOST_SIMPLICIAL 
IS_SIMPLICIAL 

Definition at line 293 of file treeWidth.h.


Constructor & Destructor Documentation

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::QuickBB ( UndirectedGraph const &  graph)

Builds a new QuickBB algorithm for the given graph


Member Function Documentation

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
void BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::branchAndBound ( QuickBBState nstate) [protected]

Each vertex in the search tree is an elimination order. The root is an elimination order of length 0. It's children are elimination order of length 1 and so on. The leafs are elimination order of length n and define a tree decomposition. This algorithm searches the best solution (= permutation with minimal tree width) in this search tree. It computes the lowerbound for each vertex to get the mimimal tree width of the subtree, which is rooted in this vertex. Branches are bounded, if their lowerbound is higher than the tree width of the best found solution, or if there is another branch with a better tree width which eliminates the same vertices but in a different order. To speed up the computation, the algorithm uses a greedy solution as "template".

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
BitSet BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::buildBitset ( ) const [protected]

The bitset remembers the eliminated vertices without an ordering.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
EliminationOrder BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::compute ( )

computes the best elimination order

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
SIMPLICIAL_TYPE BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::isSimplicial ( VertexType vertex) const
template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
void BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::prune ( QuickBBState ) [protected]

Vertices which are simplicial or almost simplicial can be eliminated instantly. So this function is called at the begin of the algorithm to reduce the number of vertices and the length of the searched permutation. You could call this function in each branch&bound step, but testing the simpliciality is expensive. So this is done only one time in the algorithm.


Member Data Documentation

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
UndirectedGraph BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::graph_ [protected]

The graph for which the tree decomposition is built

Definition at line 347 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
EliminationOrder BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::greedy_solution [protected]

An initial permutation which is computed by a greedy algorithm

Definition at line 357 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
EliminationOrder BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::own_solution [protected]

The permutation which is found by this algorithm

Definition at line 362 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
QuickBBState BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::state [protected]

the current vertex in the search-tree

Definition at line 352 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
Size BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::upper_bound [protected]

the current upper bound. A branch is bound if it has a worse penalty than the upper bound. Each found solution gives a new upper bound. The greedy solution is the initial upper bound. The algorithm terminates if it's upper bound is equal to the lowerbound.

Definition at line 375 of file treeWidth.h.

template<class UndirectedGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
GraphMap BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::visitedSubgraphs [protected]

Remembers the eliminated vertices of found branches during the algorithm. A branch is bound if it eliminates the same vertices but with a worse penalty.

Definition at line 368 of file treeWidth.h.

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