DirectedAcyclicGraphs

A node in a directed acyclic graph (of which it is the root)

The trait of inner nodes (nodes that have children)

The trait of leaf nodes (nodes without children)

A trait hierarchy denoting types of DAG nodes NodeType defines an orthogonal type hierarchy of node types, so we can dispatch on node type regardless of the graph type. See @ref{https://docs.julialang.org/en/v1/manual/methods/#Trait-based-dispatch-1}

Get the node type trait of the given Node

A node in a tree (of which it is the root)

Retrieve list of nodes in DAG matching predicate p

Apply a function to each node in a graph, bottom up

Is the node contained in the DAG?

Get the parent of a given tree node (or nothing if the node is root)

Get the children of a given inner node

Compute the length of the path from a tree node to the leaf following the branching function

feedforward_layers(root::DAG)

Assign a layer id with each node, starting from leafs to root

Find a binary inner node that has left in its left subtree and right in its right subtree. Supports nothing as a catch-all for either left or right. Returns nothing if no such node exists.

Find the leaf in the tree by follwing the branching function

foldup(node::DAG, 
    f_leaf::Function, 
    f_inner::Function, 
    ::Type{T})::T where {T}

Compute a function bottom-up on the graph. f_leaf is called on leaf nodes, and f_inner is called on inner nodes. Values of type T are passed up the circuit and given to f_inner as a function on the children.

Compute a function bottom-up on the circuit. f_leaf is called on leaf nodes, and f_inner is called on inner nodes. Values of type T are passed up the circuit and given to f_inner in aggregate as a vector from the children.

Apply a function to each node in a graph, top down

Group the elements of list by their values according to function f

Does the DAG node have children?

Does the node have a parent?

innernode_stats(c::DAG)

Give count of types and fan-ins of inner nodes in the graph

Get the list of inner nodes in a given graph

Is one node equal to another locally, ignoring children?

Is the DAG node an inner node?

Is the DAG node a leaf node?

Is the node the root of its tree?

Assign an integer label to each circuit node, bottom up, starting at 1

Find the least common ancestor. Assumes the Tree has access to a parent. A given descends_from function is required to quickly check whether a node is an ancestor.

leaf_stats(c::DAG)

Give count of types of leaf nodes in the graph

Get the list of leaf nodes in a given graph

left_most_descendent(root::DAG)::DAG

Return the left-most descendent.

Order the DAG's nodes bottom-up in a list (with optional element type)

Map the values in the dictionary, retaining the same keys

node_stats(c::DAG)

Give count of types and fan-ins of all nodes in the graph

Get the number of children of a given inner DAG node

Number of edges in the DAG

Count the number of inner nodes in a given graph

Count the number of leaf nodes in a given graph

num_nodes(node::DAG)

Count the number of nodes in the DAG

num_parents(root::DAG)

Count the number of parents for each node in DAG under root

parent_stats(c::DAG)

Give number of nodes grouped by (type, parent_count)

Print the given tree

right_most_descendent(root::DAG)::DAG

Return the right-most descendent.

Get the root of the given tree node

tree_num_edges(node::DAG)::BigInt

Compute the number of edges in the tree-unfolding of the DAG.

tree_num_nodes(node::DAG)::BigInt

Compute the number of nodes in of a tree-unfolding of the DAG.