|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnl.uu.cs.treewidth.algorithm.MinorMinWidth_QuickBB<D>
public class MinorMinWidth_QuickBB<D extends GraphInput.InputData>
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.
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 |
---|
public MinorMinWidth_QuickBB()
Method Detail |
---|
public java.lang.String getName()
public void setInput(NGraph<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> g)
g
- the input graphpublic void run()
public void contractEdge(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1, NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v2)
v1
- v2
- public void removeVertex(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1)
v1
- The vertex to removepublic int getLowerBound()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |