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

java.lang.Object
  extended by nl.uu.cs.treewidth.algorithm.MinorMinWidth_QuickBB<D>

public class MinorMinWidth_QuickBB<D extends GraphInput.InputData>
extends java.lang.Object

The 'MinorMinWidth' lower bound. Reference: A Complete Anytime Algorithm for Treewidth Vibhav Gogate and Rina Dechter 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. This algorithm is optimized to be used with the QuickBB algorithm. It does not really contract the edges from the graph, but uses a copy of the neighbors of every vertex.

Author:
tw team

Constructor Summary
MinorMinWidth_QuickBB()
          Starts out as a lowerbound of -infty; improved to the mindegree lowerbound once run() is called.
 
Method Summary
 void contractEdge(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1, NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v2)
          This method 'contracts' the edge between v1 and v2.
 int getLowerBound()
           
 java.lang.String getName()
           
 void removeVertex(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1)
          This method removes the vertex from the copies of the neigborlists of its neighbors and clears it's own neighborlist copy.
 void run()
          Method runs the algorithm and sets the lowerbound.
 void setInput(NGraph<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> g)
          This method sets the input.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

MinorMinWidth_QuickBB

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

Method Detail

getName

public java.lang.String getName()

setInput

public void setInput(NGraph<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> g)
This method sets the input. The input should be of type QuickBBData, cause we copy the list of neighbors to a special variable. This variable is introduced, cause we do not wan't to really contract edges (too expensive method). WARNING: the graph must contain ListVertices!

Parameters:
g - the input graph

run

public void run()
Method runs the algorithm and sets the lowerbound.


contractEdge

public void contractEdge(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1,
                         NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v2)
This method 'contracts' the edge between v1 and v2. The graph isn't really modified, just the extra variable in the QuickBBData (see top description for more information)

Parameters:
v1 -
v2 -

removeVertex

public void removeVertex(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1)
This method removes the vertex from the copies of the neigborlists of its neighbors and clears it's own neighborlist copy.

Parameters:
v1 - The vertex to remove

getLowerBound

public int getLowerBound()
Returns:
The current lowerbound