# DirectedAcyclicGraphs

`DirectedAcyclicGraphs.DAG`

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

`DirectedAcyclicGraphs.Inner`

— TypeThe trait of inner nodes (nodes that have children)

`DirectedAcyclicGraphs.Leaf`

— TypeThe trait of leaf nodes (nodes without children)

`DirectedAcyclicGraphs.NodeType`

— TypeA 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}

`DirectedAcyclicGraphs.NodeType`

— MethodGet the node type trait of the given `Node`

`DirectedAcyclicGraphs.Tree`

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

`Base.filter`

— MethodRetrieve list of nodes in DAG matching predicate `p`

`Base.foreach`

— FunctionApply a function to each node in a graph, bottom up

`Base.in`

— FunctionIs the node contained in the `DAG`

?

`Base.parent`

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

`DirectedAcyclicGraphs.children`

— FunctionGet the children of a given inner node

`DirectedAcyclicGraphs.depth`

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

`DirectedAcyclicGraphs.feedforward_layers`

— Method`feedforward_layers(root::DAG)`

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

`DirectedAcyclicGraphs.find_inode`

— MethodFind 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.

`DirectedAcyclicGraphs.find_leaf`

— MethodFind the leaf in the tree by follwing the branching function

`DirectedAcyclicGraphs.foldup`

— Method```
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.

`DirectedAcyclicGraphs.foldup_aggregate`

— MethodCompute 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.

`DirectedAcyclicGraphs.foreach_down`

— MethodApply a function to each node in a graph, top down

`DirectedAcyclicGraphs.groupby`

— MethodGroup the elements of `list`

by their values according to function `f`

`DirectedAcyclicGraphs.has_children`

— MethodDoes the DAG node have children?

`DirectedAcyclicGraphs.has_parent`

— MethodDoes the node have a parent?

`DirectedAcyclicGraphs.innernode_stats`

— Method`innernode_stats(c::DAG)`

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

`DirectedAcyclicGraphs.innernodes`

— MethodGet the list of inner nodes in a given graph

`DirectedAcyclicGraphs.isequal_local`

— MethodIs one node equal to another locally, ignoring children?

`DirectedAcyclicGraphs.isinner`

— MethodIs the DAG node an inner node?

`DirectedAcyclicGraphs.isleaf`

— MethodIs the DAG node a leaf node?

`DirectedAcyclicGraphs.isroot`

— MethodIs the node the root of its tree?

`DirectedAcyclicGraphs.label_nodes`

— MethodAssign an integer label to each circuit node, bottom up, starting at `1`

`DirectedAcyclicGraphs.lca`

— MethodFind 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.

`DirectedAcyclicGraphs.leaf_stats`

— Method`leaf_stats(c::DAG)`

Give count of types of leaf nodes in the graph

`DirectedAcyclicGraphs.leafnodes`

— MethodGet the list of leaf nodes in a given graph

`DirectedAcyclicGraphs.left_most_descendent`

— Method`left_most_descendent(root::DAG)::DAG`

Return the left-most descendent.

`DirectedAcyclicGraphs.linearize`

— MethodOrder the `DAG`

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

`DirectedAcyclicGraphs.map_values`

— MethodMap the values in the dictionary, retaining the same keys

`DirectedAcyclicGraphs.node_stats`

— Method`node_stats(c::DAG)`

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

`DirectedAcyclicGraphs.num_children`

— MethodGet the number of children of a given inner DAG node

`DirectedAcyclicGraphs.num_edges`

— FunctionNumber of edges in the `DAG`

`DirectedAcyclicGraphs.num_innernodes`

— MethodCount the number of inner nodes in a given graph

`DirectedAcyclicGraphs.num_leafnodes`

— MethodCount the number of leaf nodes in a given graph

`DirectedAcyclicGraphs.num_nodes`

— Function`num_nodes(node::DAG)`

Count the number of nodes in the `DAG`

`DirectedAcyclicGraphs.num_parents`

— Method`num_parents(root::DAG)`

Count the number of parents for each node in `DAG`

under `root`

`DirectedAcyclicGraphs.parent_stats`

— Method`parent_stats(c::DAG)`

Give number of nodes grouped by (type, parent_count)

`DirectedAcyclicGraphs.print_tree`

— FunctionPrint the given tree

`DirectedAcyclicGraphs.right_most_descendent`

— Method`right_most_descendent(root::DAG)::DAG`

Return the right-most descendent.

`DirectedAcyclicGraphs.root`

— MethodGet the root of the given tree node

`DirectedAcyclicGraphs.tree_num_edges`

— Function`tree_num_edges(node::DAG)::BigInt`

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

.

`DirectedAcyclicGraphs.tree_num_nodes`

— Function`tree_num_nodes(node::DAG)::BigInt`

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

.