Loading...
Searching...
No Matches
BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound > Class Template Reference

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

## 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, Size > | GraphMap
typedef std::pair< typename GraphMap::iterator, bool > | MapPos
typedef std::pair< BitSet, Size > | MapEntry

## 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
std::map< int, VertexType > | index_to_vertex_

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

  Lowerbound | the lowerbound algorithm which should be used by this branch and bound algorithm
  Upperbound | the greedy algorithm which is used to compute a initial solution

Definition at line 316 of file treeWidth.h.

## Member Typedef Documentation

## BitSet

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

## GraphMap

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

## MapEntry

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

## MapPos

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

## Member Enumeration Documentation

## SIMPLICIAL_TYPE

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

## Constructor & Destructor Documentation

## QuickBB()

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

## branchAndBound()

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".

## buildBitset()

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.

## compute()

template<class UndirectedGraph>
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>

EliminationOrder BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::compute | ( |  | ) |

computes the best elimination order

## isSimplicial()

template<class UndirectedGraph>
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>

SIMPLICIAL_TYPE BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::isSimplicial | ( | VertexType & | vertex | ) | const

## prune()

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

## graph_

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

## greedy_solution

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

## index_to_vertex_

template<class UndirectedGraph>
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>

std::map<int, VertexType> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::index_to_vertex_

protected

Definition at line 433 of file treeWidth.h.

## own_solution

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

## state

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

## upper_bound

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

## visitedSubgraphs

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