Implement ribbon graphs

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

This ticket is meant to implement a new class of objects: ribbon graphs. These are graphs together with a cyclic ordering of the half edges adjacent to each vertex. This data allows us to unambiguosly "thicken" the ribbon graph to an orientable surface with boundary.

This will be done by encoding the ribbon graphs in two permutations. As done for example in [Gir] (and many other places). This is also meant to include basic methods of the class to compute:

• Genus of the thicekning
• Number of boundary components
• Labeling of the boundary components (see also [Gir])
• A basis of the homology of the graph (and so of the thickening) -This base satisfies the condition that each element of the basis is an embedded circle in the graph and contains one (and only one) edge that is not in any other element of the basis.

This is implementation is useful in itself but is also meant to serve as a base for a later implementation of something called "tete-a-tete" graphs which is an original idea by the mathematician Norbert A'Campo [Nor] and has been developed in my thesis. These other graphs model periodic automorphisms of the thickening of the graph.

[Gir] Girondo, Ernesto; González-Diez, Gabino (2012), Introduction to compact Riemann surfaces and dessins d'enfants, London Mathematical Society Student Texts, 79, Cambridge: Cambridge University Press,

[Nor] Tete-a-tete graphs and geometric monodromy

CC: @tscrim @sagetrac-tmonteil

Component: geometry

Keywords: ribbon, surfaces, orientable, days79

Author: Pablo Portilla

Branch/Commit: 809412e

Reviewer: David Coudert, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/21587

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4ef44be to d2cf929

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

d2cf929

Merge remote-tracking branch 'trac/u/SimonKing/metaclass_framework' into t/21587/ribbon_graphs

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:36

Replying to @sagetrac-git:

Branch pushed to git repo; I updated commit sha1. New commits:

d2cf929

Merge remote-tracking branch 'trac/u/SimonKing/metaclass_framework' into t/21587/ribbon_graphs

Just merged to the new rc0.

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:37

I don't know if I have to do anything else in order for people to start reviewing or is it just that there are a lot of tickets to review and few people reviewing

[tscrim]

comment:38

Replying to @sagetrac-pportilla:

I don't know if I have to do anything else in order for people to start reviewing or is it just that there are a lot of tickets to review and few people reviewing

It's a waiting game a lot of times. I hope to get around to review this soon, but unfortunately, I have a few other things that are higher priority at the moment. It takes finding someone who has enough knowledge in the area and time (which sometimes is 0, but I will [eventually] review this).

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:39

Replying to @tscrim:

Replying to @sagetrac-pportilla:

I don't know if I have to do anything else in order for people to start reviewing or is it just that there are a lot of tickets to review and few people reviewing

It's a waiting game a lot of times. I hope to get around to review this soon, but unfortunately, I have a few other things that are higher priority at the moment. It takes finding someone who has enough knowledge in the area and time (which sometimes is 0, but I will [eventually] review this).

Thanks for the quick answer! I will try to review or at least test some other tickets myself.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

43fda6a

Merge remote-tracking branch 'origin/master' into t/21587/ribbon_graphs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d2cf929 to 43fda6a

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:41

A test has been run by a patchbot. Everything was fine except for the "startup_time". Is there something that I have to do to fix this? Or this issue just deppends on the architecture on which the test is being run and I shouldn't do anything?

Thank you,

pportilla

[tscrim]

comment:42

It probably comes from the fact that we probably want to lazily import this to avoid increasing the number of imports at the startup of Sage. Also, you seem to have accidentally included changes to the git ignore file.

[tscrim]

comment:43

Also I will be at a SageDays next week and plan to review this ticket during that time.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

f18be10

reverted changes on .gitignore

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 43fda6a to f18be10

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:45

Replying to @tscrim:

Also I will be at a SageDays next week and plan to review this ticket during that time.

First of all: thank you! When this is positively reviewed, I have more interesting work to upload on other tickets (related to ribbon graphs)!

I already reverted .gitignore to its original state, thanks for that.

Should I change all imports for lazy imports? Will that do it?

[tscrim]

comment:46

You only need to change the one in all.py:

from .ribbon_graph import RibbonGraph, make_ribbon

