- 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>
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)$
-
-
Nested Class Summary
Nested Classes Modifier and Type Class 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.VertexCoverAlgorithm
VertexCoverAlgorithm.VertexCover<V>, VertexCoverAlgorithm.VertexCoverImpl<V>
-
-
Field Summary
Fields Modifier and Type Field Description private Graph<V,E>
graph
Input graphprivate java.util.Map<java.util.BitSet,RecursiveExactVCImpl.BitSetCover>
memo
Map for memoizationprivate int
n
Number of vertices in the graphprivate NeighborCache<V,E>
neighborCache
Neighbor cache TODO JK: It might be worth trying to replace the neighbors index by a bitset view.private double
upperBoundOnVertexCoverWeight
Maximum weight of the vertex cover.private java.util.Map<V,java.lang.Integer>
vertexIDDictionary
Mapping of a vertex to its index in the list of verticesprivate java.util.Map<V,java.lang.Double>
vertexWeightMap
private java.util.List<V>
vertices
Ordered list of vertices which will be iteratively considered to be included in a matchingprivate boolean
weighted
Indicates whether we are solving a weighted or unweighted version of the problem
-
Constructor Summary
Constructors Constructor Description RecursiveExactVCImpl(Graph<V,E> graph)
Constructs a new GreedyVCImpl instanceRecursiveExactVCImpl(Graph<V,E> graph, java.util.Map<V,java.lang.Double> vertexWeightMap)
Constructs a new GreedyVCImpl instance
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private RecursiveExactVCImpl.BitSetCover
calculateCoverRecursively(int indexNextCandidate, java.util.BitSet visited, double accumulatedWeight)
private double
calculateUpperBound()
Calculates a cheap upper bound on the optimum solution.VertexCoverAlgorithm.VertexCover<V>
getVertexCover()
Computes a vertex cover.private double
getWeight(java.util.Collection<V> vertices)
Returns the weight of a collection of vertices.
-
-
-
Field Detail
-
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 java.util.Map<java.util.BitSet,RecursiveExactVCImpl.BitSetCover> memo
Map for memoization
-
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
-
-
Method Detail
-
getVertexCover
public VertexCoverAlgorithm.VertexCover<V> getVertexCover()
Description copied from interface:VertexCoverAlgorithm
Computes a vertex cover.- Specified by:
getVertexCover
in interfaceVertexCoverAlgorithm<V>
- Returns:
- a vertex cover
-
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?
-
-