Graph-like expressions

[MilesCranmer]

This WIP PR will implement remaining methods for trees that allow two or more parents to share a node. This means we can re-use subexpressions in a single expression. @AlCap23 This should partially address some of #14.

Comments:

• Created a new GraphNode type which inherits from a new AbstractExpressionNode. It is assumed that expressions made with GraphNode are to be treated as having shared subexpressions (so requires storing a stack of node IDs when counting, etc.), but those made with Node are treated like trees (even if there are some shared subexpressions).
  • It is easy to convert back and forth. Just note that converting to Node will destroy any shared subexpressions.
• Had to add a keyword to tree_mapreduce in the form of a passed function f_on_shared which takes two arguments: the result of the function evaluation, and whether it has already been passed. So, for instance, count_nodes can define f_on_shared=(result, is_shared) -> is_shared ? 0 : result, meaning it will avoid double-counting nodes.
• I changed from IdDict to Dict{UInt} because surprisingly the latter is faster for doing the exact same task! I looked into why this is and apparently IdDict does not specialize its methods on the input value... So it's actually faster to just pass the objectid manually to a regular Dict. Very weird.

---

Here's a to-do list of functions remaining:

• [x] copy_node
• [x] convert
• [x] simplify_tree!
• [x] combine_operators (Conceptually not possible - I throw an error instead)
• [x] string_tree
  • I think the technique in the SymbolicRegression.jl branch is good - whenever there is a shared node, the second time you print it, surround it with { ... }. It is easy to pattern match with your eyes and figure out where it is shared from.
  • Alternatively, we could do something more complicated and have a multi-step scheme... Like for each shared node, we write out z1 = ...; y=sin(z1)*z1 or something.