as that is the one that gets called on startup (which then subsequently calls the ones in ribbon_graph.py).

[dcoudert]

comment:47

I did not check all the code, but the following must be done:

• method _find should be simplified as follows, where an error is raised if the k is not in the list.

for i,lst in enumerate(l):
    if k in lst:
        return [i, lst.index(k)]
raise ValueError("element {} not found".format(k))

• method _clean should be simplied as return [copy(elt) for elt in l if len(elt)>0]

• Many other simplifications could be done. For instance:

  • darts_rho = [j for i in range(len(repr_rho)) for j in repr_rho[i]] is darts_rho = flatten(repr_rho)
  • darts_sigma = flatten(repr_sigma)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f18be10 to 4cd202e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

4cd202e

Suggested changes commited

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4cd202e to 72ef663

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

72ef663

Fixed similar lines and turned them more "pythonic"

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:50

I forgot to change the state to "need review" after commiting the suggested fixes.

[tscrim]

comment:51

I have made it through the code and overall it looks good. I reworked some things to fix some things I encountered while I was doing my review. I also went through the doc and brought it up to Sage standards. If my changes look good, then you can set it to a positive review.

---

New commits:

f4a419c	Merge branch 'u/pportilla/ribbon_graphs' of trac.sagemath.org:sage into public/geometry/ribbon_graphs-21587
6b0f5fc	Reworking some things with the documentation and internal structures.

[tscrim]

Reviewer: Davis Coudert, Travis Scrimshaw

[tscrim]

Changed commit from 72ef663 to 6b0f5fc

[tscrim]

Changed branch from u/pportilla/ribbon_graphs to public/geometry/ribbon_graphs-21587

[tscrim]

Changed keywords from ribbon, surfaces, orientable to ribbon, surfaces, orientable, days79

[tscrim]

Changed reviewer from Davis Coudert, Travis Scrimshaw to David Coudert, Travis Scrimshaw

[dcoudert]

comment:53

In the _find method, you should add a TEST: section for the case when an error is raised.

Shouldn't you put almost all the introduction to the topic and so that you have in the class RibbonGraph in the module description ? In the class, you can then refer to the module's documentation.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

4e3b676

Added extra test to _find.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6b0f5fc to 4e3b676

[tscrim]

comment:55

Replying to @dcoudert:

In the _find method, you should add a TEST: section for the case when an error is raised.

Added.

Shouldn't you put almost all the introduction to the topic and so that you have in the class RibbonGraph in the module description ? In the class, you can then refer to the module's documentation.

No, you want the doc in the class-level doc because then it is accessible from the command line RibbonGraph?. It is also easy to find in the full doc page as well.

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:56

The changes look very good to me. (thank you).

If the other reviewer also agrees, it can be changed to positive_review.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

0075562

Added one method and one function. Both were already included in the next work I will be uploading when this is positively reviewed, but since they refer strictly to ribbon graphs I think that they suit better here.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4e3b676 to 0075562

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

6f4b8a6

Added a missing example.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0075562 to 6f4b8a6

[tscrim]

comment:59

David, any other comments?

[dcoudert]

comment:60

I don't really understand what is a ribbon graph, so it's not easy to comment. However, it is surprising to have methods for contracting and extruding edges but not a method to list vertices or edges.

