`traversal` – Graph Traversal Utilities#

pytensor.graph.traversal.ancestors(graphs, blockers=None)[source]#

Return the variables that contribute to those in given graphs (inclusive), stopping at blockers.

Parameters:

graphs (list of Variable instances) – Output Variable instances from which to search backward through owners.
blockers (list of Variable instances) – A collection of Variables that, when found, prevent the graph search from preceding from that point.

Yields:

Variables – All ancestor variables, in the order found by a right-recursive depth-first search started at the variables in graphs.

pytensor.graph.traversal.apply_ancestors(graphs, blockers=None)[source]#: Return the Apply nodes that contribute to those in given graphs, excluding the owners of the blockers.

pytensor.graph.traversal.apply_depends_on(apply, depends_on)[source]#

Determine if any depends_on is in the graph given by apply.

Parameters:

apply (Apply) – The Apply node to check.
depends_on (Union[Apply, Collection[Apply]]) – Apply nodes to check dependency on

Return type:

bool

pytensor.graph.traversal.applys_between(ins, outs)[source]#

Extract the Applys contained within the sub-graph between given input and output variables.

Notes

This is identical to apply_ancestors(outs, blockers=ins)

Parameters:

ins (list) – Input Variables.
outs (list) – Output Variables.

Yields:

The Applys that are contained within the sub-graph that lies
between ins and outs, including the owners of the Variables in
outs and intermediary Applys between ins and outs, but not the
owners of the Variables in ins.

pytensor.graph.traversal.explicit_graph_inputs(graph)[source]#

Get the root variables needed as inputs to a function that computes graph

Parameters:: graph (TensorVariable) – Output Variable instances for which to search backward through owners.
Returns:: Generator of root Variables (without owner) needed to compile a function that evaluates graphs.
Return type:: iterable

Examples

import pytensor
import pytensor.tensor as pt
from pytensor.graph.traversal import explicit_graph_inputs

x = pt.vector("x")
y = pt.constant(2)
z = pt.mul(x * y)

inputs = list(explicit_graph_inputs(z))
f = pytensor.function(inputs, z)
eval = f([1, 2, 3])

print(eval)
# [2. 4. 6.]

pytensor.graph.traversal.general_toposort(outputs, deps, compute_deps_cache=None, deps_cache=None, clients=None)[source]#

Perform a topological sort of all nodes starting from a given node.

Parameters:

deps (callable) – A Python function that takes a node as input and returns its dependence.
compute_deps_cache (optional) – If provided, deps_cache should also be provided. This is a function like deps, but that also caches its results in a dict passed as deps_cache.

Notes

This is a simple wrapper around walk_toposort for backwards compatibility

deps(i) should behave like a pure function (no funny business with internal state).

The order of the return value list is determined by the order of nodes returned by the deps function.

pytensor.graph.traversal.get_var_by_name(graphs, target_var_id)[source]#

Get variables in a graph using their names.

Parameters:

graphs – The graph, or graphs, to search.
target_var_id – The name to match against either Variable.name or Variable.auto_name.

Return type:

A tuple containing all the Variables that match target_var_id.

pytensor.graph.traversal.graph_inputs(graphs, blockers=None)[source]#

Return the inputs required to compute the given Variables.

Parameters:

graphs (list of Variable instances) – Output Variable instances from which to search backward through owners.
blockers (list of Variable instances) – A collection of Variables that, when found, prevent the graph search from preceding from that point.

Yields:

Input nodes with no owner, in the order found by a breath first search started at the nodes in graphs.

pytensor.graph.traversal.io_toposort(inputs, outputs, orderings=None, clients=None)[source]#

Perform topological of nodes between input and output variables.

Notes

This is just a wrapper around toposort_with_extra_orderings for backwards compatibility

Parameters:

inputs (list or tuple of Variable instances) – Graph inputs.
outputs (list or tuple of Apply instances) – Graph outputs.
orderings (dict) – Keys are Apply instances, values are lists of Apply instances.

pytensor.graph.traversal.orphans_between(ins, outs)[source]#

Extract the root Variables not within the sub-graph between input and output nodes.

Parameters:

ins (list) – Input Variables.
outs (list) – Output Variables.

Yields:

Variable – The Variables upon which one or more Variables in outs depend, but are neither in ins nor in the sub-graph that lies between them.

Examples

>>> from pytensor.graph.traversal import orphans_between
>>> from pytensor.tensor import scalars
>>> x, y = scalars("xy")
>>> list(orphans_between([x], [(x + y)]))
[y]

