Add regular tree generator#197
Conversation
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## master #197 +/- ##
==========================================
- Coverage 97.30% 97.28% -0.02%
==========================================
Files 123 123
Lines 7378 7406 +28
==========================================
+ Hits 7179 7205 +26
- Misses 199 201 +2 ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
| k <= 0 && return SimpleGraph(0) | ||
| k == 1 && return SimpleGraph(1) |
There was a problem hiding this comment.
In these cases we return a graph of of eltype Int, but in all other cases we return a graph of type T.
There was a problem hiding this comment.
To be completely honest, I am not sure if it is the best idea to determine the eltype of the graphs from k and z - we do that indeed for other graphs here, but I never really liked that.
There was a problem hiding this comment.
Maybe we can have a function signature
regular_tree(T::Type{<:Integer}, k::Integer, z::Integer)and then define something like
regular_tree(k::Integer, z::Integer) = regular_tree(Int64, k, z)that for be similar to the function sprand from SparseArrays for example.
| """ | ||
| regular_tree(k::Integer, z::integer) | ||
|
|
||
| Create a [regular tree](https://en.wikipedia.org/wiki/Bethe_lattice), |
There was a problem hiding this comment.
That wikipedia article might be a bit confusing, because it talks about infinite trees in the introduction.
Maybe we can decribe that a bit more clearly here?
If I understood correctly, what you want to create is a perfect k-ary tree such as described here? https://en.wikipedia.org/wiki/M-ary_tree#Types_of_m-ary_trees
|
By the way I called it 'regular tree' because of the analogy with regular graphs but that might not be too accurate because:
That said, |
|
Changes:
|
I think |
aurorarossi
left a comment
There was a problem hiding this comment.
Some comments on the docstrings. If you agree with the style then I will open a PR to fix double_binary_tree and binary_tree
| end | ||
|
|
||
| """ | ||
| regular_tree([T=Int64, ], k::Integer, z::integer) |
There was a problem hiding this comment.
Except for binary_tree and double_binary_tree all the other functions of this file have the following style:
| regular_tree([T=Int64, ], k::Integer, z::integer) | |
| regular_tree(T, k, z) |
| julia> regular_tree(4, 3) | ||
| {40, 39} undirected simple Int64 graph | ||
|
|
There was a problem hiding this comment.
I would remove it and I would put it in the docstring of the function regular_tree(k,z).
| julia> regular_tree(4, 3) | |
| {40, 39} undirected simple Int64 graph |
|
|
||
| julia> regular_tree(5, 2) == binary_tree(5) | ||
| true |
There was a problem hiding this comment.
Same as above.
| julia> regular_tree(5, 2) == binary_tree(5) | |
| true |
| end | ||
| return SimpleGraph(ne, fadjlist) | ||
| end | ||
|
|
There was a problem hiding this comment.
I would add the docstring also to this function.
| """ | |
| regular_tree(k, z) | |
| Create a regular tree or [perfect z-ary tree](https://en.wikipedia.org/wiki/M-ary_tree#Types_of_m-ary_trees): | |
| a `k`-level tree where all nodes except the leaves have exactly `z` children. | |
| For `z = 2` one recovers a binary tree. | |
| # Examples | |
| ```jldoctest | |
| julia> regular_tree(4, 3) | |
| {40, 39} undirected simple Int64 graph | |
| julia> regular_tree(5, 2) == binary_tree(5) | |
| true | |
| ``` | |
| """ |
There was a problem hiding this comment.
It's quite often the case, that the docstrings for multiple methods of a function are only added for a single method - I think that would also be better here, than adding docstrings for both methods of this function.
|
I just realized that a
|
|
Agree! Indeed it was corrected and should be ok in the current version of this PR |
|
Is there a function to create an actual Cayley tree? |
|
Not that i know of |
|
I am not an expert, but it seems trivial to be implemented, given the actual code for the tree. After setting up the central node (root), one only needs to demand that each child has |
| ``` | ||
| """ | ||
| function regular_tree(T::Type{<:Integer}, k::Integer, z::Integer) | ||
| z <= 0 && throw(DomainError(z, "number of children must be positive")) |
There was a problem hiding this comment.
Shouldn't we also check for k >= 0 here?
| if Graphs.isbounded(k) && (BigInt(z)^k - 1) ÷ (z - 1) > typemax(T) | ||
| throw(InexactError(:convert, T, (BigInt(z)^k - 1) ÷ (z - 1))) | ||
| end | ||
|
|
||
| n = T((z^k - 1) / (z - 1)) |
There was a problem hiding this comment.
You already calculate the number of vertices with (BigInt(z)^k - 1) ÷ (z - 1), so we we could just reuse this for n.
With the expression n = T((z^k - 1) / (z - 1)) there are two issues:
z^kmight overflow before converting it toT- By using the
/operator instead of÷your intermediate result will be a double
There was a problem hiding this comment.
A lot of these overflow issues probably won't happen if we restrict k and z to Int in the function definition.
|
Changed the signature to match the rest of the file as suggested by @aurorarossi, but kept only one docstring. Fixed potential overflow as suggested by @simonschoelly. |
|
There is this one comment from me, about Otherwise looks good for me - I did not check the math, but choose to believe the tests. |
|
Sure, i replied under your review comment:
|
|
@stecrotti , it seems this PR lost steam a few years ago. Could you run the formatter on it -- after that it should be good to go for merging. |
|
doctests are actually failing, so for now I will mark this as a draft to manage my review queue a bit more easily -- do not hesitate to convert it back to not draft if you decide to look into it |
|
I fixed the doctests. |
Benchmark Results (Julia v1)Time benchmarks
Memory benchmarks
|
|
Thank you, Stefano! Your quick turnaround is extremely highly appreciated! You might have noticed that we are struggling to have enough volunteers on the team. Let me know if you are interested in being added as a maintainer -- help with reviews can really help revive this ecosystem. |
Generator for a regular tree, also known as Bethe Lattice or Cayley Tree, which generalizes a binary tree to arbitrary degree.
I tried to keep the code as close as possible to the one for
binary_tree.