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

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

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

The GreedyFillIn algorithm computes a permutation and at the same time derives an upperbound.
It does this by eliminating the vertex for which we have to add the lowest number of edges when we would eliminate the vertex. This is done until the graph is empty.
Reference paper: Treewidth Computations I. Upper Bounds, Hans L. Bodlaender and Arie M.C.A. Koster (to appear).

Author:
tw team

Nested Class Summary
 class GreedyFillIn.GreedyData
           
 
Constructor Summary
GreedyFillIn()
           
GreedyFillIn(boolean checkDegreeZero)
           
 
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

GreedyFillIn

public GreedyFillIn()

GreedyFillIn

public GreedyFillIn(boolean checkDegreeZero)
Method Detail

getPermutation

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

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>

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.