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

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

public class TreewidthDP<D extends GraphInput.InputData>
extends java.lang.Object
implements Exact<D>


Constructor Summary
TreewidthDP()
          Create an instance of the DP algorithm with the trivial upperbound of n-1.
TreewidthDP(int upperBound)
          Create an instance of the DP algorithm with a known upperbound.
TreewidthDP(UpperBound<D> ubAlg)
          Create an instance of the DP algorithm and use the supplied upperbound algorithm to calculate the initial upperbound.
 
Method Summary
 java.lang.String getName()
          Every algorithm has a name.
 int getTreewidth()
          Returns the found treewidth.
 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

TreewidthDP

public TreewidthDP()
Create an instance of the DP algorithm with the trivial upperbound of n-1.


TreewidthDP

public TreewidthDP(int upperBound)
Create an instance of the DP algorithm with a known upperbound.

Parameters:
upperBound - A known upperbound for the graph.

TreewidthDP

public TreewidthDP(UpperBound<D> ubAlg)
Create an instance of the DP algorithm and use the supplied upperbound algorithm to calculate the initial upperbound.

Parameters:
ubAlg - The upperbound algorithm to use.
Method Detail

getTreewidth

public int getTreewidth()
Description copied from interface: Exact
Returns the found treewidth.
This method does not compute the treewidth; you must first call run().

Specified by:
getTreewidth in interface Exact<D extends GraphInput.InputData>
Returns:
The treewidth computed.

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.

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>