A DFSgeneration module that also computes the order in which is variable is visited and the total number of variables in the DFS. More...

Inheritance diagram for frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >:

[legend]

Classes
class	DFSorderOutputMessage
	Carries DFS order information for one variable. More...

Public Member Functions
	DFSgenerationWithOrder (DCOPProblemInterface< V, U > problem, Element parameters) throws ClassNotFoundException
	Constructor.
	DFSgenerationWithOrder (Element parameters, DCOPProblemInterface< V, U > problem)
	The constructor called in "statistics gatherer" mode.
Collection< MessageType >	getMsgTypes ()
void	reset ()
void	notifyIn (Message msg)
Public Member Functions inherited from frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >
	DFSgeneration ()
	Default constructor.
HashMap< String, DFSview< V, U > >	getDFS ()
Collection< MessageType >	getMsgTypes ()
void	notifyIn (Message msg)
	The algorithm.
void	setQueue (Queue queue)
void	getStatsFromQueue (Queue queue)
void	setSilent (boolean silent)
String	dfsToString ()
void	reset ()
long	getFinalTime ()
	Returns the time at which the DFS phase has finished, determined by looking at the timestamp of the stat messages.

Static Public Attributes
static MessageType	ROOT_VAR_MSG_TYPE = LeaderElectionMaxID.OUTPUT_MSG_TYPE
	The type of the messages telling whether a given variable is a root.
static MessageType	CHILD_ORDER_MSG_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "CHILDwithOrder")
	The type of the message used to tell the recipient that it is a child of the sender.
static MessageType	PSEUDO_ORDER_MSG_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "PSEUDOwithOrder")
	The type of the message used to tell the recipient that it is a pseudo-child of the sender.
static MessageType	OUTPUT_MSG_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "DFSoutput_DFSgenerationWithOrder")
	The type of the output messages.
static final MessageType	OUTPUT_ORDER_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "DFSorderOutput")
	The type of the output messages containing the orders of variables in the DFS.
static final MessageType	VARIABLE_COUNT_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "DFSorderVarNbr")
	The type of the top-down messages sent by the root containing the number of variables in the DFS.
Static Public Attributes inherited from frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >
static MessageType	FINISH_MSG_TYPE
	The type of the message telling the agent finished.
static MessageType	START_MSG_TYPE
	The type of the message telling the module to start.
static MessageType	ROOT_VAR_MSG_TYPE
	The type of the messages telling whether a given variable is a root.
static final MessageType	CHILD_MSG_TYPE
	The type of the message used to tell the recipient that it is a child of the sender.
static MessageType	PSEUDO_MSG_TYPE
	The type of the message used to tell the recipient that it is a pseudo-child of the sender.
static MessageType	OUTPUT_MSG_TYPE
	The type of the output messages.
static final MessageType	STATS_MSG_TYPE
	The type of the messages containing statistics.

Protected Member Functions
MessageType	getRootVarMsgType ()
MessageType	getChildMsgType ()
MessageType	getPseudoMsgType ()
MessageType	getOutputMsgType ()
void	init ()
void	init (String var)
CHILDmsg	makeChildToken (Serializable rootID, String var, String parent, Collection< String > openNeighbors)
void	processAdditionalMsgInformation (Message msg, String myVar, DFSview< V, U > myRelationships)
void	sendAdditionalDFSoutput (Serializable rootID, String myVar)
Protected Member Functions inherited from frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >
MessageType	getRootVarMsgType ()
MessageType	getChildMsgType ()
MessageType	getPseudoMsgType ()
MessageType	getOutputMsgType ()
void	init ()
	Parses the problem.
void	processAdditionalMsgInformation (Message msg, String var, DFSview< V, U > dfsView)
	allows to process information included in messages which extend CHILDmsg
CHILDmsg	makeChildToken (Serializable rootID, String var, String dest, Collection< String > openNeighbors)
	makes the ChildToken Message with all the information required by the module
void	sendAdditionalDFSoutput (Serializable rootID, String myVar)
	Use this method to send additional output from DFS generation.
boolean	sendDownCHILDtoken (Serializable rootID, String var, Collection< String > openList, DFSview< V, U > myDFSview, Message msg)
	Attempts to choose the next child and sends it a CHILD token.

Private Member Functions
boolean	isRoot (String var)
int	orderOfNextChild (String var)

Private Attributes
Map< String, Integer >	trueOrder
	Map of the true final order of this agent's variables.
Map< String, Integer >	declaredOrder
	Map of the declared final order of this agent's variables.
Map< String, Integer >	order_process
	Map of the last order received.
Map< String, Boolean >	are_root
	For each variable, whether it is a root.
