nl.uu.cs.treewidth.algorithm
Class MaximumCardinalitySearch<D extends GraphInput.InputData>
java.lang.Object
nl.uu.cs.treewidth.algorithm.MaximumCardinalitySearch<D>
- All Implemented Interfaces:
- Algorithm<D>, LowerBound<D>, Permutation<D>
public class MaximumCardinalitySearch<D extends GraphInput.InputData>
- extends java.lang.Object
- implements Permutation<D>, LowerBound<D>
Triangulation by using the elimination scheme obtained by using
the MCS (Maximum Cardinality Search) algorithm as given by Tarjan and Yannakakis.
The triangulation does not need to be minimal.
Reference paper: Maximum Cardinality Search for Computing Minimal Triangulations
Anne Berry, Jean R. S. Blair, and Pinar Heggernes
- Author:
- tw team
Methods inherited from class java.lang.Object |
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
MaximumCardinalitySearch
public MaximumCardinalitySearch()
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>
getLowerBound
public int getLowerBound()
- Specified by:
getLowerBound
in interface LowerBound<D extends GraphInput.InputData>
- Returns:
- A valid lowerbound. See class documentation for
details.