This class is designed to store GOODs received by a node from its children, and is used in the O-DPOP algorithm. More...

Inheritance diagram for frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >:

[legend]

Classes
class	IntArrayWrapper
	The IntArrayWrapper is used as a key for (partial) assignments. More...

Public Member Functions
	InnerNodeTree (String ownVariable, Val[] ownVariableDomain, UtilitySolutionSpace< Val, U > space, int numberOfChildren, U zero, L leafNodeInstance, U infeasibleUtil, boolean maximize, boolean collectStats)
	A constructor.
	InnerNodeTree (String ownVariable, Val[] ownVariableDomain, List< UtilitySolutionSpace< Val, U > > spaces, int numberOfChildren, U zero, L leafNodeInstance, U infeasibleUtil, boolean maximize, boolean collectStats)
	A constructor.
boolean	add (Good< Val, U > g, int sender)
	Adds a good to the tree.
void	setFinalDomainSize (String[] variables, int[] domainSize)
String	toString ()
	Method used for debugging purposes.
IntArrayWrapper	createIntArrayWrapper (int[] array)
IntArrayWrapper	createIntArrayWrapper (int size)
boolean	checkLeaf (L leaf, IntArrayWrapper currentPath, boolean checkUB, U utility, int sender)
	Method to check that the utility and UB are consistent with the available information.
boolean	add (Good< Val, U > g, int sender, HashMap< String, Val[]> domains)
Val[][]	getDomains ()
Public Member Functions inherited from frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >
boolean	add (Good< Val, U > g, int sender, HashMap< String, Val[]> domains)
	Adds a good to the tree.
Good< Val, U >	getAmax ()
void	getBestAssignmentForOwnVariable (HashMap< String, Val > contextMap)
String[]	getChildSeparatorReportingOrder (int child)
	Returns the variables in the childs separator in the order it reported them.
int	getChildSeparatorSize (int child)
HashMap< String, Val >	getChildValues (HashMap< String, Val > parentContext, int child)
	Given a map that maps variables to values, this method returns the values belonging to the variables in a child's separator.
int[]	getFinalDomainSize ()
Val[][]	getDomains ()
boolean	hasFullInfo ()
boolean	hasMore ()
boolean	isValuationSufficient ()
boolean	knowsVariable (String variable)
boolean	notEnoughInfo ()
void	removeAMax ()
void	setChildrenSeparator (int child, String[] variables)
	Initializes the separator of a child.
boolean	setChildDone (int child)
	If a child has send a DONE message, the upper bound should be set to -infinity.
String	toString ()
	Method used for debugging purposes.
IntArrayWrapper	createIntArrayWrapper (int[] array)
boolean	checkLeaf (L leaf, IntArrayWrapper currentPath, boolean checkUB, U utility, int sender)
	Method to check that the utility and UB are consistent with the available information.
boolean	compareWithHypercube (UtilitySolutionSpace< Val, U > h)
	Method to check the initialization of the tree.
boolean	pathExists (Val[] values)
boolean	UBexists (InnerNode< U, L > currentNode, int depth)
	Test to see whether a leafnode used as upperbound actually exists, i.e.
boolean	Utilexists (InnerNode< U, L > currentNode, int depth)
	Checks whether the maxUtil of a node actually exists.
int	treeSize ()
	Wrapper around treeSize(int, int, Node).
void	setFinalDomainSize (String[] variables, int[] domainSize)

Protected Member Functions
	InnerNodeTree (String ownVariable, Val[] ownVariableDomain, UtilitySolutionSpace< Val, U > space, U zero, int numberOfChildren, U infeasibleUtil, boolean maximize, boolean collectStats)
	A constructor.
	InnerNodeTree (String ownVariable, Val[] ownVariableDomain, List< UtilitySolutionSpace< Val, U > > spaces, U zero, int numberOfChildren, U infeasibleUtil, boolean maximize, boolean collectStats)
	A constructor.
	InnerNodeTree (L leafNodeInstance, String ownVariable, Val[] ownVariableDomain, UtilitySolutionSpace< Val, U > space, U zero, int numberOfChildren, U infeasibleUtil, boolean maximize, boolean collectStats)
	A dummy constructor to be used by extending classes.
	InnerNodeTree (L leafNodeInstance, String ownVariable, Val[] ownVariableDomain, List< UtilitySolutionSpace< Val, U > > spaces, U zero, int numberOfChildren, U infeasibleUtil, boolean maximize, boolean collectStats)
	A dummy constructor to be used by extending classes.
void	addNewDomainElement (HashMap< String, Val > newValues)
	This method adds a new variable to the data structure.
void	addNewDomainElementNoUB (int depth, int horizon, IntArrayWrapper currentPath, int[] partialPath, int[] newDomainPath, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNodeUncast, Good< Val, U > g, U utilityDelta, int sender, boolean onPartialPath, boolean fill)
	This method is called when a new domain element is discovered before the UBs can be calculated.
void	addNewDomainElementWithUB (int depth, int horizon, IntArrayWrapper currentPath, int[] partialPath, int[] newDomainPath, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNodeUncast, Good< Val, U > g, U utilityDelta, int sender, boolean onPartialPath, boolean fill)
	This method is called when a new domain element is discovered while the UB is already set.
int[]	addNewVariable (String[] allVariables, HashMap< String, Val > newVariables, int sender)
	This method adds new variables to the data structure.
void	changeDummyToReal (int depth, InnerNode< U, L > currentNode, boolean change)
	Changes all dummy children of the variables in dummyToReal to real nodes.
void	changeDummyToReal (int depth, IntArrayWrapper currentPath, InnerNode< U, L > currentNode, boolean change)
	Changes all dummy children of the variables in dummyToReal to real nodes.
InnerNode< U, L >	createInnerNode (int numberOfChildren)
InnerNode< U, L >	createInnerNode (Node< U >[] children)
L	createLeaf (IntArrayWrapper currentPath, boolean real, Good< Val, U > g, int child, final boolean withUB)
	Method to create a new leaf node.
L	createLeaf (IntArrayWrapper currentPath, boolean real, final boolean withUB)
	Method to create a new leaf node.
frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	createPathNoUB (int depth, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.IntArrayWrapper currentPathUncast, int[] partialPath, boolean real, Good< Val, U > g, int sender)
	Given a partial path, this method creates the path in the tree.
boolean	findUnused (int depth, int[] localPath, InnerNode< U, L > currentNode)
	Check whether the assignment to the local problem, represented by localPath, can still be used somewhere.
U	getOwnVariableOptions (int[] optimalPath, Val[] assignments)
	Given the assignment of variables in its separator, this method returns the utility for all domain elements of the own variable.
void	init (int numberOfChildren, U zero)
	Initialize all the variables of the tree.
U	initiateBounds (frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNodeUncast, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.IntArrayWrapper currentPathUncast, int depth, boolean onLocalPath, Good< Val, U > g, int sender)
	This method adds the dummy part to the tree.
void	updatePath (int depth, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.IntArrayWrapper currentPathUncast, int[] partialPath, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNodeUncast, Good< Val, U > g, U utilityDelta, int sender, boolean onLocalPath, final boolean withUB)
	This method walks trough the tree according to the given partial path and finds all leaf nodes that correspond to assignments that are compatible with the good to be added.
boolean	upperBoundChangesUtil (frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > node, U UB)
void	removeDummies (int removalDepth, boolean[] change, int depth, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNodeUncast)
	Remove the dummy element for the variables marked in change.
boolean	hasSupport (IntArrayWrapper currentPath)
	Method to check whether a particular leaf node has support, i.e.
boolean	checkTree (int depth, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNodeUncast, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.IntArrayWrapper currentPathUncast, boolean UB, boolean checkLeafs, boolean checkSupport, boolean checkUtil)
	This method checks the tree on the following properties.
Protected Member Functions inherited from frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >
	InnerNodeTree (String ownVariable, Val[] ownVariableDomain, UtilitySolutionSpace< Val, U > space, U zero, int numberOfChildren, U infeasibleUtil, boolean maximize, boolean collectStats)
	A constructor.
int[]	addNewVariable (String[] allVariables, HashMap< String, Val > newVariables, HashMap< String, Val[]> newDomains, int sender)
	This method adds new variables to the data structure.
boolean	addVariableToTree (int nbrNewVariables, IntArrayWrapper currentPath, int[] indexPath, int depth, InnerNode< U, L > oldRoot, InnerNode< U, L > currentNode, boolean possibleInconsistencies, boolean onIndexPath, int sender)
	This method is called when variables are received.
InnerNode< U, L >	createInnerNode (int numberOfChildren)
	Create an inner node with a specified number of children.
L	createLeaf (IntArrayWrapper currentPath, Good< Val, U > g, int child, final boolean withUB)
	Method to create a new leaf node.
InnerNode< U, L >	createPathNoUB (int depth, IntArrayWrapper currentPath, int[] partialPath, boolean real, Good< Val, U > g, int sender)
	Given a partial path, this method creates the path in the tree.
void	finalDomainSizeReceiver ()
	logs the reception of a domain size info message
int[]	getOwnVariableOptions (Val[] assignments)
	Given the assignment of variables in its separator, this method returns the utility for all domain elements of the own variable.
U	getUtilityLocalProblem (IntArrayWrapper currentPath)
	Given an assignment to all the variables, represented as a path in the tree, this method returns the utility given by the variable's local problem.
void	init (int numberOfChildren, U zero)
	Initialize all the variables of the tree.
void	initializeUpperBoundSums ()
	Initializes both the sum of bounds array and the powersOf2 array.
U	initiateBounds (InnerNode< U, L > currentNode, IntArrayWrapper currentPath, int depth, boolean onLocalPath, Good< Val, U > g, int sender)
	This method instantiates the upper bounds.
boolean	localPathAlive (int depth, InnerNode< U, L > currentNode)
	Used to check whether the local path chosen is still alive For debuggin purposes only.
boolean	pathAlive (int[] path, int depth, InnerNode< U, L > currentNode)
	Method to check whether the (possibly) partial path is alive, i.e.
void	updatePath (int depth, IntArrayWrapper currentPath, int[] partialPath, InnerNode< U, L > currentNode, Good< Val, U > g, U utilityDelta, int sender, boolean onLocalPath, final boolean withUB)
	This method walks trough the tree according to the given partial path and finds all leaf nodes that correspond to assignments that are compatible with the good to be added.
void	updateLocalProblem ()
void	updateUpperBoundSums (int child, U oldBound, U newBound)
	Updates the upperBoundSums array given the child that has changed its bound, the old bound and the new bound.
boolean	upperBoundChangesUtil (InnerNode< U, L > node, U UB)
U	recalculateUB (int depth, InnerNode< U, L > currentNodeUncast, U UBtoBeat, boolean recalculateUtil, boolean recalculateUB)
	This method recalculates the upper bound for a particular node.
void	removeInconsistencies (InnerNode< U, L > currentNode, int depth, IntArrayWrapper currentPath)
	This method checks whether any of the leafnodes have become infeasible due to the addition of a new variable.
boolean	removePath (int depth, InnerNode< U, L > currentNode, boolean onLocalPath)
	This method finds the leaf node corresponding to the current best assignment, removes all its children and sets its parent node to a dead node.
