Class MVCConstructive

java.lang.Object

es.urjc.etsii.grafo.create.Constructive<MSTSolution, MSTInstance>

es.urjc.etsii.grafo.algorithms.cmsa.CMSAConstructive<MSTSolution, MSTInstance, Integer>

es.urjc.etsii.grafo.graphs.mvc.MVCConstructive

public class MVCConstructive
extends CMSAConstructive<MSTSolution, MSTInstance, Integer>

Probabilistic constructive method for the Minimum Vertex Cover (MVC) problem, used as the "Construct" step of the CMSA demo in this project.

Repeatedly picks a random still-uncovered edge, and adds one of its endpoints to the cover, biased towards the endpoint with the highest degree (as in the classic greedy vertex cover heuristic), but not always: this randomization is what allows CMSA to sample different, varied vertex subsets across iterations to build the sub-instance.

Nested Class Summary

Nested classes/interfaces inherited from class Constructive

Constructive.NullConstructive<S,I>

Constructor Summary

Constructors

Constructor	Description
MVCConstructive()
MVCConstructive(double greedyBias)

Method Summary

Modifier and Type	Method	Description
MSTSolution	construct(MSTSolution solution)	Build a solution.
String	toString()
Set<Integer>	usedComponents(MSTSolution solution)	Returns the solution components used to build the given solution.

Methods inherited from class Constructive

nul

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Details

MVCConstructive

public MVCConstructive()

MVCConstructive

@AutoconfigConstructor
public MVCConstructive(@RealParam(min=0.0,max=1.0)
 double greedyBias)

Method Details

construct

public MSTSolution construct(MSTSolution solution)

Description copied from class: Constructive

Build a solution. Start with an empty solution, end when the solution is valid.

Specified by:

construct in class Constructive<MSTSolution, MSTInstance>

Parameters:

solution - Empty solution, the result of calling the constructor.

Returns:

A valid solution that fulfills all the problem constraints.

usedComponents

public Set<Integer> usedComponents(MSTSolution solution)

Description copied from class: CMSAConstructive

Returns the solution components used to build the given solution. This method is usually called immediately after Constructive.construct(Solution), but implementations should not assume this and must be able to work with any feasible solution to the problem, as it is also used to identify which components are part of the solution returned by the CMSASolver.

Specified by:

usedComponents in class CMSAConstructive<MSTSolution, MSTInstance, Integer>

Parameters:

solution - a feasible solution to the problem

Returns:

the set of solution components used in the given solution

toString

public String toString()

Description copied from class: Constructive

Overrides:

toString in class Constructive<MSTSolution, MSTInstance>