dag Module

dag Module#

Basic code for operating on directed acyclic graphs (DAGs). None of these functions import or use any other parts of Pangolin. End-users of Pangolin are not expected to use these functions directly.

class pangolin.dag.Node(*parents)[source]#

The basic Node class. This is just an object that remembers a set of parents.

Parameters:

parents (Self) – parents of this node

property parents: tuple[Self, ...]#

The parents of this node

pangolin.dag.upstream_nodes_flat(nodes_flat, node_block, edge_block, upstream)[source]#

Do a DFS starting at all the nodes in nodes_flat. But never visit nodes if node_block(n) and never follow an edge from n to p if link_block(n,p).

Parameters:

  • nodes_flat (Sequence) – starting nodes

  • node_block (Callable[[N], bool] | None) – should DFS be blocked from visting a node?

  • edge_block (Callable[[N, N], bool] | None) – should DFS be blocked from following a link?

  • upstream (list[N]) – list of nodes, destructively updated

pangolin.dag.upstream_nodes(nodes, node_block=None, edge_block=None)[source]#

Do a DFS of all ancestors starting at all the nodes in nodes.

Parameters:

  • nodes (PyTree[N]) – Single node or list/pytree of node

  • node_block (Callable[[N], bool] | None) – Function defining which nodes to block from inclusion. If node_block(node) is True, then node is not visited. (Defalt: Don’t block.)

  • edge_block (Callable[[N, N], bool] | None) – Function defining which edges should not be followed. If edge_block(node, parent) is true, then don’t follow edge from node to parent. (Defalt: Don’t block)

Returns:

List of upstream nodes in topological order

Return type:

list[N]

pangolin.dag.upstream_with_descendent_old(requested_nodes, given_nodes)[source]#

First, find all nodes that are upstream (inclusive) of requested_nodes Then, find all the nodes that are downstream (inclusive) of that set that have a descendant in given_nodes

Parameters:

  • requested_nodes (list[N]) – nodes to search above

  • given_nodes (list[N]) – must have a descendant in this set

Return type:

list[N]

pangolin.dag.upstream_with_descendent(requested_nodes, given_nodes)[source]#

First, find all nodes that are upstream (inclusive) of requested_nodes Then, find all the nodes that are downstream (inclusive) of that set that have a descendant in given_nodes

Parameters:

  • requested_nodes (list[N])

  • given_nodes (list[N])

Return type:

list[N]

pangolin.dag.get_children(nodes, node_block=None)[source]#

Get all children for all upstream nodes

Parameters:

  • nodes (PyTree[N]) – Starting nodes (as in get_upstream)

  • node_block (Callable[[N], bool] | None) – Block condition (as in get_upstream)

Returns:

Dictionary mapping each upstream node to a list of children of that node

Return type:

dict[N, list[N]]

pangolin.dag.is_in(node, nodes)[source]#
Parameters:

  • node (N)

  • nodes (Sequence)

Return type:

bool

pangolin.dag.has_second_path(node, par_i)[source]#
Parameters:

  • node (Node)

  • par_i (int)

Return type:

bool

pangolin.dag.get_graph(nodes, get_content, block_condition=None)[source]#
Parameters:

nodes (PyTree[N])

Return type:

dict[N, Any]