pytensor.graph.traversal.toposort(graphs, blockers=None)[source]#

Topologically sort of Apply nodes between graphs (outputs) and blockers (inputs).

This is a streamlined version of io_toposort_generator when no additional ordering constraints are needed.

pytensor.graph.traversal.toposort_with_orderings(graphs, *, blockers=None, orderings=None)[source]#

Perform topological of nodes between blocker (input) and graphs (output) variables with arbitrary extra orderings

Extra orderings can be used to force sorting of variables that are not naturally related in the graph. This can be used by inplace optimizations to ensure a variable is only destroyed after all other uses. Those other uses show up as dependencies of the destroying node, in the orderings dictionary.

Parameters:

graphs (list or tuple of Variable instances) – Graph outputs.
blockers (list or tuple of Variable instances) – Graph inputs.
orderings (dict) – Keys are Apply or Variable instances, values are lists of Apply or Variable instances.

pytensor.graph.traversal.truncated_graph_inputs(outputs, ancestors_to_include=None)[source]#

Get the truncate graph inputs.

Unlike graph_inputs() this function will return the closest variables to outputs that do not depend on ancestors_to_include. So given all the returned variables provided there is no missing variable to compute the output and all variables are independent from each other.

Parameters:

outputs (Iterable[Variable]) – Variable to get conditions for
ancestors_to_include (Optional[Iterable[Variable]]) – Additional ancestors to assume, by default None

Returns:

Variables required to compute outputs

Return type:

List[Variable]

Examples

The returned variables marked in (parenthesis), ancestors variables are c, output variables are o

No ancestors to include

n - n - (o)

One ancestors to include

n - (c) - o

Two ancestors to include where on depends on another, both returned

(c) - (c) - o

Additional variables are present

   (c) - n - o
n - (n) -'

Disconnected ancestors to include not returned

(c) - n - o
 c

Disconnected output is present and returned

(c) - (c) - o
(o)

ancestors to include that include itself adds itself

n - (c) - (o/c)

pytensor.graph.traversal.variable_ancestors(graphs, blockers=None)[source]#

Return the variables that contribute to those in given graphs (inclusive), stopping at blockers.

Parameters:

graphs (list of Variable instances) – Output Variable instances from which to search backward through owners.
blockers (list of Variable instances) – A collection of Variables that, when found, prevent the graph search from preceding from that point.

Yields:

Variables – All ancestor variables, in the order found by a right-recursive depth-first search started at the variables in graphs.

pytensor.graph.traversal.variable_depends_on(variable, depends_on)[source]#

Determine if any depends_on is in the graph given by variable.

Notes

The interpretation of dependency is done at a variable level. A variable may depend on some output variables from a multi-output apply node but not others.

Parameters:

variable (Variable) – T to check
depends_on (Iterable[Variable]) – Nodes to check dependency on

Return type:

bool

pytensor.graph.traversal.vars_between(ins, outs)[source]#

Extract the Variables within the sub-graph between input and output nodes.

Notes

This function is like ancestors(outs, blockers=ins), except it can also yield disconnected output variables from multi-output apply nodes.

Parameters:

ins – Input Variables.
outs – Output Variables.

Yields:

The Variables that are involved in the subgraph that lies
between ins and outs. This includes ins, outs,
orphans_between(ins, outs) and all values of all intermediary steps from
ins to outs.

pytensor.graph.traversal.walk(nodes, expand, bfs=True, return_children=False)[source]#

Walk through a graph, either breadth- or depth-first.

Parameters:

nodes – The nodes from which to start walking.
expand – A callable that is applied to each node in nodes, the results of which are either new nodes to visit or None.
bfs – If True, breath first search is used; otherwise, depth first search.
return_children – If True, each output node will be accompanied by the output of expand (i.e. the corresponding child nodes).

Notes

A node will appear at most once in the return value, even if it appears multiple times in the nodes parameter.

pytensor.graph.traversal.walk_toposort(graphs, deps)[source]#

Perform a topological sort of all nodes starting from a given node.

Parameters:

graphs – An iterable of nodes from which to start the topological sort.
deps (callable) – A Python function that takes a node as input and returns its dependence.

Notes

deps(i) should behave like a pure function (no funny business with internal state).

The implementation uses identity (is), so items returned by deps must be the same objects as those yielded by graphs.

The order of the return value list is determined by the order of nodes returned by the deps function.

traversal – Graph Traversal Utilities#

`traversal` – Graph Traversal Utilities#