PSEUDOTREE

Pseudo tree computation graphs are DFS trees built from the constraint graph where pseudo-parent and pseudo-children links are added to the tree.

This model is typically used for the dpop algorithm.

class ComputationPseudoTree(roots: Iterable[_BuildingNode])

Pseudo-tree based computation graph.

The kind of computation graph is used by algorithm that need to build a pseudo-tree from the constraints graph.

class PseudoTreeLink(link_type: str, source: str, target: str)

Link between to node in a pseudo-tree computation graph.

property source: str

The source of the link.

Returns:

The name of source PseudoTreeNode computation node.

Return type:

str

property target

The target of the link.

Returns:

The name of target PseudoTreeNode computation node.

Return type:

str

class PseudoTreeNode(variable: Variable, constraints: Iterable[RelationProtocol], links: Iterable[PseudoTreeLink], name: str | None = None)

ComputationNode for Pseudo-tree computation graph.

Parameters:

• variable (Variable) – The variable this computation is responsible for.

• constraints (iterable of constraints-like objects) – The constraints the variable depends on.

• links (iterable of PseudoTreeLink) – The links are mandatory because we cannot extract them from the variable and constraints of this node (as it is the case for factor graph or hyper-graph), they depends on the DFS pseudo tree generation.

• name (str) – The name of the node. If given given, the name of the variable is used as the node name.

build_computation_graph(dcop: DCOP, variables: Iterable[Variable] | None = None, constraints: Iterable[RelationProtocol] | None = None) → ComputationPseudoTree

Build a computation pseudo-tree graph for the DCOP.

A computation graph is generally built from a DCOP, however it is also possible to build it by simply passing the variables and constraints.

Notes

With DFS pseudo tree, all the DCOP is needed, you cannot build a sub-graph by passing a subset of the variables and constraints.

Parameters:

• dcop (DCOP) – DCOP object to build the computation graph from.When this parameter is used, the constraints and variables parameters MUST NOT be used.

• variables (iterable of Variables objects) – The variables to build the computation graph from. When this parameter is used, the constraints parameter MUST also be given.

• constraints (iterable of Constraints objects) – The constraints to build the computation graph from. When this parameter is used, the variables parameter MUST also be given.

Returns:

In pseudo-tree graph for the variables and constraints

Return type:

ComputationPseudoTree

Raises:

ValueError – If both dcop and one of the variables or constraints arguments have been used.

get_dfs_relations(tree_node: PseudoTreeNode)

Utility function to get lists of descendants and ancestors.

Parameters:

tree_node (PseudoTreeNode) – a node in a dfs tree

Returns:

a tuple (parent, pseudo_parents, children, pseudo_children)

Return type:

tuple

tree_str_desc(root, indent_num=0)

Build a string representing a pseudo-tree :param root: :param indent_num: :return: