Distributed algorithm to compute one variable linear ordering per connected component in the constraint graph. More...

Inheritance diagram for frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >:

[legend]

Classes
interface	Heuristic
	Variable ordering heuristic. More...
class	MaxWidthMinDom
	A heuristic that maximizes the number of neighbors already in the order, breaking ties by minimizing the domain size, and then by variable name. More...
class	ComponentInfo
	All relevant information about a connected component of the constraint graph. More...

Public Member Functions
	LinearOrdering (Element parameters, DCOPProblemInterface< V, U > problem)
	The constructor called in "statistics gatherer" mode.
	LinearOrdering (DCOPProblemInterface< V, U > problem, Element parameters)
	Constructor.
void	reset ()
void	getStatsFromQueue (Queue queue)
void	setQueue (Queue queue)
void	setSilent (boolean silent)
Collection< MessageType >	getMsgTypes ()
void	notifyIn (Message msg)
Public Member Functions inherited from frodo2.communication.IncomingMsgPolicyInterface< T >
default void	notifyIn (Message msg, Object toAgent)
	Notifies the listener of an incoming message.

Static Public Attributes
static MessageType	START_MSG_TYPE = AgentInterface.START_AGENT
	The type of the message telling the module to start.

Static Package Attributes
static final MessageType	REQUEST_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "NextVarRequest")
	The type of the messages sent to request proposals for the next variable to put in the order.
static final MessageType	PROPOSAL_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "NextVarProposal")
	The type of the messages containing a proposal for the next variable to put in the order.
static final MessageType	NEXT_VAR_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "NextVarChosen")
	The type of the messages notifying an agent that one of its variable is next in the order.

Private Member Functions
void	init ()
	Parses the problem.
void	printOrder ()
	Prints the variable order in DOT format.

Private Attributes
Queue	queue
	This module's queue.
boolean	silent = false
	Whether the stats gatherer should display the resulting linear order.
String	dotRendererClass
	Renderer to display DOT code.
DCOPProblemInterface< V, U >	problem
	The problem.
boolean	started = false
	Whether the module has already started the algorithm.
int	countdown
	The number of my variables for which I have not yet received the output of VariableElection.
HashMap< Comparable<?>, ComponentInfo >	compInfos
	The information about each connected component in the constraint graph.
String	myID
	This agent's name.
Set< String >	allAgents
	The set of all agents in the problem.
ArrayList< RequestMsg >	pendingMsgs
	A list of pending requests.
Heuristic< IntIntStringTuple >	heuristic
	The heuristic.
Map< String, Set< String > >	agentNeighborhoods
	For each internal variable, its list of agent neighbors.
Map< String, String >	owners
	The owner of each variable I know.
HashMap< String, Comparable<?> >	componentIDs
	The component ID for this agent's variables and all their neighbors.
Map< String, ? extends Collection< String > >	neighborhoods
	For each internal variable, its list of neighbors.

Static Private Attributes
static final MessageType	TEMP_OUTPUT_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "VarOrderNoSpace")
	The type of the message notifying the agent of the chosen ordering, excluding the spaces.

Detailed Description

Distributed algorithm to compute one variable linear ordering per connected component in the constraint graph.

The algorithm is initiated by the variable(s) chosen by VariableElection. At each iteration, the current variable prompts all agents for their best proposals for the next variable.

Parameters

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

Warning: Requires that each agent know the identity of all other agents in the problem.

Todo: Write a dedicated unit test.

Author: Thomas Leaute

Constructor & Destructor Documentation

◆ LinearOrdering() [1/2]

frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable< U > >.LinearOrdering	(	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 (currently unused)

References problem.

◆ LinearOrdering() [2/2]

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

Constructor.

Parameters

problem	this agent's problem
parameters	the parameters for LinearOrdering

References problem.

Member Function Documentation

◆ getMsgTypes()

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

See also: StatsReporter.getMsgTypes()

Implements frodo2.communication.MessageListener< T >.

References NEXT_VAR_MSG_TYPE, frodo2.algorithms.varOrdering.election.LeaderElectionMaxID< T extends Comparable< T > &Serializable >.OUTPUT_MSG_TYPE, PROPOSAL_MSG_TYPE, REQUEST_MSG_TYPE, START_MSG_TYPE, and TEMP_OUTPUT_MSG_TYPE.

◆ getStatsFromQueue()

void frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.getStatsFromQueue ( Queue queue )

See also: StatsReporter.getStatsFromQueue(Queue)

Implements frodo2.algorithms.StatsReporter.

References queue, and frodo2.algorithms.varOrdering.linear.OrderMsg< V extends Addable< V >, U extends Addable >.STATS_MSG_TYPE.

Referenced by frodo2.algorithms.afb.test.AFBagentTest< V extends Addable< V >, U extends Addable >.setUp(), and frodo2.algorithms.synchbb.test.SynchBBagentTest< V extends Addable< V >, U extends Addable >.setUp().

◆ init()

void frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.init ( )

private

Parses the problem.

References frodo2.solutionSpaces.ProblemInterface< V extends Addable< V >, U extends Addable >.getAgent(), frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getAgentNeighborhoods(), frodo2.solutionSpaces.ProblemInterface< V extends Addable< V >, U extends Addable >.getAgents(), frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getNbrIntVars(), frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getNeighborhoods(), and frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getOwners().

Referenced by notifyIn().

Here is the call graph for this function:

◆ notifyIn()

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

See also: StatsReporter.notifyIn(Message)

Implements frodo2.communication.IncomingMsgPolicyInterface< T >.

References agentNeighborhoods, frodo2.communication.MessageType.equals(), frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getNbrNeighbors(), init(), notifyIn(), frodo2.algorithms.varOrdering.election.LeaderElectionMaxID< T extends Comparable< T > &Serializable >.OUTPUT_MSG_TYPE, frodo2.communication.Queue.sendMessage(), frodo2.communication.Queue.sendMessageToMulti(), frodo2.communication.Queue.sendMessageToSelf(), frodo2.algorithms.AgentInterface< V extends Addable< V > >.STATS_MONITOR, frodo2.algorithms.varOrdering.linear.OrderMsg< V extends Addable< V >, U extends Addable >.STATS_MSG_TYPE, and TEMP_OUTPUT_MSG_TYPE.

Referenced by notifyIn().

Here is the call graph for this function:

◆ printOrder()

void frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.printOrder ( )

private

Prints the variable order in DOT format.

References dotRendererClass, and problem.

◆ reset()

void frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.reset ( )

See also: StatsReporter.reset()

Implements frodo2.algorithms.StatsReporter.

◆ setQueue()

void frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.setQueue ( Queue queue )

See also: StatsReporter.setQueue(Queue)

Implements frodo2.communication.MessageListener< T >.

References queue.

◆ setSilent()

void frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.setSilent ( boolean silent )

See also: StatsReporter.setSilent(boolean)

Implements frodo2.algorithms.StatsReporter.

References silent.

Referenced by frodo2.algorithms.afb.test.AFBagentTest< V extends Addable< V >, U extends Addable >.setUp(), and frodo2.algorithms.synchbb.test.SynchBBagentTest< V extends Addable< V >, U extends Addable >.setUp().

Member Data Documentation

◆ agentNeighborhoods

Map< String, Set<String> > frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.agentNeighborhoods

private

For each internal variable, its list of agent neighbors.

Referenced by notifyIn().

◆ allAgents

Set<String> frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.allAgents

private

The set of all agents in the problem.

◆ compInfos

HashMap<Comparable<?>, ComponentInfo> frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.compInfos

private

The information about each connected component in the constraint graph.

◆ componentIDs

HashMap< String, Comparable<?> > frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.componentIDs

private

The component ID for this agent's variables and all their neighbors.

◆ countdown

int frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.countdown

private

The number of my variables for which I have not yet received the output of VariableElection.

◆ dotRendererClass

String frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.dotRendererClass

private

Renderer to display DOT code.

Referenced by printOrder().

◆ heuristic

Heuristic<IntIntStringTuple> frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.heuristic

private

The heuristic.

◆ myID

String frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.myID

private

This agent's name.

◆ neighborhoods

Map<String, ? extends Collection<String> > frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.neighborhoods

private

For each internal variable, its list of neighbors.

◆ NEXT_VAR_MSG_TYPE

final MessageType frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.NEXT_VAR_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "NextVarChosen")

