Operation

AppliedNodeReduction <: AppliedOperation

The applied version of the NodeReduction.

AppliedNodeSplit <: AppliedOperation

The applied version of the NodeSplit.

AppliedOperation

An abstract base class for already applied operations. An applied operation can be reversed iff it is the last applied operation on the DAG. Every applied operation stores a Diff from when it was initially applied to be able to revert the operation.

See also: revert_operation!.

NodeReduction <: Operation

The NodeReduction operation. Represents the reduction of two or more nodes with one another. Only one of the input nodes is kept, while all others are deleted and their parents are accumulated in the kept node's parents instead.

After the node reduction is applied, the graph has length(nr.input) - 1 fewer nodes.

Requirements for successful application

A vector of nodes can be reduced if:

• All nodes are in the graph.
• All nodes have the same task type.
• All nodes have the same set of children.

is_valid_node_reduction_input can be used to @assert these requirements.

See also: can_reduce

NodeSplit <: Operation

The NodeSplit operation. Represents the split of its input node into one node for each of its parents. It is the reverse operation to the NodeReduction.

Requirements for successful application

A node can be split if:

• It is in the graph.
• It has at least 2 parents.

is_valid_node_split_input can be used to @assert these requirements.

See also: can_split

Operation

An abstract base class for operations. An operation can be applied to a DAG, changing its nodes and edges.

Possible operations on a DAG can be retrieved using get_operations.

See also: push_operation!, pop_operation!

generate_operations(graph::DAG)

Generate all possible operations on the graph. Used initially when the graph is freshly assembled or parsed. Uses multithreading for speedup.

Safely inserts all the found operations into the graph and its nodes.

insert_operation!(nf::NodeReduction)

Insert the given node reduction into its input nodes' operation caches. This is thread-safe.

insert_operation!(nf::NodeSplit)

Insert the given node split into its input node's operation cache. This is thread-safe.

nr_insertion!(operations::PossibleOperations, nodeReductions::Vector{Vector{NodeReduction}})

Insert the node reductions into the graph and the nodes' caches. Employs multithreading for speedup.

ns_insertion!(operations::PossibleOperations, nodeSplits::Vector{Vector{NodeSplits}})

Insert the node splits into the graph and the nodes' caches. Employs multithreading for speedup.

apply_all!(graph::DAG)

Apply all unapplied operations in the DAG. Is automatically called in all functions that require the latest state of the DAG.

apply_operation!(graph::DAG, operation::NodeReduction)

Apply the given NodeReduction to the graph. Generic wrapper around node_reduction!.

Return an AppliedNodeReduction object generated from the graph's Diff.

apply_operation!(graph::DAG, operation::NodeSplit)

Apply the given NodeSplit to the graph. Generic wrapper around node_split!.

Return an AppliedNodeSplit object generated from the graph's Diff.

apply_operation!(graph::DAG, operation::Operation)

Fallback implementation of apply_operation! for unimplemented operation types, throwing an error.

node_reduction!(graph::DAG, nodes::Vector{Node})

Reduce the given nodes together into one node, return the applied difference to the graph.

For details see NodeReduction.

node_split!(graph::DAG, n1::Node)

Split the given node into one node per parent, return the applied difference to the graph.

For details see NodeSplit.

revert_diff!(graph::DAG, diff::Diff)

Revert the given diff on the graph. Used to revert the individual AppliedOperations with revert_operation!.

revert_operation!(graph::DAG, operation::AppliedOperation)

Fallback implementation of operation reversion for unimplemented operation types, throwing an error.

revert_operation!(graph::DAG, operation::AppliedNodeReduction)

Revert the applied node reduction on the graph. Return the original NodeReduction operation.

revert_operation!(graph::DAG, operation::AppliedNodeSplit)

Revert the applied node split on the graph. Return the original NodeSplit operation.

get_operations(graph::DAG)

Return the PossibleOperations of the graph at the current state.

clean_node!(graph::DAG, node::Node)

Sort this node's parent and child sets, then find reductions and splits involving it. Needs to be called after the node was changed in some way.

find_reductions!(graph::DAG, node::Node)

Find node reductions involving the given node. The function pushes the found NodeReduction (if any) everywhere it needs to be and returns nothing.

find_splits!(graph::DAG, node::Node)

Find the node split of the given node. The function pushes the found NodeSplit (if any) everywhere it needs to be and returns nothing.

==(op1::NodeReduction, op2::NodeReduction)

Equality comparison between two node reductions. Two node reductions are considered equal when they have the same inputs.

==(op1::NodeSplit, op2::NodeSplit)

Equality comparison between two node splits. Two node splits are considered equal if they have the same input node.

==(op1::Operation, op2::Operation)

Fallback implementation of operation equality. Return false. Actual comparisons are done by the overloads of same type operation comparisons.

delete!(operations::PossibleOperations, op::NodeReduction)

Delete the given node reduction from the possible operations.

delete!(operations::PossibleOperations, op::NodeSplit)

Delete the given node split from the possible operations.

isempty(operations::PossibleOperations)

Return whether operations is empty, i.e. all of its fields are empty.

length(operations::PossibleOperations)

Return a named tuple with the number of each of the operation types as a named tuple. The fields are named the same as the PossibleOperations'.

can_reduce(n1::Node, n2::Node)

Return whether the given two nodes can be reduced. See NodeReduction for the requirements.

can_split(n1::Node)

Return whether the given node can be split. See NodeSplit for the requirements.

show(io::IO, op::NodeReduction)

Print a string representation of the node reduction to io.

show(io::IO, op::NodeSplit)

Print a string representation of the node split to io.

show(io::IO, ops::PossibleOperations)

Print a string representation of the set of possible operations to io.

is_valid(graph::DAG, nr::NodeReduction)

Assert for a given NodeReduction whether it is a valid operation in the graph.

Intended for use with @assert or @test.

is_valid(graph::DAG, nr::NodeSplit)

Assert for a given NodeSplit whether it is a valid operation in the graph.

Intended for use with @assert or @test.

is_valid_node_reduction_input(graph::DAG, nodes::Vector{Node})

Assert for a gven node reduction input whether the nodes can be reduced. For the requirements of a node reduction see NodeReduction.

Intended for use with @assert or @test.

is_valid_node_split_input(graph::DAG, n1::Node)

Assert for a gven node split input whether the node can be split. For the requirements of a node split see NodeSplit.

Intended for use with @assert or @test.