• [x] print_tree
• [x] Default show
• [x] count_nodes
• [x] count_depth (will work as-is)
• [x] count_constants
• [x] index_constants
• [x] get_constants
• [x] set_constants!
• [x] set_node! (will work as-is)
• [x] filter
• [x] collect
• [x] map
• [x] filter_map
• [x] count
• [x] foreach
• [x] collect
• [x] sum
• [x] mapreduce
• [x] iterate (Not possible)
• [x] length
• [x] copy
• [x] hash
• [x] == (requires exact structure when comparing GraphNode. If want to compare without structure, just do Node(t1) == Node(t2).
• Within symbolic regression (need to add later)
  • compute_complexity
  • All the mutation functions
  • Optimization routine

Then these ones:

To-do for detailed testing:

• [x] copy_node
• [x] convert
• [x] simplify_tree!
• [x] print and show
• [x] count_nodes
• [x] count_depth
• [x] count_constants
• [x] index_constants
• [x] get_constants
• [x] set_constants!
• [x] set_node!
• [x] hash
• [x] ==
• [x] filter
• [x] collect
• [x] map
• [x] filter_map
• [x] count
• [x] foreach
• [x] collect
• [x] sum
• [x] mapreduce
• [x] iterate
• [x] length
• [x] copy
• [x] Test that the auto-conversion in the constructors works as expected

We also need to:

• [x] Fix slow down
• [x] Update docs

[coveralls]

Pull Request Test Coverage Report for Build 7247053604

• 320 of 344 (93.02%) changed or added relevant lines in 11 files are covered.
• 3 unchanged lines in 2 files lost coverage.
• Overall coverage increased (+1.8%) to 92.874%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
src/EvaluateEquationDerivative.jl	7	8	87.5%
src/Utils.jl	17	18	94.44%
src/base.jl	96	97	98.97%
src/EquationUtils.jl	30	33	90.91%
src/OperatorEnumConstruction.jl	29	32	90.63%
src/Equation.jl	97	112	86.61%
<!--	Total:	320	344	93.02%	-->

Files with Coverage Reduction	New Missed Lines	%
src/Utils.jl	1	92.11%
src/ExtensionInterface.jl	2	0.0%
<!--	Total:	3		-->

Totals
Change from base Build 5997104008:	1.8%
Covered Lines:	1212
Relevant Lines:	1305

---

💛 - Coveralls

[github-actions[bot]]

Benchmark Results

	master	f8f9678c149a26...	t[master]/t[f8f9678c149a26...]
eval/ComplexF32/evaluation	7.4 ± 0.49 ms	7.38 ± 0.46 ms	1
eval/ComplexF64/evaluation	9.54 ± 0.68 ms	9.53 ± 0.74 ms	1
eval/Float32/derivative	10.8 ± 1.3 ms	10.9 ± 1.3 ms	0.993
eval/Float32/derivative_turbo	12.1 ± 1.4 ms	12 ± 1.4 ms	1.01
eval/Float32/evaluation	2.64 ± 0.22 ms	2.66 ± 0.23 ms	0.993
eval/Float32/evaluation_turbo	0.623 ± 0.027 ms	0.621 ± 0.025 ms	1
eval/Float64/derivative	13.6 ± 0.52 ms	13.7 ± 0.54 ms	0.988
eval/Float64/derivative_turbo	14.4 ± 0.59 ms	14.4 ± 0.57 ms	0.996
eval/Float64/evaluation	2.84 ± 0.24 ms	2.83 ± 0.24 ms	1
eval/Float64/evaluation_turbo	1.11 ± 0.061 ms	1.12 ± 0.059 ms	0.998
utils/combine_operators/break_sharing	0.0397 ± 0.0026 ms	0.0406 ± 0.0025 ms	0.979
utils/convert/break_sharing	28.2 ± 0.56 μs	28.2 ± 0.54 μs	0.999
utils/convert/preserve_sharing	0.155 ± 0.002 ms	0.128 ± 0.0026 ms	1.21
utils/copy/break_sharing	29 ± 0.55 μs	28.9 ± 0.59 μs	1.01
utils/copy/preserve_sharing	0.155 ± 0.0021 ms	0.129 ± 0.0026 ms	1.2
utils/count_constants/break_sharing	12.1 ± 0.23 μs	10.5 ± 0.17 μs	1.16
utils/count_depth/break_sharing	13.2 ± 0.25 μs	12.6 ± 0.23 μs	1.05
utils/count_nodes/break_sharing	11.7 ± 0.18 μs	10 ± 0.17 μs	1.17
utils/get_set_constants!/break_sharing	0.0683 ± 0.0011 ms	0.0535 ± 0.00075 ms	1.28
utils/has_constants/break_sharing	5.16 ± 0.26 μs	4.66 ± 0.22 μs	1.11
utils/has_operators/break_sharing	1.62 ± 0.016 μs	1.59 ± 0.017 μs	1.02
utils/index_constants/break_sharing	0.0525 ± 0.0021 ms	27.4 ± 0.68 μs	1.92
utils/is_constant/break_sharing	4.97 ± 0.26 μs	4.71 ± 0.23 μs	1.05
utils/simplify_tree/break_sharing	0.133 ± 0.013 ms	0.254 ± 0.02 ms	0.522
utils/string_tree/break_sharing	0.237 ± 0.0038 ms	0.563 ± 0.012 ms	0.421
utils/count_nodes/preserve_sharing		0.114 ± 0.0023 ms
utils/simplify_tree/preserve_sharing		0.376 ± 0.021 ms
utils/get_set_constants!/preserve_sharing		0.318 ± 0.0053 ms
utils/index_constants/preserve_sharing		0.129 ± 0.0023 ms
utils/string_tree/preserve_sharing		0.691 ± 0.013 ms
utils/count_constants/preserve_sharing		0.112 ± 0.0023 ms
time_to_load	0.671 ± 0.0094 s	0.682 ± 0.0014 s	0.984

[MilesCranmer]

Need to temporarily have RecursiveArrayTools.jl as an extension to force its version and get around this issue: https://github.com/SciML/RecursiveArrayTools.jl/issues/299.