staticpackage

The type of the messages notifying an agent that one of its variable is next in the order.

Referenced by getMsgTypes(), frodo2.algorithms.varOrdering.linear.NextVarMsg.NextVarMsg(), and frodo2.algorithms.varOrdering.linear.NextVarMsg.NextVarMsg().

◆ owners

Map<String, String> frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.owners

private

The owner of each variable I know.

◆ pendingMsgs

ArrayList<RequestMsg> frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.pendingMsgs

private

A list of pending requests.

◆ problem

DCOPProblemInterface<V, U> frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.problem

private

The problem.

Referenced by LinearOrdering(), LinearOrdering(), and printOrder().

◆ PROPOSAL_MSG_TYPE

final MessageType frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.PROPOSAL_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "NextVarProposal")

staticpackage

The type of the messages containing a proposal for the next variable to put in the order.

Referenced by getMsgTypes(), frodo2.algorithms.varOrdering.linear.ProposalMsg< S extends Comparable< S > &Serializable >.ProposalMsg(), and frodo2.algorithms.varOrdering.linear.ProposalMsg< S extends Comparable< S > &Serializable >.ProposalMsg().

◆ queue

Queue frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.queue

private

This module's queue.

Referenced by getStatsFromQueue(), and setQueue().

◆ REQUEST_MSG_TYPE

final MessageType frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.REQUEST_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "NextVarRequest")

staticpackage

The type of the messages sent to request proposals for the next variable to put in the order.

Referenced by getMsgTypes(), frodo2.algorithms.varOrdering.linear.RequestMsg.RequestMsg(), and frodo2.algorithms.varOrdering.linear.RequestMsg.RequestMsg().

◆ silent

boolean frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.silent = false

private

Whether the stats gatherer should display the resulting linear order.

Referenced by setSilent().

◆ START_MSG_TYPE

MessageType frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.START_MSG_TYPE = AgentInterface.START_AGENT

static

The type of the message telling the module to start.

Referenced by getMsgTypes().

◆ started

boolean frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.started = false

private

Whether the module has already started the algorithm.

◆ TEMP_OUTPUT_MSG_TYPE

final MessageType frodo2.algorithms.varOrdering.linear.LinearOrdering< V extends Addable< V >, U extends Addable >.TEMP_OUTPUT_MSG_TYPE = new MessageType ("VarOrdering", "LinearOrdering", "VarOrderNoSpace")

staticprivate

The type of the message notifying the agent of the chosen ordering, excluding the spaces.

Referenced by getMsgTypes(), and notifyIn().

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

src/frodo2/algorithms/varOrdering/linear/LinearOrdering.java

Classes

Public Member Functions

Static Public Attributes

Static Package Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ LinearOrdering() [1/2]

◆ LinearOrdering() [2/2]

Member Function Documentation

◆ getMsgTypes()

◆ getStatsFromQueue()

◆ init()

◆ notifyIn()

◆ printOrder()

◆ reset()

◆ setQueue()

◆ setSilent()

Member Data Documentation

◆ agentNeighborhoods

◆ allAgents

◆ compInfos

◆ componentIDs

◆ countdown

◆ dotRendererClass

◆ heuristic

◆ myID

◆ neighborhoods

◆ NEXT_VAR_MSG_TYPE

◆ owners

◆ pendingMsgs

◆ problem

◆ PROPOSAL_MSG_TYPE

◆ queue

◆ REQUEST_MSG_TYPE

◆ silent

◆ START_MSG_TYPE

◆ started

◆ TEMP_OUTPUT_MSG_TYPE