Add regular tree generator

[stecrotti]

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.

[codecov[bot]]

Codecov Report

Merging #197 (b26cf91) into master (ea6bcfe) will decrease coverage by 0.13%. The diff coverage is 92.85%.

@@            Coverage Diff             @@
##           master     #197      +/-   ##
==========================================
- Coverage   97.40%   97.26%   -0.14%     
==========================================
  Files         109      109              
  Lines        6468     6506      +38     
==========================================
+ Hits         6300     6328      +28     
- Misses        168      178      +10     

[stecrotti]

By the way I called it 'regular tree' because of the analogy with regular graphs but that might not be too accurate because:

1. A regular tree is not a regular graph (because of the leaves)
2. z-regular graphs have nodes of degree z while z-ary trees have nodes of degree z+1, potentially confusing

That said, mary_tree(k, m), zary_tree(k, z) don't look great to me.

[stecrotti]

Changes:

• New method with type regular_tree(T::Type{<:Integer}, k::Integer, z::Integer)
• Improved docs with correct wiki page
• InexactError instead of DomainError when number of vertices is not representable
• Assert z > 0, fallback to a path graph in case z = 1
• Appropriate conversions to the provided type T, checked by test

[simonschoelly]

By the way I called it 'regular tree' because of the analogy with regular graphs but that might not be too accurate because:

1. A regular tree is not a regular graph (because of the leaves)

2. z-regular graphs have nodes of degree z while z-ary trees have nodes of degree z+1, potentially confusing

That said, mary_tree(k, m), zary_tree(k, z) don't look great to me.

I think regular tree is perfectly fine. For example here, the same term is used: https://www.wolframalpha.com/examples/mathematics/discrete-mathematics/graph-theory/regular-trees/

[dapias]

I just realized that a $k$-ary tree is not the same as a Cayley tree of connectivity $k$ because in a $k$-ary tree, the root has connectivity $k$, and all the nodes excepting those in the leaves have connectivity $k+1$. Look, for instance, at the attached plot, nodes 2,3 and 4 have connectivity four and not three as it would be the case for a Cayley tree

[stecrotti]

Agree! Indeed it was corrected and should be ok in the current version of this PR

[dapias]

Is there a function to create an actual Cayley tree?

[stecrotti]

Not that i know of

[dapias]

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 $(z-1)$ children instead of $z$

[stecrotti]

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.

[simonschoelly]

There is this one comment from me, about k >= 0 - not sure if you have seen it, but feel free to ignore that it you think we should not change anything there.

Otherwise looks good for me - I did not check the math, but choose to believe the tests.

[stecrotti]

Sure, i replied under your review comment:

I stuck to what was used in the rest of the file which is that for k<=0 it returns a SimpleGraph(zero(T)). I guess there was a good reason for that? If not it makes total sense to error if k<0.