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

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

public class AllStartMinorMinWidth<D extends GraphInput.InputData>
extends java.lang.Object
implements LowerBound<D>

The algorithm repeativly contracts the lowest degree vertex with a lowest degree neighbor. The lowerbound is the maximum degree of the selected lowest degree vertices at the time of contraction. Reference: A Complete Anytime Algorithm for Treewidth Vibhav Gogate and Rina Dechter

Author:
tw team

Nested Class Summary
 
Nested classes/interfaces inherited from interface nl.uu.cs.treewidth.algorithm.LowerBound
LowerBound.Creator
 
Constructor Summary
AllStartMinorMinWidth()
          Starts out as a lowerbound of -infty; improved to the mindegree lowerbound once run() is called.
 
Method Summary
 int getLowerBound()
           
 java.lang.String getName()
          Every algorithm has a name.
 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

AllStartMinorMinWidth

public AllStartMinorMinWidth()
Starts out as a lowerbound of -infty; improved to the mindegree lowerbound once run() is called.

Method Detail

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>

getLowerBound

public int getLowerBound()
Specified by:
getLowerBound in interface LowerBound<D extends GraphInput.InputData>
Returns:
A valid lowerbound. See class documentation for details.