IntArrayWrapper	toKey (Val[] values, String[] variables, int sender)
	Takes a good received by a child and transforms the assignment to a key.
boolean	checkTree (int depth, InnerNode< U, L > currentNode, IntArrayWrapper currentPath, boolean UB, boolean checkLeafs, boolean checkSupport, boolean checkUtil)
	This method checks the tree on the following properties.
boolean	hasSupport (IntArrayWrapper currentPath)
	Method to check whether a particular leaf node has support, i.e.
boolean	setOldUB ()
	Used to set the old upperbound.

Protected Attributes
HashMap< String, Integer >	finalDomainSizeUnknownVariables
	the final domain sizes of as yet unknown variables
boolean[]	dummy
	Used to determine whether a variable has a dummy element or not.
int	dummyDepth
	The depth until where one can find dummy variables.
int	numberOfDummies
	Counts the number of dummy variables in the tree.
int	numberOfAncestors
	Stores the number of higher priority neighbours.
int	upperboundArraySize
	The size of the array containing precalculated upperbounds.
ArrayList< HashMap< IntArrayWrapper, U > >	goodsReceived
	For each child a map that stores the utilities received from children.
Protected Attributes inherited from frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >
HashMap< String, Integer >	variableToDepth
	links a variable to its depth in the tree.
HashMap< String, HashMap< Val, Integer > >	valuePointers
	Used to determine to which child a variable value corresponds to.
int[]	domainSize
	Stores, for a level in the tree, the size of the domain of the corresponding variable.
int[]	finalDomainSize
	Stores the final sizes of the domains of all the variables.
int[]	branchingFactor
	For every level of the tree, it stores the branching factor.
boolean[][]	childrenVariables
	Stores which variables are in a child's separator.
String[][]	childrenVariablesReportingOrder
	For each child it stores the order in which the variables are reported.
int[]	separatorSizePerChild
	Stores the number of reported variables per child.
boolean[]	ownVariables
	Stores which are this variable's neighbours.
ArrayList< HashMap< IntArrayWrapper, U > >	goodsReceived
	For each child a map that stores the utilities received from children.
boolean	storeReceivedGoods
	If domain or variable information is incomplete received goods must be stored, otherwise they can be discarded after processing.
boolean	hasLocalProblem
	`true` when this variable has a local problem, and false otherwise
U	optimalLocalUtility
	The optimal utility of the local problem.
int[]	optimalLocalPath
	The path of the currently optimal local solution.
U	localUpperBound
	The upperbound on all the completely unseen assignments.
U[]	upperBounds
	For each child it stores that last confirmed utility received.
U[]	upperBoundSums
	For every combination of children, this array contains the sum of upperBounds belonging to the selected children.
int	maxNumberLocalProblemOccurences
	The total number of times a solution to a local problem can be used in the separator problem.
int[]	powersOf2
	Pre-calculated powers of 2.
int	upperBoundIsInfiniteCounter
	Counts the number of children that have already sent at least one confirmed good.
int	upperBoundIsMinInfiniteCounter
	COunts the number of children that have already reported a minInfinite value.
HashMap< String, ArrayList< Val > >	domains
	The variable domains, where the position in the ArrayList denotes which child corresponds to the value.
int	numberOfChildren
	The number of children of the variable.
InnerNode< U, L >	root
	The root of the tree.
boolean	fullInfo
	True when the information on the final domain size is complete.
int	fullInfoCounter
	Counts the number of children from which one still needs to receive domain information.
boolean	stillToSend
	True if the domain information has not been requested yet.
L	leafNodeInstance
	An instance of a leaf node, used to create new instances.
U	oldUB
	Stores the UB as it was before a new good has been received.
int	localCounter
	The number of times the currently best local solution has NOT been used in the tree, i.e.
String[][]	unpackedVariablesPerChild
	Per child the unpacked variables (different from the reported variables).
HashMap< String, Val[]>	toBeProcessedDomains
	Domains still to be added to `domains`.

Private Member Functions
void	addVariableToTree (int nbrNewVariables, int depth, InnerNode< U, L > oldRoot, InnerNode< U, L > currentNode, boolean possibleInconsistencies)
	This method is called when variables are received.
InnerNode< U, L >	createPathWithUB (int depth, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.IntArrayWrapper currentPathUncast, int[] partialPath, boolean real, Good< Val, U > g, int sender)
	Given a partial path, this method creates the path in the tree.
InnerNode< U, L >	fillTree (InnerNode< U, L > example, int depth, IntArrayWrapper currentPath, boolean real, boolean onLocalPath, final boolean withUB, boolean onPartialPath, int[] partialPath, Good< Val, U > g, int sender)
	Fills a part of the tree that has been created by the reception of a new domain value.
void	fillTree (int depth, int[] partialPath, InnerNode< U, L > currentNode, IntArrayWrapper currentPath, Good< Val, U > g, U utilityDelta, int sender, boolean real, boolean onLocalPath, final boolean withUB, boolean onPartialPath, boolean fill)
	Fills a part of the tree that should be converted from dummy to real by the reception of a new domain value.
int	setFinalDomainSize (boolean[] change, String variable, int size, int depth)
	Sets the final size of the domain of a variable.
boolean	checkDummy (int depth, InnerNode< U, L > currentNode)
	Check whether only the parts of the tree that should be dummy are dummy.

Static Private Attributes
static final long	serialVersionUID = 5527333118050747769L
	Used for serialization.

Additional Inherited Members
Static Protected Attributes inherited from frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >
static final long	serialVersionUID
	Used for serialization.

Detailed Description

This class is designed to store GOODs received by a node from its children, and is used in the O-DPOP algorithm.

A GOOD contains an assignment to a set of variables, and a utility. A GOOD is identified by its assignment, and in this class the GOODs are ordered using a tree based on these assignments.

