Package org.ddolib.examples.misp

Class MispDominance

java.lang.Object

org.ddolib.examples.misp.MispDominance

All Implemented Interfaces:

Dominance<BitSet>

public class MispDominance
extends Object
implements Dominance<BitSet>

Implementation of a dominance relation for the Maximum Independent Set Problem (MISP).

In this context, one state state1 is considered dominated by another state state2 if all vertices selected in state1 are also selected in state2. This allows pruning suboptimal states during the search.

Constructor Summary

Constructors

Constructor	Description
MispDominance()

Method Summary

Modifier and Type	Method	Description
Integer	getKey(BitSet state)	Returns a key for the dominance relation.
boolean	isDominatedOrEqual(BitSet state1, BitSet state2)	Determines whether state1 is dominated by or equal to state2.

Methods inherited from class java.lang.Object

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

Constructor Details

MispDominance

public MispDominance()

Method Details

getKey

public Integer getKey(BitSet state)

Returns a key for the dominance relation.

This implementation always returns 0 since no partitioning of states is needed based on a specific key.

Specified by:

getKey in interface Dominance<BitSet>

Parameters:

state - the current state

Returns:

a key for the dominance relation

isDominatedOrEqual

public boolean isDominatedOrEqual(BitSet state1,
 BitSet state2)

Determines whether state1 is dominated by or equal to state2.

A state state1 is dominated by state2 if all vertices selected in state1 are also selected in state2.

Specified by:

isDominatedOrEqual in interface Dominance<BitSet>

Parameters:

state1 - the first state to compare

state2 - the second state to compare

Returns:

true if state1 is dominated by or equal to state2, false otherwise