jopt.csp.spi
Class AC1

java.lang.Object
  extended byjopt.csp.spi.arcalgorithm.ArcBasedAcAlg
      extended byjopt.csp.spi.AC1
All Implemented Interfaces:
ChoicePointAlgorithm, jopt.csp.variable.CspAlgorithm, NodeArcGraphListener

public class AC1
extends ArcBasedAcAlg

Arc consistent algorithm based on the AC1 algorithm. This algorithm is both simple and extremely inefficient as it revisits all arcs if any node changed in the previous iteration. It is implemented only for demonstration and comparison with better arc algorithms, and it should not be used in production. Consistency in networks of Relations [AC1-3] A.K. Mackworth, in Artificial Intelligence 8, 99-118, 1977.


Constructor Summary
AC1()
          Creates an arc consistent strength algorithm
AC1(int strength)
          Creates algorithm with specified strength
 
Method Summary
 void arcAddedEvent(NodeArcGraph graph, Arc arc)
          Updates changed flag to true to allow next call to propagate to process arcs in graph
 void nodeChangedEvent(NodeArcGraph graph, NodeChangeEvent evt)
          Updates changed flag to true to allow next call to propagate to process arcs in graph
 void propagate()
          Propagates constraints added to algorithm reducing domains of variables to which constraints are applied.
 
Methods inherited from class jopt.csp.spi.arcalgorithm.ArcBasedAcAlg
addConstraint, addVariable, arcRemovedEvent, getProblemState, getVarFactory, nodeRemovedEvent, restoreProblemState, setChoicePointStack
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AC1

public AC1()
Creates an arc consistent strength algorithm


AC1

public AC1(int strength)
Creates algorithm with specified strength

See Also:
CspAlgorithmStrength
Method Detail

propagate

public void propagate()
               throws jopt.csp.variable.PropagationFailureException
Propagates constraints added to algorithm reducing domains of variables to which constraints are applied.

Throws:
jopt.csp.variable.PropagationFailureException - If unable to propagate constraints

arcAddedEvent

public void arcAddedEvent(NodeArcGraph graph,
                          Arc arc)
Updates changed flag to true to allow next call to propagate to process arcs in graph

Specified by:
arcAddedEvent in interface NodeArcGraphListener
Overrides:
arcAddedEvent in class ArcBasedAcAlg

nodeChangedEvent

public void nodeChangedEvent(NodeArcGraph graph,
                             NodeChangeEvent evt)
Updates changed flag to true to allow next call to propagate to process arcs in graph

Specified by:
nodeChangedEvent in interface NodeArcGraphListener
Overrides:
nodeChangedEvent in class ArcBasedAcAlg