Package org.graph4j.vsp

Class GreedyVertexSeparator

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.vsp.VertexSeparatorBase

org.graph4j.vsp.GreedyVertexSeparator

All Implemented Interfaces:

VertexSeparatorAlgorithm

public class GreedyVertexSeparator
extends VertexSeparatorBase
implements VertexSeparatorAlgorithm

There is no guarantee that the vertex separator created by the greedy algorithm is of minimum size.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.vsp.VertexSeparatorBase

maxShoreSize, solution

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
GreedyVertexSeparator(Graph graph)
GreedyVertexSeparator(Graph graph, int maxShoreSize)

Method Summary

Modifier and Type	Method	Description
VertexSeparator	getSeparator()	Computes and returns a vertex separator set.

Methods inherited from class org.graph4j.vsp.VertexSeparatorBase

maxShoreSize

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.vsp.VertexSeparatorAlgorithm

getGraph

Constructor Details

GreedyVertexSeparator

public GreedyVertexSeparator(Graph graph)

GreedyVertexSeparator

public GreedyVertexSeparator(Graph graph,
 int maxShoreSize)

Method Details

getSeparator

public VertexSeparator getSeparator()

Computes and returns a vertex separator set. There is no guarantee that the vertex separator returned is of minimum size. The right shore may be empty (in case of complete graphs, for example).

Specified by:

getSeparator in interface VertexSeparatorAlgorithm

Specified by:

getSeparator in class VertexSeparatorBase

Returns:

a vertex separator set.