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

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

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

Triangulation by using the elimination scheme found by applying the LEX-P algorithm. These triangulations are not necessarily minimal. This All Start Version is run n times; everytime selecting a different vertex to start with. Sourcepaper: A Note on Lexicographic Breadth First Search for Chordal Graphs by Klaus Simon

Author:
team tw

Constructor Summary
AllStartLexBFS()
           
 
Method Summary
 java.lang.String getName()
          Every algorithm has a name.
 NVertexOrder<D> getPermutation()
           
 int getUpperBound()
          Returns the upperbound.
 void run()
          Method runs the algorithm and sets the permutation.
 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

AllStartLexBFS

public AllStartLexBFS()
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 input graph

run

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

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:
the upperbound