Also, the method bipartite_rib that is added to the global namespace (I'm not sure it is useful here) should be renamed to e.g., bipartite_ribbon_graph or something like that.

a typo: A ribbon graph codified as two elements of a certaing permutation

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:61

Replying to @dcoudert:

I don't really understand what is a ribbon graph, so it's not easy to comment. However, it is surprising to have methods for contracting and extruding edges but not a method to list vertices or edges.

Also, the method bipartite_rib that is added to the global namespace (I'm not sure it is useful here) should be renamed to e.g., bipartite_ribbon_graph or something like that.

a typo: A ribbon graph codified as two elements of a certaing permutation

A ribbon graph is an object that recovers the topology of a surface with boundary. You can see it as the "spine" (a strong deformation retract) of a surface with boundary. The combinatorial data of a ribbon graph (the two permutations) allow us to unambiguously thicken the graph to a surface with boundary. I think that to people familiar with the mathematical object this implementation is quite natural.

I'm not on my laptop at the moment but I think that I state that one can look at the cycles that form sigma as the vertices and the cycles that form tho as the edges. The names are chosen sigma and tho because those are used in some texts as well as sigma_0 and sigma_1.

I don't understand what "useful" means in this context but the bipartite_rib function produces a lot of examples of ribbon graphs such that their thickenings (associated surfaces with boundary) are very much used in Singularity theory. In fact they are the building blocks for all Milnor fibers of plane curve singularities. And I will definitely use them on the implementation of tete-a-tete graphs.

I agree on changing the name as well as the other correction. I will fix them when I get home!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6f4b8a6 to 82b52eb

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

82b52eb

Fixed typos and normalized name of method.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 82b52eb to 87e3342

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b22ef55	Merge branch 'public/geometry/ribbon_graphs-21587' of trac.sagemath.org:sage into public/geometry/ribbon_graphs-21587
87e3342	Moving the bipartite construction into the RibbonGraph constructor.

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:64

I don't plan to update this ticket with new methods. I am also happy with your changes so whenever you think it is the time, you can positively review it.

Also, I created a new ticket #22016 to implement ribbon graphs (it depends on this ticket). However there seems to be some kind of problem: first, the branch name appears in read and second, I can't checkout that ticket.

[tscrim]

comment:65

I changed the constructor of RibbonGraph to allow access to the bipartite construction so we avoid putting more stuff in the global namespace.

Ribbon graphs also have appeared in the recent preprint https://arxiv.org/abs/1612.00061, where they are related to Brauer graph algebras. I'm not entirely convinced that getting a list of edges and vertices is useful with the current implementation.

So, since Pablo says my changes are good, I'm setting this to a positive review. David, if you have any objections, feel free to set back to needs work.

[dcoudert]

comment:66

No objection. Best,

[vbraun]

comment:67

3048[dochtml] [geometry ] /home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/geometry/ribbon_graph.py:docstring of sage.geometry.ribbon_graph.RibbonGraph.normalize:7: WARNING: Bullet list ends without a blank line; unexpected unindent.
3049[dochtml] Error building the documentation.
3050[dochtml] Traceback (most recent call last):
3051[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python/runpy.py", line 162, in _run_module_as_main
3052[dochtml]     "__main__", fname, loader, pkg_name)
3053[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python/runpy.py", line 72, in _run_code
3054[dochtml]     exec code in run_globals
3055[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
3056[dochtml]     main()
3057[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1667, in main
3058[dochtml]     builder()
3059[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 316, in _wrapper
3060[dochtml]     getattr(get_builder(document), 'inventory')(*args, **kwds)
3061[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 510, in _wrapper
3062[dochtml]     build_many(build_ref_doc, L)
3063[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 266, in build_many
3064[dochtml]     results.append(target(arg))
3065[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 70, in build_ref_doc
3066[dochtml]     getattr(ReferenceSubBuilder(doc, lang), format)(*args, **kwds)
3067[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 719, in _wrapper
3068[dochtml]     getattr(DocBuilder, build_type)(self, *args, **kwds)
3069[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 104, in f
3070[dochtml]     runsphinx()
3071[dochtml]   File "/home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage_setup/docbuild/sphinxbuild.py", line 215, in runsphinx
3072[dochtml]     raise exception
3073[dochtml] OSError: [geometry ] /home/buildbot/slave/sage_git/build/local/lib/python2.7/site-packages/sage/geometry/ribbon_graph.py:docstring of sage.geometry.ribbon_graph.RibbonGraph.normalize:7: WARNING: Bullet list ends without a blank line; unexpected unindent.
3074[dochtml] 
3075Makefile:1071: recipe for target 'doc-html-mathjax' failed
3076make[1]: *** [doc-html-mathjax] Error 1
3077make[1]: Leaving directory '/home/buildbot/slave/sage_git/build/build/make'

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

809412e

fixed indentation on docstring

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 87e3342 to 809412e

[5286a521-11fe-4c4e-9f98-8ed6b0603b1f]

comment:69

It should be fixed now. There were a couple of spaces missing in an OUTPUT environment.