Class MDD


  • public class MDD
    extends java.lang.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.8
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static boolean debugAll  
      int[] diagram
      For each node at given index i-th it specifies all possible outgoing edges.
      int[] domainLimits
      The initial domain limits used to create an MDD array representation.
      private boolean extendable
      It creates and MDD representation given the list of variables.
      int freePosition
      It specifies the first position in the array which is available for use.
      (package private) java.util.List<java.lang.Integer>[][] id  
      (package private) int memorySavings  
      static 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.
      (package private) java.util.TreeMap<java.lang.Integer,​java.lang.Integer> reducedNodes  
      (package private) java.util.List<int[]>[][] same  
      static int START_SIZE
      The initial size of the array representing an MDD.
      static int TERMINAL
      It specifies an identifier which denotes a terminal node.
      IntVar[] vars
      The ordered list of variables participating in MDD.
      IndexDomainView[] views
      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

      All Methods Instance Methods Concrete Methods 
      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 checkIfAllowed()  
      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 reduce()
      It reduces MDD to minimal size.
      private int reduce​(int node, int level)  
      MDD reuse​(IntVar[] vars)
      If possible it will return an MDD which reuse an array representation of the current MDD.
      private void shrink()  
      java.lang.String toString()  
      • Methods inherited from class java.lang.Object

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

      • TERMINAL

        public static final int TERMINAL
        It specifies an identifier which denotes a terminal node.
        See Also:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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:
        Constant Field Values
      • 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

        java.util.List<int[]>[][] same
      • id

        java.util.List<java.lang.Integer>[][] id
      • reducedNodes

        java.util.TreeMap<java.lang.Integer,​java.lang.Integer> reducedNodes
      • memorySavings

        int memorySavings
    • Constructor Detail

      • 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 Detail

      • 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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object