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.InnerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >:

[legend]

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, HashMap< String, Val[]> domains)
	Adds a good to the tree.
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 (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.
frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	createInnerNode (int numberOfChildren)
frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	createInnerNode (Node< U >[] children)
void	updateLocalProblem ()
U	recalculateUB (int depth, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > currentNode, U UBtoBeat, boolean recalculateUtil, boolean recalculateUB)
	This method recalculates the upper bound for a particular node.
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.

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

Additional Inherited Members
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`.

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/4]

frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.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() [2/4]

frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.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() [3/4]

frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.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 createInnerNode(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.fullInfo, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.hasLocalProblem, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.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 updateLocalProblem().

Here is the call graph for this function:

◆ InnerNodeTree() [4/4]

frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.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 >.fullInfo, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.hasLocalProblem, frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.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 updateLocalProblem().

Here is the call graph for this function:

Member Function Documentation

◆ add()

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

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
domains	reported domains

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

Here is the call graph for this function:

◆ createInnerNode() [1/2]

frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.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(), InnerNodeTree(), and InnerNodeTree().

◆ createInnerNode() [2/2]

frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L > frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.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[])

◆ recalculateUB()

U frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable< U >, L extends LeafNode< U > >.recalculateUB	(	int	depth,
		frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode< U, L >	currentNode,
		U	UBtoBeat,
		boolean	recalculateUtil,
		boolean	recalculateUB )

protected

This method recalculates the upper bound for a particular node.

If the upper bound of this node is already up to date nothing happens. If not, the method searches further down the tree to find the actual current upper bound

Parameters

depth	the current depth
currentNode	the node that is currently visited
UBtoBeat	the UB that needs to be beat
recalculateUtil	`true` when the recalculation of the utility can make a difference higher up
recalculateUB	`true` when the recalculation of the upperbound can make a difference higher up

Returns: the new upper bound for currentNode

References frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.checkTree(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNode, L extends LeafNode >.getChild(), recalculateUB(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.UBexists(), frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.upperBoundSums, and frodo2.algorithms.odpop.goodsTree.InnerNodeTreeFullDomain.InnerNodeTree< Val, U, L >.Utilexists().

Referenced by recalculateUB().

Here is the call graph for this function:

◆ updateLocalProblem()

void frodo2.algorithms.odpop.goodsTree.InnerNodeTreeBinaryDomains.InnerNodeTree< Val extends Addable< Val >, U extends Addable, L extends LeafNode >.updateLocalProblem ( )

protected

Author: Brammert Ottens, 16 nov 2009 Find the next best local solution that is still allowed

Referenced by InnerNodeTree(), and InnerNodeTree().

Here is the call graph for this function:

Member Data Documentation

◆ serialVersionUID

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

staticprotected

Used for serialization.

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

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

Public Member Functions

Protected Member Functions

Static Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ InnerNodeTree() [1/4]

◆ InnerNodeTree() [2/4]

◆ InnerNodeTree() [3/4]

◆ InnerNodeTree() [4/4]

Member Function Documentation

◆ add()

◆ createInnerNode() [1/2]

◆ createInnerNode() [2/2]

◆ recalculateUB()

◆ updateLocalProblem()

Member Data Documentation

◆ serialVersionUID