leaspy.variables.dag

This module defines the VariablesDAG class used to represent the relationships between the variables of a model.

Classes

VariablesDAG

Directed acyclic graph of symbolic variables used in a leaspy model with efficient topologically sorted bidirectional access.

Module Contents

class VariablesDAG

Bases: collections.abc.Mapping

Directed acyclic graph of symbolic variables used in a leaspy model with efficient topologically sorted bidirectional access.

Parameters:

variablesMapping [ VariableName, VariableInterface]: The specifications of DAG nodes.
direct_ancestorsVariablesToFrozenSet: The nodes that are directly connected (in-going edge) to a given node. Use from_dict() class method to reach the natural dependencies of linked variables.

Notes

In general the VariablesDAG is not a tree because the graph may not be totally connected and may have multiple roots. It is not a multi-tree either since there may be multiple directed paths between two nodes - e.g. logistic_model = f[g, b(g), …]. However, we do assume that there is no cycle in the graph (not checked currently), which is equivalent to be topologically sortable.

In order to improve the efficiency of the algorithms, a node-wise sorted children and ancestors mappings are computed. These mappings are useful to:

perform computations and caching of intermediate variable dependencies
quickly reset all dependent nodes upon a modification

Finally, we do not store children nor ancestors in a specific node class to avoid cross-references in such nodes.

References

https://en.wikipedia.org/wiki/Directed_acyclic_graph#Computational_problems

Examples

>>> from leaspy.variables import VariablesDAG
>>> from leaspy.variables.specs import IndepVariable, LinkedVariable
>>> d_vars = {
    "x": IndepVariable(),
    "y": LinkedVariable(lambda *, x: -x),
}
>>> dag = VariablesDAG.from_dict(d_vars)

variables: Mapping[leaspy.variables.specs.VariableName, VariableInterface]: The specifications of DAG nodes.

direct_ancestors: leaspy.variables.specs.VariablesToFrozenSet: Mapping of variable names to their direct ancestors.

direct_children: leaspy.variables.specs.VariablesToFrozenSet: Mapping of variable names to their direct children.

sorted_variables_names: tuple[leaspy.variables.specs.VariableName, Ellipsis]: A topological sorting of variables from roots to leaves. The iteration order corresponds to this sorting.

sorted_children: Mapping[leaspy.variables.specs.VariableName, tuple[leaspy.variables.specs.VariableName, Ellipsis]]: Mapping of all children of a given variable in a topological order.

sorted_ancestors: Mapping[leaspy.variables.specs.VariableName, tuple[leaspy.variables.specs.VariableName, Ellipsis]]: Mapping of all ancestor of a given variable in a topological order.

sorted_variables_by_type: Mapping[Type[VariableInterface], Mapping[leaspy.variables.specs.VariableName, VariableInterface]]: The sorted variables, but stratified per variable type, to easily access them.

classmethod from_dict(input_dictionary)

Instantiate a new DAG of variables from a dictionary of variables.

This method is using LinkedVariable dependencies as direct ancestors.

Parameters:

input_dictionaryMapping [VariableName , VariableInterface]: The dictionary to use to create the DAG.

Parameters:

input_dictionary (Mapping[leaspy.variables.specs.VariableName, VariableInterface])

static compute_topological_order_and_path_matrix(direct_children, direct_ancestors)

Produce a topological sorting of the DAG.

This relies on a modified Kahn’s algorithm to produce a topological sorting of DAG, and the corresponding path matrix as a by-product.

Parameters:

direct_childrenVariablesToFrozenSet
direct_ancestorsVariablesToFrozenSet: The edges out-going (children) and in-going (ancestors) from a given node (at most one edge per node and no self-loop).

Returns:

sorted_nodestuple [VariableName, …]: Nodes in a topological order.
path_matrixtorch.Tensor [bool]: Boolean triangle superior (strict) matrix indicating whether there is a (directed) path between nodes.

Parameters:

direct_children (leaspy.variables.specs.VariablesToFrozenSet)
direct_ancestors (leaspy.variables.specs.VariablesToFrozenSet)

Return type:

tuple[tuple[leaspy.variables.specs.VariableName, Ellipsis], Tensor]

Notes

The algorithm has linear complexity with the O(number of edges + number of nodes). Input nodes are sorted by name in order to have fully reproducible output of the initial order of nodes and edges. (Thus renaming nodes may change the output, due to non-uniqueness of topological order)

static compute_sorted_children_and_ancestors(sorted_nodes, path_matrix)

Produce node-wise topologically sorted children and ancestors from provided nodes.

Parameters:

sorted_nodestuple of VariableName: The sorted nodes.
path_matrixtorch.Tensor

Returns:

sorted_childrendict [VariableName, tuple [VariableName, …]]: The sorted children.
sorted_ancestorsdict [VariableName, tuple [VariableName, …]]: The sorted ancestors.

Parameters:

sorted_nodes (tuple[leaspy.variables.specs.VariableName, Ellipsis])
path_matrix (Tensor)

Return type:

tuple[dict[leaspy.variables.specs.VariableName, tuple[leaspy.variables.specs.VariableName, Ellipsis]], dict[leaspy.variables.specs.VariableName, tuple[leaspy.variables.specs.VariableName, Ellipsis]]]

property individual_variable_names: tuple[leaspy.variables.specs.VariableName, Ellipsis]

Returns a tuple of variable names corresponding to the individual variables.

Returns:

tuple of VariableName: The individual variable names.

Return type:

tuple[leaspy.variables.specs.VariableName, Ellipsis]