The basic functionality of this class is to either add a received GOOD to the tree, or to obtain the assignment that has the highest utility.

Author: Brammert

Parameters

<Val>	type used for variable values
<U>	type used for utility values
<L>	type used for the leaf node

Todo: write Unit test for this class

Constructor & Destructor Documentation

◆ InnerNodeTree() [1/6]

frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.InnerNodeTree	(	String	ownVariable,
		Val[]	ownVariableDomain,
		UtilitySolutionSpace< Val, U >	space,
		U	zero,
		int	numberOfChildren,
		U	infeasibleUtil,
		boolean	maximize,
		boolean	collectStats )

protected

A constructor.

Parameters

ownVariable	The variable that owns this tree
ownVariableDomain	The domain of `ownVariable`
space	The space controlled by this tree
zero	The zero utility
numberOfChildren	The number of children of this tree
infeasibleUtil	The infeasible utility
maximize	when `true` we are maximizing, when `false` we are minimizing
collectStats	`true` when statistics should be collected, and `false` otherwise

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren.

◆ InnerNodeTree() [2/6]

frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.InnerNodeTree	(	String	ownVariable,
		Val[]	ownVariableDomain,
		List< UtilitySolutionSpace< Val, U > >	spaces,
		U	zero,
		int	numberOfChildren,
		U	infeasibleUtil,
		boolean	maximize,
		boolean	collectStats )

protected

A constructor.

Parameters

ownVariable	The variable that owns this tree
ownVariableDomain	The domain of `ownVariable`
spaces	The space controlled by this tree
zero	The zero utility
numberOfChildren	The number of children of this tree
infeasibleUtil	The infeasible utility
maximize	when `true` we are maximizing, when `false` we are minimizing
collectStats	`true` when statistics should be collected, and `false` otherwise

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren.

◆ InnerNodeTree() [3/6]

frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.InnerNodeTree	(	L	leafNodeInstance,
		String	ownVariable,
		Val[]	ownVariableDomain,
		UtilitySolutionSpace< Val, U >	space,
		U	zero,
		int	numberOfChildren,
		U	infeasibleUtil,
		boolean	maximize,
		boolean	collectStats )

protected

A dummy constructor to be used by extending classes.

Parameters

leafNodeInstance	an instance of the leaf node class
ownVariable	The variable that owns this tree
ownVariableDomain	The domain of `ownVariable`
space	The local problem
zero	The zero utility
numberOfChildren	The number of children of this tree
infeasibleUtil	The infeasible utility
maximize	when `true` we are maximizing, when `false` we are minimizing
collectStats	`true` when statistics should be collected, and `false` otherwise

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.leafNodeInstance, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren.

◆ InnerNodeTree() [4/6]

frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.InnerNodeTree	(	L	leafNodeInstance,
		String	ownVariable,
		Val[]	ownVariableDomain,
		List< UtilitySolutionSpace< Val, U > >	spaces,
		U	zero,
		int	numberOfChildren,
		U	infeasibleUtil,
		boolean	maximize,
		boolean	collectStats )

protected

A dummy constructor to be used by extending classes.

Parameters

leafNodeInstance	an instance of the leaf node class
ownVariable	The variable that owns this tree
ownVariableDomain	The domain of `ownVariable`
spaces	The local problem
zero	The zero utility
numberOfChildren	The number of children of this tree
infeasibleUtil	The infeasible utility
maximize	when `true` we are maximizing, when `false` we are minimizing
collectStats	`true` when statistics should be collected, and `false` otherwise

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.leafNodeInstance, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren.

◆ InnerNodeTree() [5/6]

frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.InnerNodeTree	(	String	ownVariable,
		Val[]	ownVariableDomain,
		UtilitySolutionSpace< Val, U >	space,
		int	numberOfChildren,
		U	zero,
		L	leafNodeInstance,
		U	infeasibleUtil,
		boolean	maximize,
		boolean	collectStats )

A constructor.

Warning: we assume that the agent's own variable is put in the end of variables_order

Parameters

