net.sf.cpsolver.ifs.extension
Class MacRevised

java.lang.Object
  net.sf.cpsolver.ifs.extension.Extension
      net.sf.cpsolver.ifs.extension.MacRevised

All Implemented Interfaces:

ModelListener

public class MacRevised
extends Extension

Another implementation of MAC propagation.

Version:

IFS 1.1 (Iterative Forward Search)
Copyright (C) 2006 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

See Also:

MacPropagation

Field Summary

protected Vector	iConstraints List of constraints on which arc-consistency is to be maintained
protected long	iIteration Current iteration

Constructor Summary

MacRevised(Solver solver, DataProperties properties)
Constructor

Method Summary

void	addConstraint(Constraint constraint) Adds a constraint on which arc-consistency is to be maintained
void	afterAssigned(long iteration, Value value) After a value is assigned: explanations of other values of the value's variable are reset (to contain only the assigned value), propagation over the assigned variable takes place.
void	afterUnassigned(long iteration, Value value) After a value is unassigned: explanations of all values of unassigned variable are recomputed (Value.conflicts()), propagation undo over the unassigned variable takes place.
void	beforeAssigned(long iteration, Value value) Before a value is unassigned: until the value is inconsistent with the current solution, an assignment from its explanation is picked and unassigned.
boolean	contains(Constraint constraint) Returns true, if arc-consistency is to be maintained on the given constraint
HashSet	explanation(Constraint constraint, Value value, Variable variable)
Set	goodValues(Variable variable) good values of a variable (values not removed from variables domain)
boolean	hasSupport(Constraint constraint, Value value, Variable variable)
boolean	init(Solver solver) Initialization.
boolean	isGood(Value value) is variable good
Set	noGood(Value value) variables explanation
void	propagate(Constraint constraint, Value noGoodValue, Vector queue)
void	propagate(Vector queue)
boolean	revise(Constraint constraint, Value value)
boolean	revise(Value value)
protected void	setGood(Value value) sets value to be good
void	setNoGood(Value value, Set reason) sets value's explanation
HashSet	supports(Constraint constraint, Value value, Variable variable)

Methods inherited from class net.sf.cpsolver.ifs.extension.Extension

beforeUnassigned, constraintAdded, constraintRemoved, getModel, getProperties, getSolver, isRegistered, register, unregister, useValueExtra, useVariableExtra, variableAdded, variableRemoved

Methods inherited from class java.lang.Object

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

Field Detail

iConstraints

protected Vector iConstraints

List of constraints on which arc-consistency is to be maintained

iIteration

protected long iIteration

Current iteration

Constructor Detail

MacRevised

public MacRevised(Solver solver,
                  DataProperties properties)

Constructor

Method Detail

addConstraint

public void addConstraint(Constraint constraint)

Adds a constraint on which arc-consistency is to be maintained

contains

public boolean contains(Constraint constraint)

Returns true, if arc-consistency is to be maintained on the given constraint

beforeAssigned

public void beforeAssigned(long iteration,
                           Value value)

Before a value is unassigned: until the value is inconsistent with the current solution, an assignment from its explanation is picked and unassigned.

Specified by:

beforeAssigned in interface ModelListener

Overrides:

beforeAssigned in class Extension

Parameters:

iteration - current iteration

value - value to be assigned

afterAssigned

public void afterAssigned(long iteration,
                          Value value)

After a value is assigned: explanations of other values of the value's variable are reset (to contain only the assigned value), propagation over the assigned variable takes place.

Specified by:

afterAssigned in interface ModelListener

Overrides:

afterAssigned in class Extension

Parameters:

iteration - current iteration

value - value to be assigned

afterUnassigned

public void afterUnassigned(long iteration,
                            Value value)

After a value is unassigned: explanations of all values of unassigned variable are recomputed (Value.conflicts()), propagation undo over the unassigned variable takes place.

Specified by:

afterUnassigned in interface ModelListener

Overrides:

afterUnassigned in class Extension

Parameters:

iteration - current iteration

value - value to be unassigned

propagate

public void propagate(Vector queue)

propagate

public void propagate(Constraint constraint,
                      Value noGoodValue,
                      Vector queue)

revise

public boolean revise(Value value)

revise

public boolean revise(Constraint constraint,
                      Value value)

explanation

public HashSet explanation(Constraint constraint,
                           Value value,
                           Variable variable)

supports

public HashSet supports(Constraint constraint,
                        Value value,
                        Variable variable)

hasSupport

public boolean hasSupport(Constraint constraint,
                          Value value,
                          Variable variable)

init

public boolean init(Solver solver)

Initialization. Enforce arc-consistency over the current (initial) solution. AC3 algorithm is used.

Specified by:

init in interface ModelListener

Overrides:

init in class Extension

Parameters:

solver - IFS solver

goodValues

public Set goodValues(Variable variable)

good values of a variable (values not removed from variables domain)

noGood

public Set noGood(Value value)

variables explanation

isGood

public boolean isGood(Value value)

is variable good

setGood

protected void setGood(Value value)

sets value to be good

setNoGood

public void setNoGood(Value value,
                      Set reason)

sets value's explanation