Package org.graph4j.vsp

Class VertexSeparator

java.lang.Object

org.graph4j.vsp.VertexSeparator

public class VertexSeparator
extends Object

Utility class for representing a vertex separator set.

Author:

Cristian Frăsinaru

See Also:

• GreedyVertexSeparator

Constructor Summary

Constructors

Constructor	Description
VertexSeparator(Graph graph)	The default maximum shore size is 2n/3, where n is the number of vertices in the graph.
VertexSeparator(Graph graph, int maxShoreSize)
VertexSeparator(VertexSet separator, VertexSet leftShore, VertexSet rightShore)	Deprecated.
VertexSeparator(VertexSeparator other)	Copy constructor.

Method Summary

Modifier and Type	Method	Description
boolean	contains(int v)
boolean	isComplete()
boolean	isValid()	It does not test if it is complete, i.e. it contains all vertices of the graph.
VertexSet	leftShore()
VertexSet	rightShore()
VertexSet	separator()
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Details

VertexSeparator

public VertexSeparator(Graph graph)

The default maximum shore size is 2n/3, where n is the number of vertices in the graph.

Parameters:

graph - the graph on which the separator is defined.

VertexSeparator

public VertexSeparator(Graph graph,
 int maxShoreSize)

Parameters:

graph - the graph on which the separator is defined.

maxShoreSize - the maximum shore size.

VertexSeparator

public VertexSeparator(VertexSeparator other)

Copy constructor.

Parameters:

other - a vertex separator.

VertexSeparator

@Deprecated
public VertexSeparator(VertexSet separator,
 VertexSet leftShore,
 VertexSet rightShore)

Deprecated.

Parameters:

separator - the separator vertex set.

leftShore - the left shore.

rightShore - the right shore.

Method Details

separator

public VertexSet separator()

Returns:

the separator.

leftShore

public VertexSet leftShore()

Returns:

the left shore.

rightShore

public VertexSet rightShore()

Returns:

the right shore.

contains

public boolean contains(int v)

Parameters:

v - a vertex number.

Returns:

true if v is covered by any of the three sets.

isComplete

public boolean isComplete()

Returns:

true if all the vertices of the graph are in one of the three sets: leftShore, rightShore or separator.

isValid

public boolean isValid()

It does not test if it is complete, i.e. it contains all vertices of the graph.

Returns:

true if the properties of a vertex separator are satisfied.

toString

public String toString()

Overrides:

toString in class Object