org.jgrapht.alg.vertexcover

Class RecursiveExactVCImpl<V,E>

java.lang.Object

org.jgrapht.alg.vertexcover.RecursiveExactVCImpl<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MinimumVertexCoverAlgorithm<V,E>, MinimumWeightedVertexCoverAlgorithm<V,E>, VertexCoverAlgorithm<V>

public class RecursiveExactVCImpl<V,E>
extends Object
implements MinimumWeightedVertexCoverAlgorithm<V,E>, VertexCoverAlgorithm<V>

Finds a minimum vertex cover in a undirected graph. The implementation relies on a recursive algorithm. At each recursive step, the algorithm picks a unvisited vertex v and distinguishes two cases: either v has to be added to the vertex cover or all of its neighbors. In pseudo code, the algorithm (simplified) looks like this:

 
  $VC(G)$:
  if $V = \emptyset$ then return $\emptyset$
  Choose an arbitrary node $v \in G$
  $G1 := (V − v, \left{ e \in E | v \not \in e \right})$
  $G2 := (V − v − N(v), \left{ e \in E | e \cap (N(v) \cup v)= \empty \right})$
  if $|v \cup VC(G1)| \leq |N(v) \cup VC(G2)|$ then
    return $v \cup VC(G1)$
  else
    return $N(v) \cup VC(G2)$
 
 

To speed up the implementation, memoization and a bounding procedure are used. The current implementation solves instances with 150-250 vertices efficiently to optimality. TODO JK: determine runtime complexity and add it to class description. TODO JK: run this class through a performance profiler

Author:

Joris Kinable

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	RecursiveExactVCImpl.BitSetCover Helper class which represents a vertex cover as a space efficient BitSet

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MinimumVertexCoverAlgorithm

MinimumVertexCoverAlgorithm.VertexCover<V>, MinimumVertexCoverAlgorithm.VertexCoverImpl<V>

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexCoverAlgorithm

VertexCoverAlgorithm.VertexCover<V>, VertexCoverAlgorithm.VertexCoverImpl<V>

Constructor Summary

Constructors

Constructor and Description
RecursiveExactVCImpl() Deprecated. this constructor will be removed in the next release
RecursiveExactVCImpl(Graph<V,E> graph) Constructs a new GreedyVCImpl instance
RecursiveExactVCImpl(Graph<V,E> graph, Map<V,Double> vertexWeightMap) Constructs a new GreedyVCImpl instance

Method Summary

Modifier and Type	Method and Description
VertexCoverAlgorithm.VertexCover<V>	getVertexCover() Computes a vertex cover.
MinimumVertexCoverAlgorithm.VertexCover<V>	getVertexCover(Graph<V,E> graph) Computes a vertex cover; all vertices are considered to have equal weight.
MinimumVertexCoverAlgorithm.VertexCover<V>	getVertexCover(Graph<V,E> graph, Map<V,Double> vertexWeightMap) Computes a vertex cover; the weight of each vertex is provided in the in the vertexWeightMap.

Methods inherited from class java.lang.Object

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

Constructor Detail

RecursiveExactVCImpl

@Deprecated
public RecursiveExactVCImpl()

Deprecated. this constructor will be removed in the next release

Temporary constructor to ensure one-version-backwards-compatibility

RecursiveExactVCImpl

public RecursiveExactVCImpl(Graph<V,E> graph)

Constructs a new GreedyVCImpl instance

Parameters:

graph - input graph

RecursiveExactVCImpl

public RecursiveExactVCImpl(Graph<V,E> graph,
                            Map<V,Double> vertexWeightMap)

Constructs a new GreedyVCImpl instance

Parameters:

graph - input graph

vertexWeightMap - mapping of vertex weights

Method Detail

getVertexCover

public VertexCoverAlgorithm.VertexCover<V> getVertexCover()

Description copied from interface: VertexCoverAlgorithm

Computes a vertex cover.

Specified by:

getVertexCover in interface VertexCoverAlgorithm<V>

Returns:

a vertex cover

getVertexCover

public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(Graph<V,E> graph)

Description copied from interface: MinimumWeightedVertexCoverAlgorithm

Computes a vertex cover; all vertices are considered to have equal weight.

Specified by:

getVertexCover in interface MinimumVertexCoverAlgorithm<V,E>

Specified by:

getVertexCover in interface MinimumWeightedVertexCoverAlgorithm<V,E>

Parameters:

graph - the graph

Returns:

a vertex cover

getVertexCover

public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(Graph<V,E> graph,
                                                                 Map<V,Double> vertexWeightMap)

Description copied from interface: MinimumWeightedVertexCoverAlgorithm

Computes a vertex cover; the weight of each vertex is provided in the in the vertexWeightMap.

Specified by:

getVertexCover in interface MinimumWeightedVertexCoverAlgorithm<V,E>

Parameters:

graph - the input graph

vertexWeightMap - map containing non-negative weights for each vertex

Returns:

a vertex cover