frodo2.benchmarks.graphcoloring.GraphColoring Class Reference

A graph coloring problem generator. More...

Public Member Functions
	GraphColoring (int nbrNodes, double density, final double tightness, final int nbrColors, int nbrStochNodes, boolean nbrLinks)
	Constructor.
	GraphColoring (Graph graph, final double tightness, final int nbrColors, final int nbrStochNodes)
	Constructor.
Document	toXCSP (final boolean publicInteragentConstraints, final boolean soft, final boolean intensional)
	Generates an XCSP representation of a graph coloring problem.

Static Public Member Functions
static void	main (String[] args) throws IOException
	Generates a random graph coloring problem and writes it to a file.
static Document	generateProblem (boolean soft, int nbrNodes, double density, double tightness, int nbrColors, int nbrStochNodes, boolean intensional)
	Generates a problem instance.
static Element	createStats (String name, String value)
	Creates a "stats" element.

Public Attributes
final Graph	graph
	The underlying graph.
final TreeMap< String, ArrayList< Integer > >	unaryCons
	For each node, its list of forbidden colors.
final int	nbrColors
	The number of colors.

Private Attributes
final HashSet< String >	stochNodes
	The set of uncontrollable nodes.
final String	instanceName
	The name of the problem instance.
double	targetDensity = -1
	The desired density.
final double	targetTightness
	The desired tightness of the unary constraints.

Detailed Description

A graph coloring problem generator.

Author

Thomas Leaute

Constructor & Destructor Documentation

GraphColoring() [1/2]

frodo2.benchmarks.graphcoloring.GraphColoring.GraphColoring	(	int	nbrNodes,
		double	density,
		final double	tightness,
		final int	nbrColors,
		int	nbrStochNodes,
		boolean	nbrLinks )

Constructor.

Parameters

nbrNodes	total number of nodes
density	graph density
tightness	the tightness of the unary constraints
nbrColors	number of colors
nbrStochNodes	number of uncontrollable nodes
nbrLinks	if true, the density parameter states that there must be density*nbrNodes links in the graph

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

Referenced by generateProblem(), and main().

Here is the call graph for this function:

GraphColoring() [2/2]

frodo2.benchmarks.graphcoloring.GraphColoring.GraphColoring	(	Graph	graph,
		final double	tightness,
		final int	nbrColors,
		final int	nbrStochNodes )

Constructor.

Parameters

graph	the underlying graph
tightness	the tightness of the unary constraints
nbrColors	number of colors
nbrStochNodes	number of uncontrollable nodes

References graph, nbrColors, and frodo2.algorithms.RandGraphFactory.Graph.nodes.

Member Function Documentation

createStats()

Element frodo2.benchmarks.graphcoloring.GraphColoring.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 toXCSP().

generateProblem()

Document frodo2.benchmarks.graphcoloring.GraphColoring.generateProblem ( boolean soft, int nbrNodes, double density, double tightness, int nbrColors, int nbrStochNodes, boolean intensional )

static

Generates a problem instance.

Parameters

soft	whether to make it a DisCSP (false) or a Max-DisCSP (true)
nbrNodes	total number of nodes
density	graph density
tightness	the tightness of the unary constraints
nbrColors	number of colors
nbrStochNodes	number of uncontrollable nodes
intensional	whether the output should be intensional

Returns

a problem instance

References GraphColoring(), nbrColors, and toXCSP().

Here is the call graph for this function:

main()

void frodo2.benchmarks.graphcoloring.GraphColoring.main ( String[] args ) throws IOException

static

Generates a random graph coloring problem and writes it to a file.

Parameters

args	[-soft] nbrNodes density nbrColors [stochNodeRatio]

Exceptions

IOException

if an error occurs while attempting to write the output file

Todo

Add support for various graph topologies

References GraphColoring(), nbrColors, and toXCSP().

Here is the call graph for this function:

toXCSP()

Document frodo2.benchmarks.graphcoloring.GraphColoring.toXCSP	(	final boolean	publicInteragentConstraints,
		final boolean	soft,
		final boolean	intensional )

Generates an XCSP representation of a graph coloring problem.

Parameters

publicInteragentConstraints	whether inter-agent constraints should be public
soft	whether the output should be a Max-DisCSP
intensional	whether the output should be intensional

Returns

An XCSP-formatted Document

References createStats(), frodo2.algorithms.RandGraphFactory.Edge.dest, graph, nbrColors, frodo2.algorithms.RandGraphFactory.Graph.nodes, and frodo2.algorithms.RandGraphFactory.Edge.source.

Referenced by generateProblem(), and main().

Here is the call graph for this function:

Member Data Documentation

graph

final Graph frodo2.benchmarks.graphcoloring.GraphColoring.graph

The underlying graph.

Referenced by GraphColoring(), and toXCSP().

instanceName

final String frodo2.benchmarks.graphcoloring.GraphColoring.instanceName

private

The name of the problem instance.

nbrColors

final int frodo2.benchmarks.graphcoloring.GraphColoring.nbrColors

The number of colors.

Referenced by generateProblem(), GraphColoring(), GraphColoring(), main(), and toXCSP().

stochNodes

final HashSet<String> frodo2.benchmarks.graphcoloring.GraphColoring.stochNodes

private

The set of uncontrollable nodes.

targetDensity

double frodo2.benchmarks.graphcoloring.GraphColoring.targetDensity = -1

private

The desired density.

targetTightness

final double frodo2.benchmarks.graphcoloring.GraphColoring.targetTightness

private

The desired tightness of the unary constraints.

unaryCons

final TreeMap< String, ArrayList<Integer> > frodo2.benchmarks.graphcoloring.GraphColoring.unaryCons

For each node, its list of forbidden colors.

---

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

• src/frodo2/benchmarks/graphcoloring/GraphColoring.java