ownVariable	The variable ID
ownVariableDomain	The domain of `ownVariable`
space	The hypercube representing the local problem
numberOfChildren	The number of children
zero	The zero utility
leafNodeInstance	an instance of the leaf node class
infeasibleUtil	The infeasible utility
maximize	when `true` we are maximizing, when `false` we are minimizing
collectStats	`true` when statistics should be collected, and `false` otherwise

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.branchingFactor, createInnerNode(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.fullInfo, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.hasLocalProblem, init(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.leafNodeInstance, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.root, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.updateLocalProblem().

Here is the call graph for this function:

◆ InnerNodeTree() [6/6]

frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.InnerNodeTree	(	String	ownVariable,
		Val[]	ownVariableDomain,
		List< UtilitySolutionSpace< Val, U > >	spaces,
		int	numberOfChildren,
		U	zero,
		L	leafNodeInstance,
		U	infeasibleUtil,
		boolean	maximize,
		boolean	collectStats )

A constructor.

Warning: we assume that the agents own variable is put in the end of variables_order

Parameters

ownVariable	The variable ID
ownVariableDomain	The domain of `ownVariable`
spaces	The hypercubes representing the local problem
numberOfChildren	The number of children
zero	The zero utility
leafNodeInstance	an instance of the leaf node class
infeasibleUtil	The infeasible utility
maximize	when `true` we are maximizing, when `false` we are minimizing
collectStats	`true` when statistics should be collected, and `false` otherwise

References createInnerNode(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.domainSize, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.fullInfo, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.hasLocalProblem, init(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.leafNodeInstance, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.root, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.updateLocalProblem().

Here is the call graph for this function:

Member Function Documentation

◆ add() [1/2]

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.add	(	Good< Val, U >	g,
		int	sender )

Adds a good to the tree.

Author: Brammert Ottens, 10 nov 2009

Parameters

g	the good to be added
sender	the child that reported the good

Returns: true when a new variable has been added, and false otherwise

Here is the call graph for this function:

◆ add() [2/2]

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.add	(	Good< Val, U >	g,
		int	sender,
		HashMap< String, Val[]>	domains )

See also: frodo2.algorithms.odpop.goodsTree.GoodsTree.add(frodo2.algorithms.odpop.Good, int, java.util.HashMap)

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.domains.

◆ addNewDomainElement()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.addNewDomainElement ( HashMap< String, Val > newValues )

protected

This method adds a new variable to the data structure.

Note that it does not need to update the tree, this automatically happens when adding the compatible paths to the tree

Parameters

newValues The new domain elements that must be added

Referenced by add().

Here is the call graph for this function:

◆ addNewDomainElementNoUB()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.addNewDomainElementNoUB	(	int	depth,
		int	horizon,
		IntArrayWrapper	currentPath,
		int[]	partialPath,
		int[]	newDomainPath,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	currentNodeUncast,
		Good< Val, U >	g,
		U	utilityDelta,
		int	sender,
		boolean	onPartialPath,
		boolean	fill )

protected

This method is called when a new domain element is discovered before the UBs can be calculated.

It searches the tree up to the horizon depth for new branches to add. A new branch is only added when it represents a new domain element found in this round

Parameters

depth	the current depth
horizon	the maximal depth at which a dummy node can be found
currentPath	the current path taken
partialPath	the partial path defined by the received good
newDomainPath	the partial path defined by the new domain values
currentNodeUncast	the node currently visited
g	the received good
utilityDelta	the difference with the previously reported utility value for this particular good
sender	the sender of the good
onPartialPath	`true` when the partial path is still being followed, and `false` otherwise
fill	`true` when the tree should be extended by copying an already existing branch

Referenced by add(), and addNewDomainElementNoUB().

Here is the call graph for this function:

◆ addNewDomainElementWithUB()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.addNewDomainElementWithUB	(	int	depth,
		int	horizon,
		IntArrayWrapper	currentPath,
		int[]	partialPath,
		int[]	newDomainPath,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	currentNodeUncast,
		Good< Val, U >	g,
		U	utilityDelta,
		int	sender,
		boolean	onPartialPath,
		boolean	fill )

protected

This method is called when a new domain element is discovered while the UB is already set.

It searches the tree up to the horizon depth for new branches to add. A new branch is only added when it represents a new domain element found. If the upper bound must be recalculated this is done.

Parameters

depth	The current depth
horizon	The depth until which the search for non-existing children must continue
currentPath	The current path
partialPath	The path dictated by the received good
newDomainPath	the partial path defined by the new domain values
currentNodeUncast	the node currently visited
g	the received good
utilityDelta	the difference between the already received utility and the new utility defined by the received good. Is only used in ASODPOP
sender	the sender of the good
onPartialPath	`true` when the partial path is still being followed, and `false` otherwise
fill	`true` when the tree should be extend by copying an already existing branch

Todo: copy this function into the ASODPOp goodstree and change it!

child is max util candidate

Todo: : again, in the case of ASODPOP this should only be done when the good is confirmed

References addNewDomainElementWithUB(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.getExample().

Referenced by add(), and addNewDomainElementWithUB().

Here is the call graph for this function:

◆ addNewVariable()

int[] frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.addNewVariable	(	String[]	allVariables,
		HashMap< String, Val >	newVariables,
		int	sender )

protected

This method adds new variables to the data structure.

Parameters

allVariables	The current variables
newVariables	The variables to be added
sender	The child that reported the variables

Returns: the number of new variables

Referenced by add().

Here is the call graph for this function:

◆ addVariableToTree()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.addVariableToTree	(	int	nbrNewVariables,
		int	depth,
		InnerNode< U, L >	oldRoot,
		InnerNode< U, L >	currentNode,
		boolean	possibleInconsistencies )

private

This method is called when variables are received.

The new variables are placed at the root

Parameters

nbrNewVariables	The number of variables to add
depth	The current depth
oldRoot	The old root
currentNode	The current node
possibleInconsistencies	`true` when the reception of a new variable can make certain solutions infeasible

References addVariableToTree(), createInnerNode(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.getMaxChild(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.getMaxUBChild(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.removeInconsistencies(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.setChild(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.setUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNode, L extends LeafNode >.setUtil(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.IntArrayWrapper.setValue().

Referenced by add(), and addVariableToTree().

Here is the call graph for this function:

◆ changeDummyToReal() [1/2]

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.changeDummyToReal	(	int	depth,
		InnerNode< U, L >	currentNode,
		boolean	change )

protected

Changes all dummy children of the variables in dummyToReal to real nodes.

Parameters

depth	the current depth
currentNode	the node currently being visited
change	`true` when we still want to change things

References changeDummyToReal(), and dummyDepth.

Referenced by addNewDomainElement(), changeDummyToReal(), and changeDummyToReal().

Here is the call graph for this function:

◆ changeDummyToReal() [2/2]

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.changeDummyToReal	(	int	depth,
		IntArrayWrapper	currentPath,
		InnerNode< U, L >	currentNode,
		boolean	change )

protected

Changes all dummy children of the variables in dummyToReal to real nodes.

Parameters

depth	the current depth
currentPath	the path taken through the tree to get here
currentNode	the node currently being visited
change	`true` when we still want to change things

References changeDummyToReal().

Here is the call graph for this function:

◆ checkDummy()

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.checkDummy	(	int	depth,
		InnerNode< U, L >	currentNode )

private

Check whether only the parts of the tree that should be dummy are dummy.

Author: Brammert Ottens, 30 sep 2009

Parameters

depth	The current depth
currentNode	the current node being visited

Returns: true

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.branchingFactor, checkDummy(), dummy, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.getChild().

Referenced by checkDummy().

Here is the call graph for this function:

◆ checkLeaf()

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.checkLeaf	(	L	leaf,
		IntArrayWrapper	currentPath,
		boolean	checkUB,
		U	utility,
		int	sender )

Method to check that the utility and UB are consistent with the available information.

The utility should match exactly, but because UBs are only recomputed when necessary, and then should only decrease by such a recomputation, the stored UB should be at least as high as the real UB

Parameters

leaf	the leaf to be checked
currentPath	the path to this leaf
checkUB	`true` when the UB must be checked
utility	the utility reported by the sender
sender	the sender of the good

Returns: always returns true

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.childrenVariables, frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.IntArrayWrapper.getPartialAssignment(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.getUtilityLocalProblem(), goodsReceived, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.upperBounds.

Referenced by checkTree(), createLeaf(), createLeaf(), createPathWithUB(), fillTree(), and updatePath().

Here is the call graph for this function:

◆ checkTree()

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.checkTree	(	int	depth,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	currentNodeUncast,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.IntArrayWrapper	currentPathUncast,
		boolean	UB,
		boolean	checkLeafs,
		boolean	checkSupport,
		boolean	checkUtil )

protected

This method checks the tree on the following properties.

the UB is properly propagated
the utility is properly propagated
every leaf node with support is present
no UB is greater than the old upper bound

Parameters

depth	the current depth
currentNodeUncast	the current node being visited
currentPathUncast	the current path taken
UB	the current UB
checkLeafs	`true` when the leaves are to be checked
checkSupport	`check` whether existing leaf nodes actually have support
checkUtil	`true` when utility values should be checked

Returns: always returns true

Referenced by add(), addNewDomainElementNoUB(), checkTree(), fillTree(), initiateBounds(), and updatePath().

Here is the call graph for this function:

◆ createInnerNode() [1/2]

InnerNode< U, L > frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.createInnerNode ( int numberOfChildren )

protected

See also: frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.createInnerNode(int)

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren.

Referenced by add(), addVariableToTree(), createPathNoUB(), createPathWithUB(), fillTree(), initiateBounds(), InnerNodeTree(), and InnerNodeTree().

◆ createInnerNode() [2/2]

InnerNode< U, L > frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.createInnerNode ( Node[] children )

protected

See also: frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.createInnerNode(frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.Node[])

◆ createIntArrayWrapper() [1/2]

IntArrayWrapper frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.createIntArrayWrapper ( int size )

See also: frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.createIntArrayWrapper(int)

◆ createIntArrayWrapper() [2/2]

IntArrayWrapper frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.createIntArrayWrapper ( int[] array )

See also: frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.createIntArrayWrapper(int[])

Referenced by add().

◆ createLeaf() [1/2]

L frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.createLeaf	(	IntArrayWrapper	currentPath,
		boolean	real,
		final boolean	withUB )

protected

Method to create a new leaf node.

Parameters

currentPath	The path to the leaf
real	`true` when the leaf points to a real assignment
withUB	`true` when the upper bound must be set

Returns: the new leaf node

Here is the call graph for this function:

◆ createLeaf() [2/2]

L frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.createLeaf	(	IntArrayWrapper	currentPath,
		boolean	real,
		Good< Val, U >	g,
		int	child,
		final boolean	withUB )

protected

Method to create a new leaf node.

Parameters

currentPath	The path to the leaf
real	`true` when the leaf points to a real assignment
g	the received good
child	the child that reported it
withUB	`true` when the upper bound must be set

Returns: the new leaf node

Referenced by createPathNoUB(), createPathWithUB(), fillTree(), initiateBounds(), and updatePath().

Here is the call graph for this function:

◆ createPathNoUB()

frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.createPathNoUB	(	int	depth,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.IntArrayWrapper	currentPathUncast,
		int[]	partialPath,
		boolean	real,
		Good< Val, U >	g,
		int	sender )

protected

Given a partial path, this method creates the path in the tree.

This method should only be called after domain information is complete!

Parameters

depth	the current depth
currentPathUncast	the path taken
partialPath	the partial path defined by the received good
real	`true` when still in the real part of the tree
g	the received good
sender	the sender of the good

Returns: a new InnerNode

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.branchingFactor, createInnerNode(), createLeaf(), createPathNoUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.domains, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.domainSize, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.getMaxChild(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.Node >.getUtil(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.setChild(), frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNode, L extends LeafNode >.setUtil(), frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.IntArrayWrapper.setValue(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.Node >.utilCandidate().

Referenced by addNewDomainElementNoUB(), createPathNoUB(), and updatePath().

Here is the call graph for this function:

◆ createPathWithUB()

InnerNode< U, L > frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.createPathWithUB	(	int	depth,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.IntArrayWrapper	currentPathUncast,
		int[]	partialPath,
		boolean	real,
		Good< Val, U >	g,
		int	sender )

private

Given a partial path, this method creates the path in the tree.

This method should only be called after domain information is complete!

Parameters

depth	the current depth
currentPathUncast	the path taking in the tree
partialPath	the partial path defined by the received good
real	`true` if the parent is a real node
g	the received good
sender	the sender of the good

Returns: a new InnerNode

Referenced by createPathWithUB(), and updatePath().

Here is the call graph for this function:

◆ fillTree() [1/2]

InnerNode< U, L > frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.fillTree	(	InnerNode< U, L >	example,
		int	depth,
		IntArrayWrapper	currentPath,
		boolean	real,
		boolean	onLocalPath,
		final boolean	withUB,
		boolean	onPartialPath,
		int[]	partialPath,
		Good< Val, U >	g,
		int	sender )

private

Fills a part of the tree that has been created by the reception of a new domain value.

Author: Brammert Ottens, 30 sep 2009

Parameters

depth	the current depth
currentPath	the current path taken through the tree. Is only up to date up to depth
real	`true` when the current node should be a real node, and `false` when it should be a dummy
onLocalPath	`true` when we are still following the path of the currently best local solution
withUB	`true` when the UB must be instatiated as well
example	the example that is to be copied
onPartialPath	`true` then the followed path is the same as the path defined by the received good
partialPath	the path defined by the received good
g	the received good
sender	the sender of the good

Returns: a new node

Referenced by addNewDomainElementNoUB(), fillTree(), fillTree(), initiateBounds(), and updatePath().

Here is the call graph for this function:

◆ fillTree() [2/2]

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.fillTree	(	int	depth,
		int[]	partialPath,
		InnerNode< U, L >	currentNode,
		IntArrayWrapper	currentPath,
		Good< Val, U >	g,
		U	utilityDelta,
		int	sender,
		boolean	real,
		boolean	onLocalPath,
		final boolean	withUB,
		boolean	onPartialPath,
		boolean	fill )

private

Fills a part of the tree that should be converted from dummy to real by the reception of a new domain value.

Author: Brammert Ottens, 30 sep 2009

Parameters

depth	the current depth
partialPath	the partial path defined by the received good
currentNode	the current node
currentPath	the current path taken through the tree. Is only up to date up to depth
g	the received good
utilityDelta	the difference with the previously reported utility for this particlar good
sender	the sender of the good
real	`true` when the current node should be a real node, and `false` when it should be a dummy
onLocalPath	`true` when we are still following the path of the currently best local solution
withUB	`true` when the UB must be instantiated as well
onPartialPath	`true` when we are still on the partial path
fill	`true` when the tree should be extended by copying an already existing branch

References fillTree(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.ubCandidate().

Here is the call graph for this function:

◆ findUnused()

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.findUnused	(	int	depth,
		int[]	localPath,
		InnerNode< U, L >	currentNode )

protected

Check whether the assignment to the local problem, represented by localPath, can still be used somewhere.

Is only called from removeAmax()!!

Author: Brammert Ottens, 23 sep 2009

Parameters

depth	the current depth
localPath	the part of the assignment to the local problem that has just been sent as a good
currentNode	the current node being visited

Returns: true when there still is some use for the local problem assignment, and false otherwise

References findUnused().

Referenced by findUnused().

Here is the call graph for this function:

◆ getDomains()

Val[][] frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.getDomains ( )

See also: frodo2.algorithms.odpop.goodsTree.GoodsTree.getDomains()

◆ getOwnVariableOptions()

U frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.getOwnVariableOptions	(	int[]	optimalPath,
		Val[]	assignments )

protected

Given the assignment of variables in its separator, this method returns the utility for all domain elements of the own variable.

Parameters

optimalPath	the path trough the tree that leads to the optimal leafnode
assignments	collection of assignments of variables in the separator

Returns: an array of utilities

References getOwnVariableOptions(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.root, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.valuePointers.

Referenced by getOwnVariableOptions().

Here is the call graph for this function:

◆ hasSupport()

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.hasSupport ( IntArrayWrapper currentPath )

protected

Method to check whether a particular leaf node has support, i.e.

some child has reported an assignment compatible with currentPath

Parameters

currentPath the path that leads to the leaf

Returns: true if the path has support and false otherwise

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.childrenVariables, frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.IntArrayWrapper.getPartialAssignment(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.getUtilityLocalProblem(), goodsReceived, hasSupport(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.storeReceivedGoods.

Referenced by checkTree(), createLeaf(), createLeaf(), fillTree(), and hasSupport().

Here is the call graph for this function:

◆ init()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.init	(	int	numberOfChildren,
		U	zero )

protected

Initialize all the variables of the tree.

Parameters

numberOfChildren	The number of children
zero	The zero utility

Referenced by InnerNodeTree(), and InnerNodeTree().

◆ initiateBounds()

U frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.initiateBounds	(	frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	currentNodeUncast,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.IntArrayWrapper	currentPathUncast,
		int	depth,
		boolean	onLocalPath,
		Good< Val, U >	g,
		int	sender )

protected

This method adds the dummy part to the tree.

It searches through the tree from left to right. Every time it needs to add a dummy node, it copies the tree below the left most child of the current node into the dummy node. Concurrently it also instantiates the upper bounds

Parameters

currentNodeUncast	the node currently being visited
currentPathUncast	the path taken
depth	the current depth
onLocalPath	`true` when we are still following the path of the currently best local solution
g	the received good
sender	the sender of the good

Returns: the upperBound for this node

Referenced by add(), and initiateBounds().

Here is the call graph for this function:

◆ removeDummies()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.removeDummies	(	int	removalDepth,
		boolean[]	change,
		int	depth,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	currentNodeUncast )

protected

Remove the dummy element for the variables marked in change.

Parameters

removalDepth	the maximal depth until where dummy elements are to be found
change	for each variable whether the dummy elements must be removed
depth	the current depth
currentNodeUncast	the current node that is being visited

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.branchingFactor, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.Node >.hasUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.Node >.isAlive(), removeDummies(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNode, L extends LeafNode >.removeDummy().

Referenced by removeDummies(), and setFinalDomainSize().

Here is the call graph for this function:

◆ setFinalDomainSize() [1/2]

int frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.setFinalDomainSize	(	boolean[]	change,
		String	variable,
		int	size,
		int	depth )

private

Sets the final size of the domain of a variable.

Parameters

change	boolean to store the variables whose size has been set
variable	the variable whose final domain size is to be set
size	the final domain size
depth	the depth of `variable`

Returns: the depth of the variable to be changed

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.branchingFactor, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.domainSize, dummy, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.finalDomainSize, and numberOfDummies.

◆ setFinalDomainSize() [2/2]

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.setFinalDomainSize	(	String[]	variables,
		int[]	domainSize )

See also: frodo2.algorithms.odpop.goodsTree.GoodsTree.setFinalDomainSize(java.lang.String[], int[])

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.domainSize, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.finalDomainSizeReceiver(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.fullInfoCounter, removeDummies(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.root, setFinalDomainSize(), and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.variableToDepth.

Referenced by setFinalDomainSize().

Here is the call graph for this function:

◆ toString()

String frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.toString ( )

Method used for debugging purposes.

It prints the state of the tree

See also: java.lang.Object#toString()

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.branchingFactor, goodsReceived, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.hasLocalProblem, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.localUpperBound, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.numberOfChildren, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.optimalLocalPath, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.root, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.storeReceivedGoods.

◆ updatePath()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.updatePath	(	int	depth,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.IntArrayWrapper	currentPathUncast,
		int[]	partialPath,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	currentNodeUncast,
		Good< Val, U >	g,
		U	utilityDelta,
		int	sender,
		boolean	onLocalPath,
		final boolean	withUB )

protected

This method walks trough the tree according to the given partial path and finds all leaf nodes that correspond to assignments that are compatible with the good to be added.

Parameters

depth	The current depth
currentPathUncast	The current path
partialPath	The path dictated by the received good
currentNodeUncast	The current node
g	the utility reported
utilityDelta	The difference with the previously reported utility for the assignment belonging to the partial path
sender	The sender of the good
onLocalPath	`true` when we are still following the path of the currently best local solution
withUB	`true` when the UB must be updated as well

Referenced by add(), and updatePath().

Here is the call graph for this function:

◆ upperBoundChangesUtil()

boolean frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.upperBoundChangesUtil	(	frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	node,
		U	UB )

protected

See also: frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree.upperBoundChangesUtil(frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, frodo2.solutionSpaces.Addable)

Member Data Documentation

◆ dummy

boolean [] frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.dummy

protected

Used to determine whether a variable has a dummy element or not.

Referenced by add(), addNewDomainElement(), addNewVariable(), checkDummy(), checkTree(), createPathWithUB(), init(), initiateBounds(), setFinalDomainSize(), and updatePath().

◆ dummyDepth

int frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.dummyDepth

protected

The depth until where one can find dummy variables.

Referenced by addNewVariable(), changeDummyToReal(), and init().

◆ finalDomainSizeUnknownVariables

HashMap<String, Integer> frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.finalDomainSizeUnknownVariables

protected

the final domain sizes of as yet unknown variables

Referenced by addNewVariable(), and init().

◆ goodsReceived

ArrayList<HashMap<IntArrayWrapper, U> > frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.goodsReceived

protected

For each child a map that stores the utilities received from children.

This is needed due to the assumption that both domain and variable information can be incomplete

Referenced by add(), checkLeaf(), createLeaf(), createLeaf(), hasSupport(), init(), toString(), and updatePath().

◆ numberOfAncestors

int frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.numberOfAncestors

protected

Stores the number of higher priority neighbours.

Referenced by init().

◆ numberOfDummies

int frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.numberOfDummies

protected

Counts the number of dummy variables in the tree.

Referenced by setFinalDomainSize().

◆ serialVersionUID

final long frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.serialVersionUID = 5527333118050747769L

staticprivate

Used for serialization.

◆ upperboundArraySize

int frodo2.algorithms.odpop.goodsTree.InnerNodeTree.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.upperboundArraySize

protected

The size of the array containing precalculated upperbounds.

Referenced by init().

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

src/frodo2/algorithms/odpop/goodsTree/InnerNodeTree/InnerNodeTree.java

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Static Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ InnerNodeTree() [1/6]

◆ InnerNodeTree() [2/6]

◆ InnerNodeTree() [3/6]

◆ InnerNodeTree() [4/6]

◆ InnerNodeTree() [5/6]

◆ InnerNodeTree() [6/6]

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ addNewDomainElement()

◆ addNewDomainElementNoUB()

◆ addNewDomainElementWithUB()

◆ addNewVariable()

◆ addVariableToTree()

◆ changeDummyToReal() [1/2]

◆ changeDummyToReal() [2/2]

◆ checkDummy()

◆ checkLeaf()

◆ checkTree()

◆ createInnerNode() [1/2]

◆ createInnerNode() [2/2]

◆ createIntArrayWrapper() [1/2]

◆ createIntArrayWrapper() [2/2]

◆ createLeaf() [1/2]

◆ createLeaf() [2/2]

◆ createPathNoUB()

◆ createPathWithUB()

◆ fillTree() [1/2]

◆ fillTree() [2/2]

◆ findUnused()

◆ getDomains()

◆ getOwnVariableOptions()

◆ hasSupport()

◆ init()

◆ initiateBounds()

◆ removeDummies()

◆ setFinalDomainSize() [1/2]

◆ setFinalDomainSize() [2/2]

◆ toString()

◆ updatePath()

◆ upperBoundChangesUtil()

Member Data Documentation

◆ dummy

◆ dummyDepth

◆ finalDomainSizeUnknownVariables

◆ goodsReceived

◆ numberOfAncestors

◆ numberOfDummies

◆ serialVersionUID

◆ upperboundArraySize