#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 | 0293adf41a1ae5c2cb8e38e8675a4b010162e00a
Authors: | Stopgaps:
Frédéric Chapoton |
Report Upstream: N/A |
Branch: |
public/19520 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
Hellooooo,
> No, no, in the example `1,0,0,0,0,0`, the inner-root does have two
leaves.
Argggggg, sorry. I wrote this comment then spent more time understanding
what was actually going on. This comment was indeed incorrect, but I hope
that you will find nothing wrong in my modifications of doc/code.
> In the algorithms, it turns out to be more convenient to use the inner-
root as "true" root, and to transform the leaf-root to become the
rightmost leaf of the inner-root. In this case, the inner root also has
two leaves.
Yepyep. I agree that the code seems consistent with this definition: all
internal vertices have two leaves.
At first, I expected that discovering a leaf resulted in two consecutive
'0' in the word, as going there (one 0) and going back (one 0) would take
two moves. Turns out that 'discovering a leaf' takes only one 0.
This is the reason why I added in the documentation a comment about the
expected length of a sequence with respect to its associated tree.
> This algorithm is my own implementation
> of the bijective map described in section 2.1. I am not sure that it is
really efficient. I perform the closure moves by successive reductions of
the contour word,
> until there is no sequence (in,in,in,lf) in the cyclic contour word.
I see. Could you add in the doc some pointers toward the corresponding
sections of the paper (e.g. section 2.1) so that it is easier to know
while reading the code which part of the paper you were 'translating'?
Thanks,
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/19520#comment:19>
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.
