CSPGen
Class Problem

java.lang.Object
  CSPGen.Problem

public class Problem

extends java.lang.Object

Problem class is the generator of flawless Random CSPs. This generator is based on the paper "Random constraint satisfaction: Flaws and structure" by Gent et al.,1998. To call the constructor of this class, you need to know five parameters. The first is a random seed which should be a long value, the main reason to use this parameter is to keep track of generated solvable instances. The second parameter is variable numbers of this problem and the third parameter is the domain size of this problem. the fourth parameter will decide the possibility that there exists one constraint between two variables and the fifth parameter will decide the possibility that one constraint will be "satisfied". After calling the constructor, you will get an instance of CSP. In this instance, there will be five public field which will help people to access this problem.They are: size, the variable number of this problem; domainSize, the domain size of this problem; 2D array constraints, which will tell if there exist a binaryconstraint between two variables;Arraylist allconstraints, which is the list of all constraints in this problem; Array Variable, which is the list of all variables in this problem.

Field Summary

protected java.util.ArrayList	allConstraints An array to record all the constraints in this problem.
protected boolean[][]	constrained An array to record if there is one constraint between two variables.
protected BinaryConstraint[][]	constraints Records the same information as the constrained table except in the form of pointers to the actual BinaryConstraint instances.
int	domainSize The domain size of the problem.
double	p1 The first parameter, as in the constructor of this class.
double	p2 The second parameter, as in the constructor of this class.
long	Seed The seed value used in the random number generator.
int	size The number of variables in the problem.
protected Variable[]	variables An arrary of all the Variables in this problem.

Constructor Summary

Problem(long randSeed, int nbrOfVars, int domSize, double conrate, double fufillrate)
Class constructor,the main method to generate a new CSP with five parameters

Method Summary

protected void	addelEdges(int soFar, boolean add)
java.util.Enumeration	allConstraints() Returns an enumeration on all the constraints in the problem.
protected void	buildCompleteGraph() the method to build a graph that there is a constraint between any two variables
boolean	CheckConstrain(int variable1, int variable2, int value1, int value2) The method to judge if two values of two variables are consistent under the binary constraint between these two variables.
boolean	connected(int v1, int v2) Returns true if there is a a constraint between variable v1 and v2.
BinaryConstraint	connected(Variable v1, Variable v2) Returns the BinaryConstraint between v1 and v2 if one exists
protected void	connection(int v1, int v2, boolean conn) make the connection between two variables v1 and v2
Variable	getVariable(int i) Returns the Variable with the specified id.
protected void	initArrays(boolean edgeDefault) set all the edges of the graph to be true or false
static void	main(java.lang.String[] args) A testing method that generates 5 pre-set problems and prints a representation of each to the screen.
void	print() Prints out all the constraints in this problem, one per line, to the standard output.
protected void	setEdge(int v1, int v2, boolean[][] array) Deprecated. The BinaryConstraint class now handles these these details on the fly.
java.lang.String	toString() Returns a string representation of this problem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

size

public final int size

The number of variables in the problem.

domainSize

public final int domainSize

The domain size of the problem.

constrained

protected boolean[][] constrained

An array to record if there is one constraint between two variables.
constraints[x1][x2]==true means there is a constraint between variable v[x1] and variable v[x2]

constraints

protected BinaryConstraint[][] constraints

Records the same information as the constrained table except in the form of pointers to the actual BinaryConstraint instances.
null is used for false

See Also:

constrained

allConstraints

protected java.util.ArrayList allConstraints

An array to record all the constraints in this problem.

p1

public final double p1

The first parameter, as in the constructor of this class.

See Also:

Problem(long, int, int, double, double)

p2

public final double p2

The second parameter, as in the constructor of this class.

See Also:

Problem(long, int, int, double, double)

Seed

public final long Seed

The seed value used in the random number generator.

See Also:

Problem(long, int, int, double, double)

variables

protected Variable[] variables

An arrary of all the Variables in this problem.

Constructor Detail

Problem

public Problem(long randSeed,
               int nbrOfVars,
               int domSize,
               double conrate,
               double fufillrate)

Class constructor,the main method to generate a new CSP with five parameters

Parameters:

randSeed - the randomseed of the generated problem

nbrOfVars - number of variables

domSize - domain size of the problem

conrate - the parameter p1 of the problem,e.g. the possibility of there exist constraint between two variables

fufillrate - the parameter p2 of the problem, e.g. the possibility of one constraint be fulfilled.

Method Detail

initArrays

protected void initArrays(boolean edgeDefault)

set all the edges of the graph to be true or false

Parameters:

edgeDefault - the value which will be set to all edges of the graph.

connected

public boolean connected(int v1,
                         int v2)

Returns true if there is a a constraint between variable v1 and v2.

Parameters:

v1 - the id of a variable in the problem

v2 - the id of another variable in the problem

Returns:

true if there exists a constraint between variable v1 and v2, false otherwise.

connected

public BinaryConstraint connected(Variable v1,
                                  Variable v2)

Returns the BinaryConstraint between v1 and v2 if one exists.\

Parameters:

v1 - a variable in the problem

v2 - another variable in the problem

Returns:

The BinaryConstraint between the two variables or null if none exists.

addelEdges

protected void addelEdges(int soFar,
                          boolean add)

buildCompleteGraph

protected void buildCompleteGraph()

the method to build a graph that there is a constraint between any two variables

connection

protected void connection(int v1,
                          int v2,
                          boolean conn)
                   throws java.lang.IndexOutOfBoundsException

make the connection between two variables v1 and v2

Parameters:

v1 -

v2 -

conn - the parameter to tell if there exist a constraint between v1 and v2

Throws:

java.lang.IndexOutOfBoundsException

setEdge

protected void setEdge(int v1,
                       int v2,
                       boolean[][] array)

Deprecated. The BinaryConstraint class now handles these these details on the fly.

store the constraint into the variable data structure

Parameters:

v1 -

v2 -

array - the truth table of constraint between v1 and v2

Throws:

java.lang.IndexOutOfBoundsException

CheckConstrain

public boolean CheckConstrain(int variable1,
                              int variable2,
                              int value1,
                              int value2)

The method to judge if two values of two variables are consistent under the binary constraint between these two variables.

Parameters:

variable1 - the first variable to be assigned value

variable2 - the second variable to be assigned value

value1 - the value to be assigned to variable1

value2 - the value to be assigned to variable2

Returns:

true if variable1=value1 and variable2=value2 is consistent under the binary constraint between them.
false otherwise

allConstraints

public java.util.Enumeration allConstraints()

Returns an enumeration on all the constraints in the problem.

toString

public java.lang.String toString()

Returns a string representation of this problem. The returned string will have the format:

, <# of variables>, , ,

See Also:

Problem(long, int, int, double, double)

getVariable

public Variable getVariable(int i)

Returns the Variable with the specified id.

Parameters:

i - an id of a Variable in this problem

Throws:

ArrayOutOfBoundsException - if the given id does not exist in this problem.

print

public void print()

Prints out all the constraints in this problem, one per line, to the standard output.

See Also:

BinaryConstraint.toString()

main

public static void main(java.lang.String[] args)

A testing method that generates 5 pre-set problems and prints a representation of each to the screen.