Algorithms

The pydcop.algorithms module contains the implementation of all DCOP algorithm supported by pyDCOP.

For documentation on how to develop new algorithms, look at the this tutorial and this documentation.

pydcop.algorithms also defines objects and functions that are used to describe and define DCOP algorithms’ computations.

Classes

ComputationDef(node, algo)

Full definition of a Computation.

AlgorithmDef(algo, params[, mode])

Full definition of an algorithm's instance.

AlgoParameterDef(name, type[, values, ...])

Definition of an algorithm's parameter.

Functions

list_available_algorithms()

The list of available DCOP algorithms.

load_algorithm_module(algo_name)

Dynamically load an algorithm module.

prepare_algo_params(params, ...)

Ensure algorithm's parameters are valid.

check_param_value(param_val, param_def)

Check if param_val is a valid value for a AlgoParameterDef
class AlgoParameterDef(name: str, type: str, values: List[str] | None = None, default_value: str | int | float | None = None)

Definition of an algorithm’s parameter.

AlgoParameterDef instances are used to describe the parameters supported by an algorithms.

For example, dsa supports 3 parameters, which declared with a module-level variable in dsa.py

algo_params = [
  AlgoParameterDef('probability', 'float', None, 0.7),
  AlgoParameterDef('variant', 'str', ['A', 'B', 'C'], 'B'),
  AlgoParameterDef('stop_cycle', 'int', None, 0)]
default_value: str | int | float

Default value of the parameter.

name: str

Name of the parameter (str).

type: str

Type of the parameter (str)

This must be either int, float or str

values: List[str] | None

List of valid values for this parameter.

Can be None if non-applicable (for a float paramater, for example).

class AlgorithmDef(algo: str, params: Dict[str, Any], mode: str = 'min')

Full definition of an algorithm’s instance.

An AlgorithmDef represents a DCOP algorithm instance with all parameters needed to run it. These parameters depend on the considered algorithm (e.g. variant A, B or C for DSA and damping factor for maxsum) and are defined with AlgoParameterDef.

Notes

When using the constructor, params must already be a dict of valid parameters for this algorithm and no validity check is performed.

Most of the time, you should use the AlgorithmDef.build_with_default_param() static method to create an instance of AlgorithmDef, as it automatically uses default arguments for the requested algorithm.

Parameters:

  • algo (str) – Name of the algorithm. It must be the name of a module in the pydcop.algorithms package.

  • params (dict) – Dictionary of algorithm-specific configuration and parameters

  • mode (str) – 'min' of 'max', defaults to 'min'

property algo: str

The name of the algorithm.

The name of the algorithm is the name of a module in the pydcop.algorithms package.

Returns:

str

Return type:

the name of the algorithm.

static build_with_default_param(algo: str, params: Dict[str, Any] | None = None, mode: str = 'min', parameters_definitions: List[AlgoParameterDef] | None = None)

Creates an AlgoDef instance with defaults parameter values.

Parameters passed as argument are checked for validity. If a value is not provided for some required parameters, the default value is used.

Parameters:

  • algo (str) – Name of the algorithm. It must be the name of a module in the pydcop.algorithms package.

  • mode (str) – 'min' of 'max', defaults to 'min'

  • params (dict) – Dictionary of algorithm-specific parameters. If a value is not provided for some required parameters, their default value is used.

  • parameters_definitions (list of AlgoParameterDef) – Algorithms parameters definition. If not provided, their are automatically loaded form the algorithm’s module.

Returns:

algodef – An instance with defaults parameter values.

Return type:

AlgoDef

Raises:

ValueError: – If an unknown parameter is passed or if a parameter value does not respect the parameter definition.

Examples

>>> algo_def = AlgorithmDef.build_with_default_param('dsa', {'variant': 'B'})
>>> algo_def.param_value('probability')
0.7
>>> algo_def.param_value('variant')
'B'
property mode: str

The mode, 'min' or 'max'.

Returns:

str

Return type:

The mode, ‘min or ‘max’.

param_names() → Iterable[str]

Names of the parameters for this algorithm.

Return type:

An iterable of str.

param_value(param: str) → Any

The value of a parameter.

Parameters:

param (str) – A parameter name

Return type:

The value of the parameter

Raises:

KeyError – if there is no parameter with this name.:

property params: Dict

A dictionary of parameters values.

The dictionary is a copy of the internal parameters and can be safely modified.

Return type:

A dictionary of parameters values.

class ComputationDef(node: ComputationNode, algo: AlgorithmDef)

Full definition of a Computation.

A Computation node contains all the information needed to create a computation instance that can be run. It can be used when deploying the computation or as a replica when distributing copies of a computation for resilience.

Parameters:
check_param_value(param_val: Any, param_def: AlgoParameterDef) → Any

Check if param_val is a valid value for a AlgoParameterDef

When a parameter is given as a str, and the definition expect an int or a float, a conversion is automatically attempted and the converted value is returned

Parameters:

  • param_val (any) – a value

  • param_def (AlgoParameterDef) – a parameter definition

Returns:

the parameter value if it is valid according to the definition (and potentially after conversion)

Return type:

param_value

Raises:

ValueError: – Raises a ValueError if the value does not satisfies the parameter definition.

Examples

>>> param_def = AlgoParameterDef('p', 'str', ['a', 'b'], 'b')
>>> check_param_value('b', param_def)
'b'

With automatic conversion from str to int >>> param_def = AlgoParameterDef(‘p’, ‘int’, None, None) >>> check_param_value(‘5’, param_def) 5

find_computation_implementation(algorithm_module)

Find VariableComputation subclasses in an algorithm module

Parameters:

algorithm_module –

Return type:

A list of VariableComputation subclasses.

is_of_type_by_str(value: Any, type_str: str)

Check if the type of value is type_str.

Parameters:

  • value (any) – a value

  • type_str (str) – the expected type of value, given as a str

Examples

>>> is_of_type_by_str(2, 'int')
True
>>> is_of_type_by_str("2.5", 'float')
False
Return type:

boolean

list_available_algorithms() → List[str]

The list of available DCOP algorithms.

Return type:

a list of str

load_algorithm_module(algo_name: str)

Dynamically load an algorithm module.

This should be used instead of importlib.import_module as it adds default implementations for some methods, if they have not been defined for the algorithm.

Parameters:

algo_name (str) – the name of the algorithm. It must be one of the name returned by list_available_algorithms().

Returns:

The imported module for this algorithm.

Return type:

module

prepare_algo_params(params: Dict[str, Any], parameters_definitions: List[AlgoParameterDef])

Ensure algorithm’s parameters are valid.

Check validity of algorithm parameters and add default value for missing parameters.

Parameters:

  • params (Dict[str, Any]) – a dict containing name and values for parameters

  • parameters_definitions (list of AlgoParameterDef) – definition of parameters

Examples

>>> param_defs = [AlgoParameterDef('p1', 'str', ['1', '2'], '1'),                       AlgoParameterDef('p2', 'int', None, 5),                      AlgoParameterDef('p3', 'float', None, 0.5)]
>>> prepare_algo_params({}, param_defs)['p3']
0.5
>>> prepare_algo_params({'p2' : 2}, param_defs)['p2']
2
>>> prepare_algo_params({'p3' : 0.7}, param_defs)['p3']
0.7
Returns:

params – a Dict with all algorithms parameters. If a parameter was not provided in the input dict, it is added with its default value.

Return type:

dict

Raises:

ValueError: – If an unknown parameter is passed or if a parameter value does not respect the parameter definition.