Class MDD

java.lang.Object
org.jacop.util.MDD

public class MDD extends Object
Defines an MDD as used in the following paper.

K.C. Cheng and R.H. Yap, "Maintaining generalized arc consistency on ad-hoc n-ary constraints.", CP 2008.

Version:
4.9
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final boolean
     
    int[]
    For each node at given index i-th it specifies all possible outgoing edges.
    int[]
    The initial domain limits used to create an MDD array representation.
    private boolean
    It creates and MDD representation given the list of variables.
    int
    It specifies the first position in the array which is available for use.
    (package private) List<Integer>[][]
     
    (package private) int
     
    static final int
    It specifies an identifier which denotes lack of the edge for a given value (in the context of the current level (variable) of an MDD.
    (package private) TreeMap<Integer,Integer>
     
    (package private) List<int[]>[][]
     
    static final int
    The initial size of the array representing an MDD.
    static final int
    It specifies an identifier which denotes a terminal node.
    The ordered list of variables participating in MDD.
    It creates index domain views so operations based on indexes of values can be performed efficiently.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    MDD()
     
     
    MDD(IntVar[] vars)
    It creates and MDD representation given the list of variables.
     
    MDD(IntVar[] vars, int[][] table)
    It creates and MDD representation given the list of variables and (dis)allowed tuples.
     
    MDD(IntVar[] vars, int[] diagram, int[] domainLimits)
    It creates an MDD.
     
    MDD(IntVar[] vars, int[] minimumDomainLimits, int[][] table)
    It creates and MDD representation given the list of variables and (dis)allowed tuples.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addTuple(int[] tuple)
    It allows to add one by one tuple before the reduction of the initial MDD takes place.
    boolean
     
    boolean
    checkIfAllowed(int[] tuple)
    It checks if the specified tuple is allowed.
    void
    ensureSize(int size)
    It makes sure that diagram uses an array of at least given size.
    int
    findPosition(int value, int[] values)
    It finds a position of a value inside the array.
    protected int
    findRange(int value, int[] values)
     
    private void
    mtree(int[][] table)
     
    void
    It reduces MDD to minimal size.
    private int
    reduce(int node, int level)
     
    reuse(IntVar[] vars)
    If possible it will return an MDD which reuse an array representation of the current MDD.
    private void
     
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Field Details

    • TERMINAL

      public static final int TERMINAL
      It specifies an identifier which denotes a terminal node.
      See Also:
    • NOEDGE

      public static final int NOEDGE
      It specifies an identifier which denotes lack of the edge for a given value (in the context of the current level (variable) of an MDD.
      See Also:
    • debugAll

      private static final boolean debugAll
      See Also:
    • vars

      public IntVar[] vars
      The ordered list of variables participating in MDD.
    • domainLimits

      public int[] domainLimits
      The initial domain limits used to create an MDD array representation.
    • diagram

      public int[] diagram
      For each node at given index i-th it specifies all possible outgoing edges. If there was no edge for a value of the variable associated to the current node then the entry corresponding to that value is set to NOEDGE. If a given path specifies an allowed tuple than it is terminated with a terminal node.
    • views

      public IndexDomainView[] views
      It creates index domain views so operations based on indexes of values can be performed efficiently.
    • freePosition

      public int freePosition
      It specifies the first position in the array which is available for use.
    • START_SIZE

      public static final int START_SIZE
      The initial size of the array representing an MDD.
      See Also:
    • extendable

      private boolean extendable
      It creates and MDD representation given the list of variables. Tuples must be added manually (addTuple function). After all tuples are added reduce function can be called to reduce MDD. After reducing MDD adding tuples is not allowed to maintain cannonic and minimal representation.
    • same

      List<int[]>[][] same
    • id

      List<Integer>[][] id
    • reducedNodes

      TreeMap<Integer,Integer> reducedNodes
    • memorySavings

      int memorySavings
  • Constructor Details

    • MDD

      public MDD(IntVar[] vars, int[] diagram, int[] domainLimits)
      It creates an MDD. Please note that diagram argument which is potentially a very large array and can be used across many constraints is not copied by the constructor but used directly.
      Parameters:
      vars - variables involved in this multiple-value decision diagram.
      diagram - an int array representation of the diagram.
      domainLimits - the limits on the number of values imposed on each variable.
    • MDD

      public MDD(IntVar[] vars, int[] minimumDomainLimits, int[][] table)
      It creates and MDD representation given the list of variables and (dis)allowed tuples. Minimum domain limits allows artificially increase the size of the variable domain to make reuse of the same mdd across multiple constraints possible.
      Parameters:
      vars - variables and their order used in the MDD.
      minimumDomainLimits - it specifies the minimal number of values used for each of the variables.
      table - it specifies the allowed tuples which are being converted into an MDD.
    • MDD

      public MDD(IntVar[] vars, int[][] table)
      It creates and MDD representation given the list of variables and (dis)allowed tuples. Minimum domain limits allows artificially increase the size of the variable domain to make reuse of the same mdd across multiple constraints possible.
      Parameters:
      vars - variables and their order used in the MDD.
      table - it specifies the allowed tuples which are being converted into an MDD.
    • MDD

      public MDD(IntVar[] vars)
      It creates and MDD representation given the list of variables. The domain limits are set to be equal to the size of the variables domains. The tuples are being added separately one by one.
      Parameters:
      vars - variables and their order used in the MDD.
    • MDD

      protected MDD()
  • Method Details

    • reuse

      public MDD reuse(IntVar[] vars)
      If possible it will return an MDD which reuse an array representation of the current MDD. It returns null if one of the variables supplied has a larger domain then assumed by respective variable from this MDD. In order to make reuse possible first create MDD for largest size variables.
      Parameters:
      vars - array of new variables for which this MDD is being reused for.
      Returns:
      an MDD with parts of it reused for new variables.
    • addTuple

      public void addTuple(int[] tuple)
      It allows to add one by one tuple before the reduction of the initial MDD takes place.
      Parameters:
      tuple - an allowed tuple being added to MDD.
    • ensureSize

      public void ensureSize(int size)
      It makes sure that diagram uses an array of at least given size.
      Parameters:
      size - the size the array must be at least of.
    • shrink

      private void shrink()
    • mtree

      private void mtree(int[][] table)
    • findPosition

      public int findPosition(int value, int[] values)
      It finds a position of a value inside the array.
      Parameters:
      value - the value being searched.
      values - the array in which the value is being searched for.
      Returns:
      position of the value in the array.
    • findRange

      protected int findRange(int value, int[] values)
    • reduce

      public void reduce()
      It reduces MDD to minimal size.
    • reduce

      private int reduce(int node, int level)
    • checkIfAllowed

      public boolean checkIfAllowed(int[] tuple)
      It checks if the specified tuple is allowed.
      Parameters:
      tuple - the tuple being checked.
      Returns:
      true if the tuple is allowed, false otherwise.
    • checkIfAllowed

      public boolean checkIfAllowed()
      Returns:
      true only if all variables are grounded and the values assigned to variables are allowed by a MDD.
    • toString

      public String toString()
      Overrides:
      toString in class Object