OBJECTS

class ComputationGraph(graph_type: str | None = None, nodes: Iterable[ComputationNode] | None = None)

A ComputationGraph represents a graph of computation for a dcop. Many different graphs can be defined from the same dcop, depending on the kind of algorithm that will be used to solve the dcop. For example, max-sum is based on a factor graph while dpop is based on a DFS pseudo-tree. For this reason, we try to keep the computation graph definition both flexible and generic, so that it can accommodate and represents many kind of graph models.

Concrete subclasses MUST provide nodes and links attributes (or properties) that return respectively the list of `ComputationNode`s and the list of `Link`s of the graph

Parameters:

  • graph_type –

  • nodes (ComputationNodes) – an iterable of ComputationNode objects or None

Examples

>>> cg = ComputationGraph()
>>> cg.nodes
[]

>>> cg = ComputationGraph(nodes=[ComputationNode('a1'),
...                              ComputationNode('a2')])
>>> cg.nodes
[ComputationNode(a1), ComputationNode(a2)]
computation(node_name: str) → ComputationNode

Return a computation node from its name.

Parameters:

node_name (str) – a computation node name

Return type:

A ComputationNode object with this name.

Raises:

A KeyError if no computation with this name could be found –

Examples

>>> cg = ComputationGraph()
>>> cg.nodes = [ComputationNode('a1'), ComputationNode('a2')]
>>> cg.computation('a1')
ComputationNode(a1)

Return the links involving a given computation.

Parameters:

node_name (str) – a computation node name

Return type:

An iterable of Link objects involving the computation

Examples

>>> cg = ComputationGraph(
...         nodes= [ComputationNode('a1', neighbors=['a2']),
...                 ComputationNode('a2', neighbors=['a1'])])
>>> Link({'a1', 'a2'}) in cg.links_for_node('a1')
True
neighbors(node_name: str) → Iterable[str]

Return the neighbors of a computation node.

Iterates over names of neighbors instead of ComputationNode objects.

Parameters:

node_name (string) – a computation node name.

Returns:

  • An iterable over the names of the neighbors of the computation in the

  • computation graph.

Examples

>>> cg = ComputationGraph(
...         nodes= [ComputationNode('a1', neighbors=['a2']),
...                 ComputationNode('a2', neighbors=['a1'])])
>>> list(cg.neighbors('a1'))
['a2']
class ComputationNode(name: str, node_type: str | None = None, links: Iterable[Link] | None = None, neighbors: Iterable[str] | None = None)

A computation node represents one computation in a computation graph. It is not an implementation of an actual computation but contains all the information needed to instantiate a concrete computation.

ComputationNode is the base class that be used for all concrete computation graph models.

Notes

It must be possible to transfer (e.g. network) the definitions of a computation node (a serialized ComputationNode instance) and all edges (a serialized Link instances) where it is the source to a remote agent where the actual computation will be instantiated. This means a concrete computation node instance must be serializable (using the SimpleRepr mixin) and must include all information required for the computation (e.g. Variable and associated domain, Relation for the constraints , etc.).

Any subclass must also implement __hash__() and __eq__().

Parameters:

  • name (str) – the name of the computation node, usually the name of the variable ( or constraint) the computation is responsible for.

  • node_type (str) – type of the node, useful when the computation has several type of nodes (e.g. factor graphs)

  • neighbors (Iterable of neighbors' names, as string) – The name of the neighbor’s node. The neighbors can also be given with the links argument, but you cannot use links and neighbors arguments simultaneously.

  • links (Iterable of Links) – Link objects pointing to the neighbors in the graph. For complex graph it can be necessary to give links instead of neighbors names, as it allow attaching a type to the link (like pseudo child in pseudo-Tree graph) or use hyperlink.

A Computation link represent an edge, in a computation graph, from one computation node to another.

To accommodate various type of graphs, the Link base class models a hyper-edge (i.e. an edge which can have more than two vertices) and has a type attribute, which can be used to represent different kinds of relation between the nodes involved in the edge (e.g. parent, children, pseudo children, neighbor, …)

When necessary, specific graph model can extend this base class to define other types of edges : binary, directed, etc.

In any case, all edge object mus be serializable, using the SimpleRepr mixin, and must implement __hash__() and __eq__().