nl.uu.cs.treewidth.algorithm
Class QuickBB<D extends GraphInput.InputData>

java.lang.Object
  extended by nl.uu.cs.treewidth.algorithm.QuickBB<D>
All Implemented Interfaces:
Algorithm<D>, Permutation<D>, UpperBound<D>

public class QuickBB<D extends GraphInput.InputData>
extends java.lang.Object
implements UpperBound<D>, Permutation<D>

A branch and bound algorithm for treewidth, designed by Gogate and Dechter. Sometimes, this algorithm gives an exact answer (this version); sometimes the algorithm uses much time, but can be stopped to yield an upper bound on the treewidth. Reference: A Complete Anytime Algorithm for Treewidth (Gogate and Dechter).

Author:
tw team

Constructor Summary
QuickBB()
           
 
Method Summary
 java.lang.String getName()
          Every algorithm has a name.
 NVertexOrder<D> getPermutation()
           
 int getUpperBound()
          Returns the upperbound.
 void run()
          Does the actual computation of the algorithm.
 void setInput(NGraph<D> g)
          Sets the input the algorithm will run on.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

QuickBB

public QuickBB()
Method Detail

getUpperBound

public int getUpperBound()
Description copied from interface: UpperBound
Returns the upperbound.

Specified by:
getUpperBound in interface UpperBound<D extends GraphInput.InputData>
Returns:
A valid upperbound. If run() has not been called, Integer.MAX_VALUE is returned.

getName

public java.lang.String getName()
Description copied from interface: Algorithm
Every algorithm has a name. This is for identification towards the user.

Specified by:
getName in interface Algorithm<D extends GraphInput.InputData>
Returns:
Name of the algorithm.

setInput

public void setInput(NGraph<D> g)
Description copied from interface: Algorithm
Sets the input the algorithm will run on.

Specified by:
setInput in interface Algorithm<D extends GraphInput.InputData>
Parameters:
g - The graph in standard graph format.

getPermutation

public NVertexOrder<D> getPermutation()
Specified by:
getPermutation in interface Permutation<D extends GraphInput.InputData>
Returns:
The computed permutation of the vertices.

run

public void run()
Description copied from interface: Algorithm
Does the actual computation of the algorithm. The result is remembered but not returned. Get it using the appropriate return function (getUpperbound(), getLowerBound(), etc.).
Only works after setInput has been called.

Specified by:
run in interface Algorithm<D extends GraphInput.InputData>