Map< String, Integer >	nbrVars
	For each variable, the total number of variables in its constraint graph component.
final SecureRandom	rnd = new SecureRandom ()
	A source of randomness.
final int	minIncr
	Each variable overstates by rand(minIncr, 2*minIncr) its visiting order in the constraint graph traversal, in order to keep its number of neighbors secret.

Additional Inherited Members
Protected Attributes inherited from frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >
Queue	queue
	The queue on which it should call sendMessage().
boolean	started
	Whether the execution of the algorithm has started.
Map< String, Collection< String > >	openNeighbors
	For each variable that this agent owns, a collection of open neighbor variables.
HashMap< String, DFSview< V, U > >	dfsViews
	For every variable this agent owns, its view of the DFS.
Map< String, String >	owners
	For each known variable, the name of the agent that owns it.
int	totalNbrVars
	The total number of variables in the problem (used only in "statistics gatherer" mode).
NextChildChoiceHeuristic	heuristic
	The heuristic used to choose a variable's next child from its list of open neighbors.
DCOPProblemInterface< V, U >	problem
	The problem.
HashMap< Serializable, LinkedList< String > >	partialPaths
	For each component, the current partial constraint graph traversal path.

Detailed Description

A DFSgeneration module that also computes the order in which is variable is visited and the total number of variables in the DFS.

This is (a modified version of) the DFSorder() procedure from the following paper: Thomas Leaute and Boi Faltings. Privacy-preserving multi-agent constraint satisfaction. In Proceedings of the 2009 IEEE International Conference on PrivAcy, Security, riSk and Trust (PASSAT'09), Vancouver, British Columbia, August 29-31 2009. IEEE Computer Society Press.

Author: Eric Zbinden, Thomas Leaute

Parameters

<V>	the type used for variable values
<U>	the type used for utility values

Constructor & Destructor Documentation

◆ DFSgenerationWithOrder() [1/2]

frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable< U > >.DFSgenerationWithOrder	(	DCOPProblemInterface< V, U >	problem,
		Element	parameters ) throws ClassNotFoundException

Constructor.

Parameters

problem	this agent's problem
parameters	the parameters for DFSgenerationWithOrder

Exceptions

ClassNotFoundException if the heuristic class is unknown

References are_root, declaredOrder, order_process, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.problem, and trueOrder.

◆ DFSgenerationWithOrder() [2/2]

frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable< U > >.DFSgenerationWithOrder	(	Element	parameters,
		DCOPProblemInterface< V, U >	problem )

The constructor called in "statistics gatherer" mode.

Parameters

problem	the overall problem
parameters	the description of what statistics should be reported

References frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.problem.

Member Function Documentation

◆ getChildMsgType()

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.getChildMsgType ( )

protected

See also: DFSgeneration.getChildMsgType()

References CHILD_ORDER_MSG_TYPE.

◆ getMsgTypes()

Collection< MessageType > frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.getMsgTypes ( )

See also: DFSgeneration.getMsgTypes()

References VARIABLE_COUNT_TYPE.

◆ getOutputMsgType()

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.getOutputMsgType ( )

protected

Returns: The type of the output messages

References OUTPUT_MSG_TYPE.

◆ getPseudoMsgType()

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.getPseudoMsgType ( )

protected

Returns: The type of the message used to tell the recipient that it is a pseudo-child of the sender

References PSEUDO_ORDER_MSG_TYPE.

◆ getRootVarMsgType()

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.getRootVarMsgType ( )

protected

See also: DFSgeneration.getRootVarMsgType()

References ROOT_VAR_MSG_TYPE.

◆ init() [1/2]

void frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.init ( )

protected

See also: DFSgeneration.init()

References init(), and frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.problem.

Referenced by init(), and notifyIn().

Here is the call graph for this function:

◆ init() [2/2]

void frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.init ( String var )

protected

See also: DFSgeneration.init(java.lang.String)

References are_root, declaredOrder, order_process, and trueOrder.

◆ isRoot()

boolean frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.isRoot ( String var )

private

Parameters

var	the variable to test

Returns: if the specified variable is a root

References are_root.

Referenced by processAdditionalMsgInformation().

◆ makeChildToken()

CHILDmsg frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable< U > >.makeChildToken	(	Serializable	rootID,
		String	var,
		String	parent,
		Collection< String >	openNeighbors )

protected

See also: DFSgeneration#makeChildToken(Serializable, String, String, Collection)

References frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.openNeighbors, and orderOfNextChild().

Here is the call graph for this function:

◆ notifyIn()

void frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.notifyIn ( Message msg )

See also: DFSgeneration.notifyIn(Message)

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, are_root, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.dfsViews, frodo2.communication.MessageType.equals(), frodo2.algorithms.varOrdering.dfs.VarNbrMsg.getDest(), frodo2.algorithms.varOrdering.dfs.VarNbrMsg.getTotal(), frodo2.communication.Message.getType(), init(), frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.openNeighbors, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.queue, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.started, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.STATS_MSG_TYPE, and VARIABLE_COUNT_TYPE.

Here is the call graph for this function:

◆ orderOfNextChild()

int frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.orderOfNextChild ( String var )

private

Parameters

var	the variable who calls this method

Returns: the order of the next var

References order_process.

Referenced by makeChildToken().

◆ processAdditionalMsgInformation()

void frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable< U > >.processAdditionalMsgInformation	(	Message	msg,
		String	myVar,
		DFSview< V, U >	myRelationships )

protected

See also: DFSgeneration.processAdditionalMsgInformation(Message, java.lang.String, DFSview)

References frodo2.communication.MessageType.equals(), frodo2.algorithms.varOrdering.dfs.CHILDorderMsg.getOrder(), frodo2.communication.Message.getType(), isRoot(), order_process, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.queue, and trueOrder.

Here is the call graph for this function:

◆ reset()

void frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.reset ( )

See also: DFSgeneration.reset()

References are_root, declaredOrder, order_process, and trueOrder.

◆ sendAdditionalDFSoutput()

void frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable< U > >.sendAdditionalDFSoutput	(	Serializable	rootID,
		String	myVar )

protected

See also: DFSgeneration.sendAdditionalDFSoutput(Serializable, java.lang.String)

References order_process, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.queue, and trueOrder.

Member Data Documentation

◆ are_root

Map<String, Boolean> frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.are_root

private

For each variable, whether it is a root.

Referenced by DFSgenerationWithOrder(), init(), isRoot(), notifyIn(), and reset().

◆ CHILD_ORDER_MSG_TYPE

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.CHILD_ORDER_MSG_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "CHILDwithOrder")

