#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: |
-------------------------+-------------------------------------------------
Changes (by chapoton):
* commit: fae0137dbe91dbb753cba98dd9c1504003ea03bc =>
0293adf41a1ae5c2cb8e38e8675a4b010162e00a
* branch: u/chapoton/19520 => public/19520
Comment:
Hello Nathann, thanks for your time and your work.
0) adding underscores to names, done
1) using 'in' and 'lf' instead, done
> - 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.
No, no, in the example `1,0,0,0,0,0`, the inner-root does have two leaves.
One must be careful about what is called the root. There is a leaf-root
and an inner-root. In the paper, the leaf-root is considered as the "true"
root. And so the inner root would have only one leaf.
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.
> - 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`
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.
> The modifications I mention can be found at public/19520.
Let us work together on the branch public/19520
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=859e822fd2f7bf137107913508ccf79465361bcf
859e822]||{{{Merge branch 'u/chapoton/19520' of
git://trac.sagemath.org/sage into 19520}}}||
||[http://git.sagemath.org/sage.git/commit/?id=5083bfb0eed6f1582e8b7ee2c1c135a3f4ccad8c
5083bfb]||{{{trac #19520: Merged with 6.10.beta3}}}||
||[http://git.sagemath.org/sage.git/commit/?id=3561232212dcf172233ba26e67e986d7f8043160
3561232]||{{{trac #19520: Review}}}||
||[http://git.sagemath.org/sage.git/commit/?id=64b0660f43d4b1a916db0aef120fc07d385ee144
64b0660]||{{{Merge branch 'public/19520' of git://trac.sagemath.org/sage
into 19520}}}||
||[http://git.sagemath.org/sage.git/commit/?id=0293adf41a1ae5c2cb8e38e8675a4b010162e00a
0293adf]||{{{trac #19520 reviewer's comments}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19520#comment:18>
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.
