#19520: implement random triangulations in a bijective way
-------------------------+-------------------------------------------------
Reporter: | Owner:
chapoton | Status: needs_info
Type: | Milestone: sage-6.10
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers: Nathann Cohen
theory | Work issues:
Keywords: | Commit:
random graph | fae0137dbe91dbb753cba98dd9c1504003ea03bc
Authors: | Stopgaps:
Frédéric Chapoton |
Report Upstream: N/A |
Branch: |
u/chapoton/19520 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
* reviewer: => Nathann Cohen
Comment:
Hello Frédéric,
Here is another (incomplete) review:
- The names of the two functions `contour_and_graph_from_word` and
`auxiliary_random_word` are not very descriptive of what they do, and
this is
not really a problem since they are not meant to be called directly by
the
user. As they do not appear in the documentation anyway, could you turn
them
into private functions by adding a `_` at the beginning of their name?
If you do so, please update the sphinx links.
- As a french person I understand why 'f' would denote a leaf, but that
probably
isn't the appropriate letter. Is there actually anything stopping you
from
using 'inner' and 'leaf' instead of 'i' and 'f'?
- As my notion of up/down is apparently the opposite of what the paper
use, I
rearranged the sentences of the doc of `contour_and_graph_from_word` so
that
'away/toward the root' appears before the notion of up/down (which
matches the
paper, as in your original text).
- What do you call 'every inner vertex has two leaves' ? In the sequence
`[1,0,0,0,0,0]` that you use as an example in the docstring of
`contour_and_graph_from_word`, the root vertex (that you consider to be
an
'inner' vertex) has exactly one neighbor, which is not a leaf.
- In `contour_and_graph_from_word` the variable `active_vertex` was always
equal
to `inner_stack[-1]`. I removed it. Less variables to keep track of -->
easier
to understand.
- This is a search operation in a list
{{{
inner_stack[-1] in leaf_stack:
}}}
This is not very efficient. Same for `leaf_stack.remove(x)`, which first
looks
for an occurrence of `x` in `leaf_stack`, then removes it.
Fortunately none of these operations is necessary, for if there is a
leaf to
add to the current inner vertex it is the last element of `leaf_stack`
(which
also means that all 'search' operations actually read the list
completely).
- Where exactly is the algorithm of `RandomTriangulation` to be found in
[PS2006]_? In the documentation you say that it comes from this paper,
but... where? `O_o`
The modifications I mention can be found at public/19520.
Thanks,
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/19520#comment:17>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