static

The type of the message used to tell the recipient that it is a child of the sender.

Referenced by frodo2.algorithms.varOrdering.dfs.CHILDorderMsg.CHILDorderMsg(), frodo2.algorithms.varOrdering.dfs.CHILDorderMsg.CHILDorderMsg(), getChildMsgType(), frodo2.algorithms.varOrdering.dfs.tests.DFSgenerationWithOrderTest.getMsgTypes(), and frodo2.algorithms.varOrdering.dfs.tests.DFSgenerationWithOrderTest.notifyIn().

◆ declaredOrder

Map<String, Integer> frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.declaredOrder

private

Map of the declared final order of this agent's variables.

Referenced by DFSgenerationWithOrder(), frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.DFSorderOutputMessage.DFSorderOutputMessage(), init(), and reset().

◆ minIncr

final int frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.minIncr

private

Each variable overstates by rand(minIncr, 2*minIncr) its visiting order in the constraint graph traversal, in order to keep its number of neighbors secret.

◆ nbrVars

Map<String, Integer> frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.nbrVars

private

For each variable, the total number of variables in its constraint graph component.

◆ order_process

Map<String, Integer> frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.order_process

private

Map of the last order received.

Referenced by DFSgenerationWithOrder(), init(), orderOfNextChild(), processAdditionalMsgInformation(), reset(), and sendAdditionalDFSoutput().

◆ OUTPUT_MSG_TYPE

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.OUTPUT_MSG_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "DFSoutput_DFSgenerationWithOrder")

static

The type of the output messages.

Referenced by frodo2.algorithms.dpop.privacy.EncryptedUTIL< V extends Addable< V >, U extends Addable, E extends AddableLimited< U, E >.getMsgTypes(), frodo2.algorithms.dpop.privacy.RerootRequester< V extends Addable< V >, U extends Addable >.getMsgTypes(), frodo2.algorithms.dpop.privacy.test.SecureRerootingTest.getMsgTypes(), getOutputMsgType(), frodo2.algorithms.varOrdering.dfs.tests.DFSgenerationWithOrderTest.getOutputMsgType(), frodo2.algorithms.dpop.privacy.EncryptedUTIL< V extends Addable< V >, U extends Addable, E extends AddableLimited< U, E >.notifyIn(), and frodo2.algorithms.dpop.privacy.test.SecureRerootingTest.notifyIn().

◆ OUTPUT_ORDER_TYPE

final MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.OUTPUT_ORDER_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "DFSorderOutput")

static

The type of the output messages containing the orders of variables in the DFS.

