frodo2.benchmarks.maxdiscsp.MaxDisCSPProblemGenerator Class Reference

Max-DisCSP problem generator. More...

Static Public Member Functions
static Document	createSizedRandProblem (int n, int k, double p1, double p2)
	Method to create a random, sized, uniform domain Max-DisCSP problem with a certain density and tightness.
static Element	createStats (String name, String value)
	Creates a "stats" element.
static Document	generateProblem (Graph graph, int k, double p1, double p2)
	Creates a problem description based on the input constraint graph.
static Hypercube< AddableInteger, AddableInteger >	randHypercube (List< String > variables, int k, double p2)
	Generates a random hypercube.
static void	main (String[] args)

Detailed Description

Max-DisCSP problem generator.

Such CSPs are characterized by the 4-tuple (n,k,p1,p2), where: n is the number of variables, k is the common domain size, p1 is the density, i.e. fraction of the n * (n - 1) /2 possible constraints in the graph, p2 is the tightness, i.e. the fraction of the k*k value pairs in each constraint that are disallowed by the constraint (cost 1). All the other possible value pairs have cost 0.

An agent owns only one variable, and all constraints are binary.

Author

Alexandra Olteanu, Thomas Leaute

Member Function Documentation

createSizedRandProblem()

Document frodo2.benchmarks.maxdiscsp.MaxDisCSPProblemGenerator.createSizedRandProblem ( int n, int k, double p1, double p2 )

static

Method to create a random, sized, uniform domain Max-DisCSP problem with a certain density and tightness.

Parameters

n	The number of variables/agents in the problem
k	The number of values in each variable domain
p1	Density
p2	Tightness

Returns

A Document containing a random Max-DisCSP problem.

References generateProblem(), and frodo2.algorithms.RandGraphFactory.getSizedRandGraph().

Referenced by main().

Here is the call graph for this function:

createStats()

Element frodo2.benchmarks.maxdiscsp.MaxDisCSPProblemGenerator.createStats ( String name, String value )

static

Creates a "stats" element.

Parameters

name	the value of the "name" attribute
value	the text

Returns

a new "stats" element

Referenced by generateProblem().

generateProblem()

Document frodo2.benchmarks.maxdiscsp.MaxDisCSPProblemGenerator.generateProblem ( Graph graph, int k, double p1, double p2 )

static

Creates a problem description based on the input constraint graph.

Parameters

graph	a constraint graph
k	the uniform domain size. Each variable domain will have values {1,2, ... ,k}
p1	the target density of the constraint graph
p2	the target tightness of the constraint graph

Returns

a problem description based on the input graph

See also

AllTests.createRandProblem(int, int, int, boolean)

References frodo2.algorithms.RandGraphFactory.Graph.components, frodo2.algorithms.RandGraphFactory.Graph.computeDensity(), frodo2.algorithms.RandGraphFactory.Graph.computeMaxDeg(), createStats(), frodo2.algorithms.RandGraphFactory.Edge.dest, frodo2.algorithms.RandGraphFactory.Graph.edges, frodo2.algorithms.XCSPparser< V extends Addable< V >, U extends Addable< U > >.getConstraint(), frodo2.solutionSpaces.hypercube.Hypercube< V extends Addable< V >, U extends Addable< U > >.iterator(), frodo2.algorithms.RandGraphFactory.Graph.nodes, randHypercube(), and frodo2.algorithms.RandGraphFactory.Edge.source.

Referenced by createSizedRandProblem().

Here is the call graph for this function:

main()

void frodo2.benchmarks.maxdiscsp.MaxDisCSPProblemGenerator.main ( String[] args )

static

Parameters

args	Expects: n k p1 p2

Todo

Add support for MPC-DisWCSP4

References createSizedRandProblem().

Here is the call graph for this function:

randHypercube()

Hypercube< AddableInteger, AddableInteger > frodo2.benchmarks.maxdiscsp.MaxDisCSPProblemGenerator.randHypercube ( List< String > variables, int k, double p2 )

static

Generates a random hypercube.

All domains are {1, ..., k} and utility values are either 0 or 1 The utility can be 1, with probability p2 0, with probability 1-p2

Parameters

variables	list of variables involved
k	the size of the uniform domain
p2	tightness of constraint graph

Returns

a random hypercube

Referenced by generateProblem().

---

The documentation for this class was generated from the following file:

• src/frodo2/benchmarks/maxdiscsp/MaxDisCSPProblemGenerator.java