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>

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

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 = ∅ then return ∅
  Choose an arbitrary node v ∈ G
  G1 := (V − {v}, { e ∈ E | v ∈/ e })
  G2 := (V − {v} − N(v), { e ∈ E | e ∩ (N(v) ∪ {v})= ∅ })
  if |{v} ∪ VC(G1)| ≤ |N(v) ∪ VC(G2)| then
    return {v} ∪ VC(G1)
  else
    return N(v) ∪ 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>

Constructor Summary

Constructors

Constructor and Description
RecursiveExactVCImpl()

Method Summary

Modifier and Type	Method and Description
MinimumVertexCoverAlgorithm.VertexCover<V>	getVertexCover(UndirectedGraph<V,E> graph) Computes a vertex cover; all vertices are considered to have equal weight.
MinimumVertexCoverAlgorithm.VertexCover<V>	getVertexCover(UndirectedGraph<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

public RecursiveExactVCImpl()

Method Detail

getVertexCover

public MinimumVertexCoverAlgorithm.VertexCover<V> getVertexCover(UndirectedGraph<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(UndirectedGraph<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