org.cpsolver.ifs.extension

## Class MacPropagation<V extends Variable<V,T>,T extends Value<V,T>>

- java.lang.Object
- - org.cpsolver.ifs.extension.Extension<V,T>
  - - org.cpsolver.ifs.assignment.context.ExtensionWithContext<V,T,MacPropagation.NoGood>
    - - org.cpsolver.ifs.extension.MacPropagation<V,T>

- Type Parameters:
    `V` - Variable
    `T` - Value
  All Implemented Interfaces:
    CanHoldContext, HasAssignmentContext<V,T,MacPropagation.NoGood>, ModelListener<V,T>
  Direct Known Subclasses:
    DbtPropagation

      public class MacPropagation<V extends Variable<V,T>,T extends Value<V,T>>
      extends ExtensionWithContext<V,T,MacPropagation.NoGood>

  MAC propagation.
  During the arc consistency maintenance, when a value is deleted from a variable's domain, the reason (forming an explanation) can be computed and attached to the deleted value. Once a variable (say Vx with the assigned value vx) is unassigned during the search, all deleted values which contain a pair Vx = vx in their explanations need to be recomputed. Such value can be either still inconsistent with the current (partial) solution (a different explanation is attached to it in this case) or it can be returned back to its variable's domain. Arc consistency is maintained after each iteration step, i.e., the selected assignment is propagated into the not yet assigned variables. When a value vx is assigned to a variable Vx, an explanation Vx != vx' ← Vx = vx is attached to all values vx' of the variable Vx, different from vx.
  In the case of forward checking (only constraints going from assigned variables to unassigned variables are revised), computing explanations is rather easy. A value vx is deleted from the domain of the variable Vx only if there is a constraint which prohibits the assignment Vx=vx because of the existing assignments (e.g., Vy = vy, Vz = vz). An explanation for the deletion of this value vx is then Vx != vx ← (Vy = vy & ... Vz = vz), where Vy = vy & ... Vz = vz are assignments contained in the prohibiting constraint. In case of arc consistency, a value vx is deleted from the domain of the variable Vx if there is a constraint which does not permit the assignment Vx = vx with other possible assignments of the other variables in the constraint. This means that there is no support value (or combination of values) for the value vx of the variable Vx in the constraint. An explanation is then a union of explanations of all possible support values for the assignment Vx = vx of this constraint which were deleted. The reason is that if one of these support values is returned to its variable's domain, this value vx may be returned as well (i.e., the reason for its deletion has vanished, a new reason needs to be computed).
  As for the implementation, we only need to enforce arc consistency of the initial solution and to extend unassign and assign methods. Procedure `afterAssigned(Assignment, long, Value)` enforces arc consistency of the solution with the selected assignment variable = value and the procedure `afterUnassigned(Assignment, long, Value)` "undoes" the assignment variable = value. It means that explanations of all values which were deleted and which contain assignment variable = value in their explanations need to be recomputed. This can be done via returning all these values into their variables' domains followed by arc consistency maintenance over their variables.
  Parameters:

  Related Solver Parameters
  Parameter | Type | Comment
  --- | --- | ---
  MacPropagation.JustForwardCheck | `Boolean` | If true, only forward checking instead of full arc consistency is maintained during the search.

  Version:
    IFS 1.3 (Iterative Forward Search)
    Copyright (C) 2006 - 2014 Tomáš Müller
    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/.
  Author:
    Tomáš Müller

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `class` | `MacPropagation.NoGood` Assignment context

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected List<Constraint<V,T>>` | `iConstraints` List of constraints on which arc-consistency is to be maintained
    `protected long` | `iIteration` Current iteration

    - ### Fields inherited from interface org.cpsolver.ifs.assignment.context.CanHoldContext

      `sMaxSize`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `MacPropagation(Solver<V,T> solver, DataProperties properties)` Constructor

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `addConstraint(Constraint<V,T> constraint)` Adds a constraint on which arc-consistency is to be maintained
    `void` | `afterAssigned(Assignment<V,T> assignment, 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(Assignment<V,T> assignment, long iteration, T value)` After a value is unassigned: explanations of all values of unassigned variable are recomputed (`Value.conflicts(Assignment)`), propagation undo over the unassigned variable takes place.
    `void` | `beforeAssigned(Assignment<V,T> assignment, 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
    `MacPropagation.NoGood` | `createAssignmentContext(Assignment<V,T> assignment)` Create a new assignment context for the given assignment.
    `Set<T>` | `goodValues(Assignment<V,T> assignment, V variable)` good values of a variable (values not removed from variables domain)
    `boolean` | `isGood(Assignment<V,T> assignment, T value)` is variable good
    `Set<T>` | `noGood(Assignment<V,T> assignment, T value)` variables explanation
    `protected void` | `propagate(Assignment<V,T> assignment, V variable)` Propagation over the given variable.
    `protected void` | `setGood(Assignment<V,T> assignment, T value)` sets value to be good
    `void` | `setNoGood(Assignment<V,T> assignment, T value, Set<T> reason)` sets value's explanation
    `void` | `undoPropagate(Assignment<V,T> assignment, V variable)` Propagation undo over the given variable.

    - ### Methods inherited from class org.cpsolver.ifs.assignment.context.ExtensionWithContext

      `getAssignmentContextReference, getContext, getContext, init, setAssignmentContextReference, unregister`

    - ### Methods inherited from class org.cpsolver.ifs.extension.Extension

      `beforeUnassigned, constraintAdded, constraintRemoved, getModel, getProperties, getSolver, isRegistered, register, 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

    - #### MacPropagation

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

      Constructor
      Parameters:
        `solver` - current solver
        `properties` - solver configuration

  - ### Method Detail

    - #### addConstraint

          public void addConstraint(Constraint<V,T> constraint)

      Adds a constraint on which arc-consistency is to be maintained
      Parameters:
        `constraint` - a hard constraint

    - #### contains

          public boolean contains(Constraint<V,T> constraint)

      Returns true, if arc-consistency is to be maintained on the given constraint
      Parameters:
        `constraint` - a constraint
      Returns:
        true if in the set

    - #### beforeAssigned

          public void beforeAssigned(Assignment<V,T> assignment,
                                     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:
        `assignment` - current assignment
        `iteration` - current iteration
        `value` - value to be assigned

    - #### afterAssigned

          public void afterAssigned(Assignment<V,T> assignment,
                                    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:
        `assignment` - current assignment
        `iteration` - current iteration
        `value` - value to be assigned

    - #### afterUnassigned

          public void afterUnassigned(Assignment<V,T> assignment,
                                      long iteration,
                                      T value)

      After a value is unassigned: explanations of all values of unassigned variable are recomputed (`Value.conflicts(Assignment)`), 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:
        `assignment` - current assignment
        `iteration` - current iteration
        `value` - value to be unassigned

    - #### goodValues

          public Set<T> goodValues(Assignment<V,T> assignment,
                                   V variable)

      good values of a variable (values not removed from variables domain)
      Parameters:
        `assignment` - current assignment
        `variable` - given variable
      Returns:
        set of good values

    - #### noGood

          public Set<T> noGood(Assignment<V,T> assignment,
                               T value)

      variables explanation
      Parameters:
        `assignment` - current assignment
        `value` - given value
      Returns:
        no-good for the value

    - #### isGood

          public boolean isGood(Assignment<V,T> assignment,
                                T value)

      is variable good
      Parameters:
        `assignment` - current assignment
        `value` - given value
      Returns:
        true if there is no no-good set for the value

    - #### setGood

          protected void setGood(Assignment<V,T> assignment,
                                 T value)

      sets value to be good
      Parameters:
        `assignment` - current assignment
        `value` - given value

    - #### setNoGood

          public void setNoGood(Assignment<V,T> assignment,
                                T value,
                                Set<T> reason)

      sets value's explanation
      Parameters:
        `assignment` - current assignment
        `value` - given value
        `reason` - no-good set for the value

    - #### createAssignmentContext

          public MacPropagation.NoGood createAssignmentContext(Assignment<V,T> assignment)

      Description copied from interface: `HasAssignmentContext`
      Create a new assignment context for the given assignment. If there are already some variables assigned in the value, the method should make sure that the context is appropriately initialized.
      Parameters:
        `assignment` - an assignment for which there needs to be an assignment context
      Returns:
        a new instance of the assignment context, filled according to the given assignment

    - #### propagate

          protected void propagate(Assignment<V,T> assignment,
                                   V variable)

      Propagation over the given variable.
      Parameters:
        `assignment` - current assignment
        `variable` - given variable

    - #### undoPropagate

          public void undoPropagate(Assignment<V,T> assignment,
                                    V variable)

      Propagation undo over the given variable. All values having given variable in their explanations needs to be recomputed. This is done in two phases: 1) values that contain this variable in explanation are returned back to domains (marked as good) 2) propagation over variables which contains a value that was marked as good takes place
      Parameters:
        `assignment` - current assignment
        `variable` - given variable