net.sf.cpsolver.ifs.extension
Class MacRevised<V extends Variable<V,T>,T extends Value<V,T>>

java.lang.Object
  extended by net.sf.cpsolver.ifs.extension.Extension<V,T>
      extended by net.sf.cpsolver.ifs.extension.MacRevised<V,T>
All Implemented Interfaces:
ModelListener<V,T>

public class MacRevised<V extends Variable<V,T>,T extends Value<V,T>>
extends Extension<V,T>

Another implementation of MAC propagation.

Version:
IFS 1.2 (Iterative Forward Search)
Copyright (C) 2006 - 2010 Tomas Muller
muller@unitime.org
http://muller.unitime.org

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 3 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 see http://www.gnu.org/licenses/.
See Also:
MacPropagation

Field Summary
protected  List<Constraint<V,T>> iConstraints
          List of constraints on which arc-consistency is to be maintained
protected  long iIteration
          Current iteration
 
Constructor Summary
MacRevised(Solver<V,T> solver, DataProperties properties)
          Constructor
 
Method Summary
 void addConstraint(Constraint<V,T> constraint)
          Adds a constraint on which arc-consistency is to be maintained
 void afterAssigned(long iteration, T 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, T 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, T 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<V,T> constraint)
          Returns true, if arc-consistency is to be maintained on the given constraint
 Set<T> explanation(Constraint<V,T> constraint, T value, V variable)
           
 Set<T> goodValues(V variable)
          good values of a variable (values not removed from variables domain)
 boolean hasSupport(Constraint<V,T> constraint, T value, V variable)
           
 boolean init(Solver<V,T> solver)
          Initialization.
 boolean isGood(T value)
          is variable good
 Set<T> noGood(T value)
          variables explanation
 void propagate(Constraint<V,T> constraint, T noGoodValue, List<T> queue)
           
 void propagate(List<T> queue)
           
 boolean revise(Constraint<V,T> constraint, T value)
           
 boolean revise(T value)
           
protected  void setGood(T value)
          sets value to be good
 void setNoGood(T value, Set<T> reason)
          sets value's explanation
 Set<T> supports(Constraint<V,T> constraint, T value, V 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 List<Constraint<V extends Variable<V,T>,T extends Value<V,T>>> iConstraints
List of constraints on which arc-consistency is to be maintained


iIteration

protected long iIteration
Current iteration

Constructor Detail

MacRevised

public MacRevised(Solver<V,T> solver,
                  DataProperties properties)
Constructor

Method Detail

addConstraint

public void addConstraint(Constraint<V,T> constraint)
Adds a constraint on which arc-consistency is to be maintained


contains

public boolean contains(Constraint<V,T> constraint)
Returns true, if arc-consistency is to be maintained on the given constraint


beforeAssigned

public void beforeAssigned(long iteration,
                           T 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<V extends Variable<V,T>,T extends Value<V,T>>
Overrides:
beforeAssigned in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
iteration - current iteration
value - value to be assigned

afterAssigned

public void afterAssigned(long iteration,
                          T 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<V extends Variable<V,T>,T extends Value<V,T>>
Overrides:
afterAssigned in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
iteration - current iteration
value - value to be assigned

afterUnassigned

public void afterUnassigned(long iteration,
                            T 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<V extends Variable<V,T>,T extends Value<V,T>>
Overrides:
afterUnassigned in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
iteration - current iteration
value - value to be unassigned

propagate

public void propagate(List<T> queue)

propagate

public void propagate(Constraint<V,T> constraint,
                      T noGoodValue,
                      List<T> queue)

revise

public boolean revise(T value)

revise

public boolean revise(Constraint<V,T> constraint,
                      T value)

explanation

public Set<T> explanation(Constraint<V,T> constraint,
                          T value,
                          V variable)

supports

public Set<T> supports(Constraint<V,T> constraint,
                       T value,
                       V variable)

hasSupport

public boolean hasSupport(Constraint<V,T> constraint,
                          T value,
                          V variable)

init

public boolean init(Solver<V,T> solver)
Initialization. Enforce arc-consistency over the current (initial) solution. AC3 algorithm is used.

Specified by:
init in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
Overrides:
init in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
solver - IFS solver

goodValues

public Set<T> goodValues(V variable)
good values of a variable (values not removed from variables domain)


noGood

public Set<T> noGood(T value)
variables explanation


isGood

public boolean isGood(T value)
is variable good


setGood

protected void setGood(T value)
sets value to be good


setNoGood

public void setNoGood(T value,
                      Set<T> reason)
sets value's explanation



Copyright © 2014 UniTime LLC. All Rights Reserved.