Package org.graph4j.vsp

Class VertexSeparatorBase

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.vsp.VertexSeparatorBase
All Implemented Interfaces:
VertexSeparatorAlgorithm
Direct Known Subclasses:
BacktrackVertexSeparator, GreedyVertexSeparator
public abstract class VertexSeparatorBase extends SimpleGraphAlgorithm implements VertexSeparatorAlgorithm
The vertex separator problem (VSP) is to find a partition of V into nonempty three classes A, B, C such that there is no edge between A and B, max(|A|,|B|) <= f(n) and |C| is minimum. C is called separator, A and B are called shores. The value of the parameter f(n) which is more used in literature is 2n/3.
Author:
Cristian Frăsinaru

  • Field Details

    • maxShoreSize

      protected final int maxShoreSize

    • solution

      protected VertexSeparator solution

  • Constructor Details

    • VertexSeparatorBase

      public VertexSeparatorBase(Graph graph)
      Creates an algorithm for computing a vertex separator with the default argument for the maximum shore size of 2n/3, where n is the number of vertices in the graph.
      Parameters:
      graph - the input graph.

    • VertexSeparatorBase

      public VertexSeparatorBase(Graph graph, int maxShoreSize)
      Creates an algorithm for computing a vertex separator with the specified maximum shore size.
      Parameters:
      graph - the input graph.
      maxShoreSize - the maximum shore size.

  • Method Details

    • maxShoreSize

      public int maxShoreSize()
      Returns the mazimum shore size used by the algorithmS.
      Returns:
      the maximum shore size.

    • getSeparator

      public abstract VertexSeparator getSeparator()
      Description copied from interface: VertexSeparatorAlgorithm
      Returns a vertex separator separator.
      Specified by:
      getSeparator in interface VertexSeparatorAlgorithm
      Returns:
      a vertex separator set.