Package org.jacop.util
Class MDD
- java.lang.Object
-
- org.jacop.util.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()
-
-
-
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
-
debugAll
private static final boolean debugAll
- 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 classjava.lang.Object
-
-