Module org.jgrapht.core
Package org.jgrapht.alg.vertexcover

Class 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 java.lang.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 Detail

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

      • vertices

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

      • vertexIDDictionary

        private java.util.Map<V,​java.lang.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 java.util.Map<V,​java.lang.Double> vertexWeightMap

    • Constructor Detail

      • RecursiveExactVCImpl

        public RecursiveExactVCImpl​(Graph<V,​E> graph)
        Constructs a new GreedyVCImpl instance
        Parameters:
        graph - input graph

      • RecursiveExactVCImpl

        public RecursiveExactVCImpl​(Graph<V,​E> graph,
                            java.util.Map<V,​java.lang.Double> vertexWeightMap)
        Constructs a new GreedyVCImpl instance
        Parameters:
        graph - input graph
        vertexWeightMap - mapping of vertex weights

    • Method Detail

      • calculateCoverRecursively

        private RecursiveExactVCImpl.BitSetCover calculateCoverRecursively​(int indexNextCandidate,
                                                                   java.util.BitSet visited,
                                                                   double accumulatedWeight)

      • getWeight

        private double getWeight​(java.util.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?