BALL
1.4.1
|
#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 |
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.
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 285 of file treeWidth.h.
typedef std::map<VertexType, bool> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::BitSet [protected] |
Definition at line 339 of file treeWidth.h.
typedef std::map<BitSet, Size> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::GraphMap [protected] |
Definition at line 340 of file treeWidth.h.
typedef std::pair<BitSet, Size> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::MapEntry [protected] |
Definition at line 342 of file treeWidth.h.
typedef std::pair<typename GraphMap::iterator, bool> BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::MapPos [protected] |
Definition at line 341 of file treeWidth.h.
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.
Definition at line 293 of file treeWidth.h.
BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::QuickBB | ( | UndirectedGraph const & | graph | ) |
Builds a new QuickBB algorithm for the given graph
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".
BitSet BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::buildBitset | ( | ) | const [protected] |
The bitset remembers the eliminated vertices without an ordering.
EliminationOrder BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::compute | ( | ) |
computes the best elimination order
SIMPLICIAL_TYPE BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::isSimplicial | ( | VertexType & | vertex | ) | const |
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.
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.
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.
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.
QuickBBState BALL::TreeWidthImplementation< UndirectedGraph >::QuickBB< Lowerbound, Upperbound >::state [protected] |
the current vertex in the search-tree
Definition at line 352 of file treeWidth.h.
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.
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.