java.lang.Object
org.jgrapht.alg.vertexcover.RecursiveExactVCImpl<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
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-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected class
Helper class which represents a vertex cover as a space efficient BitSetNested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexCoverAlgorithm
VertexCoverAlgorithm.VertexCover<V>, VertexCoverAlgorithm.VertexCoverImpl<V>
-
Field Summary
FieldsModifier and TypeFieldDescriptionInput graphprivate Map
<BitSet, RecursiveExactVCImpl<V, E>.BitSetCover> Map for memoizationprivate int
Number of vertices in the graphprivate NeighborCache
<V, E> Neighbor cache TODO JK: It might be worth trying to replace the neighbors index by a bitset view.private double
Maximum weight of the vertex cover.Mapping of a vertex to its index in the list of verticesOrdered list of vertices which will be iteratively considered to be included in a matchingprivate boolean
Indicates whether we are solving a weighted or unweighted version of the problem -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate RecursiveExactVCImpl<V,
E>.BitSetCover calculateCoverRecursively
(int indexNextCandidate, BitSet visited, double accumulatedWeight) private double
Calculates a cheap upper bound on the optimum solution.Computes a vertex cover.private double
getWeight
(Collection<V> vertices) Returns the weight of a collection of vertices.
-
Field Details
-
graph
Input graph -
n
private int nNumber of vertices in the graph -
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
Map for memoization -
vertices
Ordered list of vertices which will be iteratively considered to be included in a matching -
vertexIDDictionary
Mapping of a vertex to its index in the list of vertices -
upperBoundOnVertexCoverWeight
private double upperBoundOnVertexCoverWeightMaximum 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 weightedIndicates whether we are solving a weighted or unweighted version of the problem -
vertexWeightMap
-
-
Constructor Details
-
RecursiveExactVCImpl
Constructs a new GreedyVCImpl instance- Parameters:
graph
- input graph
-
RecursiveExactVCImpl
Constructs a new GreedyVCImpl instance- Parameters:
graph
- input graphvertexWeightMap
- mapping of vertex weights
-
-
Method Details
-
getVertexCover
Description copied from interface:VertexCoverAlgorithm
Computes a vertex cover.- Specified by:
getVertexCover
in interfaceVertexCoverAlgorithm<V>
- Returns:
- a vertex cover
-
calculateCoverRecursively
private RecursiveExactVCImpl<V,E>.BitSetCover calculateCoverRecursively(int indexNextCandidate, BitSet visited, double accumulatedWeight) -
getWeight
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?
-