Package org.graph4j.vsp

Class BacktrackVertexSeparator

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.vsp.VertexSeparatorBase

org.graph4j.vsp.BacktrackVertexSeparator

All Implemented Interfaces:

VertexSeparatorAlgorithm

public class BacktrackVertexSeparator
extends VertexSeparatorBase

WORK IN PROGRESS. Attempts at finding an optimum vertex separator using a systematic exploration of the search space. The backtracking is implemented in a non-recursive manner, using multiple threads.

A time limit may be imposed. If the algorithm stops due to the time limit, it will return the best separator found until then.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.vsp.VertexSeparatorBase

maxShoreSize

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
VertexSeparator	getSeparator()	Returns a vertex separator separator.
long	nodesExplored()

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

BacktrackVertexSeparator

public BacktrackVertexSeparator(Graph graph)

BacktrackVertexSeparator

public BacktrackVertexSeparator(Graph graph,
 int maxShoreSize)

Method Details

getSeparator

public VertexSeparator getSeparator()

Description copied from interface: VertexSeparatorAlgorithm

Returns a vertex separator separator.

Specified by:

getSeparator in interface VertexSeparatorAlgorithm

Specified by:

getSeparator in class VertexSeparatorBase

Returns:

a vertex separator set.

nodesExplored

public long nodesExplored()

Returns:

the number of nodes explored during the search.