JaCoP.util
Class MDD

java.lang.Object
  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:

3.1

Author:

Radoslaw Szymanek and Krzysztof Kuchcinski

Field Summary

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.
int	freePosition It specifies the first position in the array which is available for use.
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.
static int	startSize 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.
static java.lang.String[]	xmlAttributes It specifies the arguments required to be saved by an XML format as well as the constructor being called to recreate an object from an XML format.

Constructor Summary

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

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.
void	reduce() It reduces MDD to minimal size.
MDD	reuse(IntVar[] vars) If possible it will return an MDD which reuse an array representation of the current MDD.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, 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.

startSize

public static int startSize

The initial size of the array representing an MDD.

xmlAttributes

public static java.lang.String[] xmlAttributes

It specifies the arguments required to be saved by an XML format as well as the constructor being called to recreate an object from an XML format.

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.

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.

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.

reduce

public void reduce()

It reduces MDD to minimal size.

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