import java.util.
ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import es.uma.ada.backtracking.Backtracking;
import es.uma.ada.datastructures.graph.Graph;
import es.uma.ada.datastructures.tuple.Pair;
import es.uma.ada.problem.combinatorial.set.vertexcover.VertexCover;
/**
* Uses backtracking to find a vertex cover
* @author ccottap
* @version 1.0
*/
public class VertexCoverBacktracking extends Backtracking {
/**
* the vertex cover instance to be solved
*/
private Graph<Integer> g;
/**
* maximum number of vertices in the cover
*/
private int k;
/**
* the solution found
*/
private Set<Integer> solution;
/**
* Sets the vertex cover instance to be solved, and uses the number of vertices
* as the maximum size of the vertex cover sought. This can be later changed
using the function
* {@link VertexCoverBacktracking#setMaxSize(int) setMaxSize}.
* @param g an undirected graph
*/
public void setInstance(Graph<Integer> g) {
this.g = g;
}
/**
* Sets the maximum size of the vertex cover
* @param k the maximum size of the vertex cover
*/
public void setMaxSize(int k) {
this.k = k;
}
@Override
protected Object initialState() {
// TODO create initial state
// Each node in the search tree represents a pair (S, v), where
// S is the current set of vertices and i is the next vertex to be considered
// TODO - returns the initial state
Set<Integer> initialSet=new HashSet<>(); //conjunto vacío de vértices
int initialVertex = 0; //primer vértice
return new Pair<>(initialSet, initialVertex);
}
@Override
protected boolean backtracking(Object state) {
@SuppressWarnings("unchecked")
Pair<Set<Integer>, Integer> p = (Pair<Set<Integer>, Integer>) state;
Set<Integer> partialSolution = p.getFirst();
int next = p.getSecond();
boolean ok = false;
nodes ++;
// TODO
if (partialSolution.size() > k) {
return false;
}
if (VertexCover.isSolution(g, partialSolution)) {
solution = new HashSet<>(partialSolution);
return true;
}
if (partialSolution.size() >= k || next > g.getVertices().size()) {
return false;
}
Set<Integer> uncoveredEdges = VertexCover.uncoveredEdges(g, next,
partialSolution);
if (uncoveredEdges.isEmpty()) {
return backtracking(new Pair<>(partialSolution, next + 1));
}
else {
Set<Integer> state1 = new HashSet<>(partialSolution);
state1.add(next);
Set<Integer> state2 = new HashSet<>(partialSolution);
state2.addAll(uncoveredEdges);
return backtracking(new Pair<>(state1, next + 1)) || backtracking(new
Pair<>(state2, next + 1));
}
@Override
public String getName() {
return "VertexCoverBacktracking";
}
/**
* Returns the solution found (null, if no solution was found)
* @return the solution found (null, if no solution was found)
*/
public Set<Integer> getSolution() {
return solution;
}