Referenced by frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.DFSorderOutputMessage.DFSorderOutputMessage(), frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.DFSorderOutputMessage.DFSorderOutputMessage(), frodo2.algorithms.dpop.privacy.CollaborativeDecryption< C extends Addable< C >, E extends AddableLimited< C, E, K extends PublicKeyShare >.getMsgTypes(), frodo2.algorithms.dpop.privacy.SecureRerooting< C extends Addable< C >, E extends AddableLimited< C, E >.getMsgTypes(), frodo2.algorithms.varOrdering.dfs.tests.DFSgenerationWithOrderTest.getMsgTypes(), frodo2.algorithms.varOrdering.dfs.tests.DFSgenerationWithOrderTest.notifyIn(), and frodo2.algorithms.varOrdering.dfs.DFSgenerationParallel< S extends Comparable< S > &Serializable >.FakeQueue.sendMessageToSelf().

◆ PSEUDO_ORDER_MSG_TYPE

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.PSEUDO_ORDER_MSG_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "PSEUDOwithOrder")

static

The type of the message used to tell the recipient that it is a pseudo-child of the sender.

Referenced by getPseudoMsgType().

◆ rnd

final SecureRandom frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.rnd = new SecureRandom ()

private

A source of randomness.

◆ ROOT_VAR_MSG_TYPE

MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.ROOT_VAR_MSG_TYPE = LeaderElectionMaxID.OUTPUT_MSG_TYPE

static

The type of the messages telling whether a given variable is a root.

Referenced by getRootVarMsgType().

◆ trueOrder

Map<String, Integer> frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.trueOrder

private

Map of the true final order of this agent's variables.

Referenced by DFSgenerationWithOrder(), frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.DFSorderOutputMessage.DFSorderOutputMessage(), init(), processAdditionalMsgInformation(), reset(), and sendAdditionalDFSoutput().

◆ VARIABLE_COUNT_TYPE

final MessageType frodo2.algorithms.varOrdering.dfs.DFSgenerationWithOrder< V extends Addable< V >, U extends Addable >.VARIABLE_COUNT_TYPE = new MessageType ("VarOrdering", "DFSgenerationWithOrder", "DFSorderVarNbr")

static

The type of the top-down messages sent by the root containing the number of variables in the DFS.

Referenced by frodo2.algorithms.dpop.privacy.CollaborativeDecryption< C extends Addable< C >, E extends AddableLimited< C, E, K extends PublicKeyShare >.getMsgTypes(), frodo2.algorithms.dpop.privacy.RerootRequester< V extends Addable< V >, U extends Addable >.getMsgTypes(), frodo2.algorithms.dpop.privacy.SecureRerooting< C extends Addable< C >, E extends AddableLimited< C, E >.getMsgTypes(), getMsgTypes(), frodo2.algorithms.varOrdering.dfs.tests.DFSgenerationWithOrderTest.getMsgTypes(), notifyIn(), frodo2.algorithms.varOrdering.dfs.tests.DFSgenerationWithOrderTest.notifyIn(), frodo2.algorithms.varOrdering.dfs.DFSgenerationParallel< S extends Comparable< S > &Serializable >.FakeQueue.notifyInListeners(), frodo2.algorithms.varOrdering.dfs.DFSgenerationParallel< S extends Comparable< S > &Serializable >.FakeQueue.sendMessageToSelf(), frodo2.algorithms.varOrdering.dfs.VarNbrMsg.VarNbrMsg(), and frodo2.algorithms.varOrdering.dfs.VarNbrMsg.VarNbrMsg().

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

src/frodo2/algorithms/varOrdering/dfs/DFSgenerationWithOrder.java

Classes

Public Member Functions

Static Public Attributes

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ DFSgenerationWithOrder() [1/2]

◆ DFSgenerationWithOrder() [2/2]

Member Function Documentation

◆ getChildMsgType()

◆ getMsgTypes()

◆ getOutputMsgType()

◆ getPseudoMsgType()

◆ getRootVarMsgType()

◆ init() [1/2]

◆ init() [2/2]

◆ isRoot()

◆ makeChildToken()

◆ notifyIn()

◆ orderOfNextChild()

◆ processAdditionalMsgInformation()

◆ reset()

◆ sendAdditionalDFSoutput()

Member Data Documentation

◆ are_root

◆ CHILD_ORDER_MSG_TYPE

◆ declaredOrder

◆ minIncr

◆ nbrVars

◆ order_process

◆ OUTPUT_MSG_TYPE

◆ OUTPUT_ORDER_TYPE

◆ PSEUDO_ORDER_MSG_TYPE

◆ rnd

◆ ROOT_VAR_MSG_TYPE

◆ trueOrder

◆ VARIABLE_COUNT_TYPE