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:
VertexCoverAlgorithm<V>
public class RecursiveExactVCImpl<V,E> extends Object implements 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

  • Field Details

    • graph

      private Graph<V,E> graph
      Input graph

    • n

      private int n
      Number of vertices in the graph

    • neighborCache

      private NeighborCache<V,E> neighborCache
      Neighbor cache TODO JK: It might be worth trying to replace the neighbors index by a bitset view. As such, all operations can be simplified to bitset operations, which may improve the algorithm's performance.

    • memo

      private Map<BitSet, RecursiveExactVCImpl<V,E>.BitSetCover> memo
      Map for memoization

    • vertices

      private List<V> vertices
      Ordered list of vertices which will be iteratively considered to be included in a matching

    • vertexIDDictionary

      private Map<V,Integer> vertexIDDictionary
      Mapping of a vertex to its index in the list of vertices

    • upperBoundOnVertexCoverWeight

      private double upperBoundOnVertexCoverWeight
      Maximum weight of the vertex cover. In case there is no weight assigned to the vertices, the weight of the cover equals the cover's cardinality.

    • weighted

      private boolean weighted
      Indicates whether we are solving a weighted or unweighted version of the problem

    • vertexWeightMap

      private Map<V,Double> vertexWeightMap

  • Constructor Details

    • 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 Details

    • 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

    • calculateCoverRecursively

      private RecursiveExactVCImpl<V,E>.BitSetCover calculateCoverRecursively(int indexNextCandidate, BitSet visited, double accumulatedWeight)

    • getWeight

      private double getWeight(Collection<V> vertices)
      Returns the weight of a collection of vertices. In case of the unweighted vertex cover problem, the return value is the cardinality of the collection. In case of the weighted version, the return value is the sum of the weights of the vertices
      Parameters:
      vertices - vertices
      Returns:
      the total weight of the vertices in the collection.

    • calculateUpperBound

      private double calculateUpperBound()
      Calculates a cheap upper bound on the optimum solution. Currently, we return the best solution found by either the greedy heuristic, or Clarkson's 2-approximation. Neither of these 2 algorithms dominates the other. //TODO JK: Are there better bounding procedures?