A DFS generation protocol with a heuristic for E[DPOP]. More...

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

[legend]

Classes
class	VarElectionHeuristic
	Heuristic used for variable election. More...

Public Member Functions
	LocalRandVarsDFS ()
	Default constructor.
	LocalRandVarsDFS (Element params)
	Constructor for the UniqueIDfactory.
	LocalRandVarsDFS (DCOPProblemInterface< V, U > problem, Element parameters) throws ClassNotFoundException, NoSuchMethodException, InstantiationException, IllegalAccessException, InvocationTargetException
	LocalRandVarsDFS (Element parameters, DCOPProblemInterface< V, U > problem)
	The constructor called in "statistics gatherer" mode.
Collection< MessageType >	getMsgTypes ()
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 final MessageType	RAND_VARS_MSG_TYPE = new MessageType ("VarOrdering", "LocalRandVarsDFS", "RandVars")
	The type of messages containing random variables.
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
void	init ()
boolean	sendDownCHILDtoken (Serializable rootID, String var, Collection< String > openList, DFSview< V, U > myDFSview, Message msg)
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
String	popNextChild (String var, DFSview< V, U > dfsView, Collection< String > openNeighbors)
	Chooses the child with the most similar set of new neighboring random variables to that of the input variable.

Private Attributes
Map< String, Set< String > >	randNeighborhoods
	For each of this agent's variables, its set of neighbor random variables.
Map< String, Set< String > >	neighborAgents
	For each variable owned by this agent, the set of agents that own a variable connected to this variable.

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 DFS generation protocol with a heuristic for E[DPOP].

The heuristic attempts to avoid putting, on the path between a variable linked to random variable r and lca(r), a variable that is not linked to r. It is also a Variable Election heuristic, electing the variable with fewest neighboring random variables.

Author: Thomas Leaute

Todo: When lca(r) can be a variable that is not linked to r, the implementation should be improved by taking advantage of the random variables in backtracking CHILD tokens received from children.

Parameters

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

Constructor & Destructor Documentation

◆ LocalRandVarsDFS() [1/4]

frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable >.LocalRandVarsDFS ( )

Default constructor.

◆ LocalRandVarsDFS() [2/4]

frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable >.LocalRandVarsDFS ( Element params )

Constructor for the UniqueIDfactory.

Parameters

params unused

◆ LocalRandVarsDFS() [3/4]

frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable< U > >.LocalRandVarsDFS	(	DCOPProblemInterface< V, U >	problem,
		Element	parameters ) throws ClassNotFoundException, NoSuchMethodException, InstantiationException, IllegalAccessException, InvocationTargetException

Parameters

problem	this agent's problem
parameters	the parameters for LocalRandVarsDFS

Exceptions

ClassNotFoundException	if the heuristic refers is of an unknown class
NoSuchMethodException	if the heuristic does not have a constructor that takes in one ProblemInterface
InvocationTargetException	if the heuristic constructor throws an exception
IllegalAccessException	if the heuristic constructor is not accessible
InstantiationException	if the heuristic class is abstract

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

◆ LocalRandVarsDFS() [4/4]

frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable< U > >.LocalRandVarsDFS	(	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

◆ getMsgTypes()

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

See also: DFSgeneration.getMsgTypes()

References RAND_VARS_MSG_TYPE.

◆ init()

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

protected

See also: DFSgeneration.init()

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

Referenced by notifyIn().

◆ notifyIn()

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

See also: DFSgeneration.notifyIn(Message)

Here is the call graph for this function:

◆ popNextChild()

String frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable< U > >.popNextChild	(	String	var,
		DFSview< V, U >	dfsView,
		Collection< String >	openNeighbors )

private

Chooses the child with the most similar set of new neighboring random variables to that of the input variable.

Breaks ties using the heuristic given as a parameter to the module constructor.

Parameters

var	the variable for which we are looking for the next child
dfsView	the current incomplete view that this variable has of its DFS neighbors
openNeighbors	the list of open neighbors for this variable

Returns: the name of the chosen next child, or null if not all messages necessary to choose have been received

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

Referenced by sendDownCHILDtoken().

◆ sendDownCHILDtoken()

boolean frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable< U > >.sendDownCHILDtoken	(	Serializable	rootID,
		String	var,
		Collection< String >	openList,
		DFSview< V, U >	myDFSview,
		Message	msg )

protected

See also: DFSgeneration.sendDownCHILDtoken(Serializable, java.lang.String, java.util.Collection, DFSview, Message)

References frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.owners, frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.partialPaths, popNextChild(), and frodo2.algorithms.varOrdering.dfs.DFSgeneration< V, U >.queue.

Here is the call graph for this function:

Member Data Documentation

◆ neighborAgents

Map< String, Set<String> > frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable >.neighborAgents

private

For each variable owned by this agent, the set of agents that own a variable connected to this variable.

◆ RAND_VARS_MSG_TYPE

final MessageType frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable >.RAND_VARS_MSG_TYPE = new MessageType ("VarOrdering", "LocalRandVarsDFS", "RandVars")

static

The type of messages containing random variables.

Referenced by getMsgTypes(), notifyIn(), and frodo2.algorithms.varOrdering.dfs.RandVarsMsg.RandVarsMsg().

◆ randNeighborhoods

Map< String, Set<String> > frodo2.algorithms.varOrdering.dfs.LocalRandVarsDFS< V extends Addable< V >, U extends Addable >.randNeighborhoods

private

For each of this agent's variables, its set of neighbor random variables.

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

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

Classes

Public Member Functions

Static Public Attributes

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ LocalRandVarsDFS() [1/4]

◆ LocalRandVarsDFS() [2/4]

◆ LocalRandVarsDFS() [3/4]

◆ LocalRandVarsDFS() [4/4]

Member Function Documentation

◆ getMsgTypes()

◆ init()

◆ notifyIn()

◆ popNextChild()

◆ sendDownCHILDtoken()

Member Data Documentation

◆ neighborAgents

◆ RAND_VARS_MSG_TYPE

◆ randNeighborhoods