search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.37k stars 466 forks source link

Create a random triangulation (max planar graph) #10276

Closed db989cf6-1213-48bd-b6c2-6b6971934065 closed 9 years ago

db989cf6-1213-48bd-b6c2-6b6971934065 commented 13 years ago

This is a new graph generator to create a random triangulation, i.e., a random planar graph all of whose faces are triangles (3-cycles). We do this by generation points iid uniformly on the surface of a sphere, finding the convex hull of those points, and returning the 1-skeleton of that polyhedron.

There might be numerical issues with the convex hull here, so we by default work over QQ

CC: @dcoudert

Component: graph theory

Keywords: random graph

Author: Ed Scheinerman

Branch/Commit: 9a682fa

Reviewer: Nathann Cohen, Frédéric Chapoton, Dima Pasechnik

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

db989cf6-1213-48bd-b6c2-6b6971934065 commented 13 years ago
comment:1

Attachment: trac_10276.patch.gz

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 12 years ago

Attachment: trac_10276-random-triangulation-rebase.patch.gz

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 12 years ago

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
 This is a new graph generator to create a random triangulation, i.e., a random planar graph all of whose faces are triangles (3-cycles). We do this by generation points iid uniformly on the surface of a sphere, finding the convex hull of those points, and returning the 1-skeleton of that polyhedron.
+
+**Apply:**
+
+1. [attachment: trac_10276-random-triangulation-rebase.patch](https://github.com/sagemath/sage-prod/files/10651406/trac_10276-random-triangulation-rebase.patch.gz)
1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 12 years ago
comment:2

Dear Ed,

Nice. I needed this for a course, so I rebased it against 4.8.alpha6. Only the author credit was failing, so it was a trivial fix.

How much work would it be to get layout information from the locations on the sphere? I would think a projection onto the plane might be better than what a planar layout currently provides and would be simpler computationally. Could you easily locate the "largest" face to be the exterior?

I'll try to stick with this for a review - I'd like to see it in Sage.

Thanks, Rob

db989cf6-1213-48bd-b6c2-6b6971934065 commented 12 years ago
comment:3

Hi Rob, I wrote this over a year ago, so it's not fresh in my mind. As best I recall, this should create a planar graph in which all faces are triangles, so all faces are "largest". Is there something I need to do to keep this moving? (Should I click one of the "action" buttons?) Best, Ed

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 12 years ago
comment:4

Replying to @sagetrac-edward-scheinerman:

Dear Ed,

Is there something I need to do to keep this moving?

Yes, I noticed it had been dormant for a while. My students here at AIMS have been using this the past few days, so I could probably give it a positive review right now. But it seems silly not to provide a layout (or a planar embedding) when it seems that all that information could be obtained from what is already computed. In other words, it should be relatively easy to improve on 

G = graphs.RandomTriangulation(40)
G.plot(layout='planar')

both in execution time and visual quality. Maybe an embedding is already available from the 1-skeleton or something. I am happy to pursue contributing code for the layout if you are not interested, or I could review something you would add. Whatever is your pleasure.

So not really anything official to do to move this along at the moment. I'm suggesting the improvement of adding a layout (with code from either of us) and would like to work this through to a positive review.

Rob

db989cf6-1213-48bd-b6c2-6b6971934065 commented 12 years ago
comment:5

Hi Rob,

I thought about this some more. Your comments make perfect sense. The RandomTriangulation method can edited to provide an embedding by stereographically projecting the vertices of the polytope into the plane. But I fear that this would give pictures that are mathematically correct but visually awful. I can sketch out the method offline if you like.

What Sage really needs (and I'm not knowledgeable enough to do this) is a really good planar graph layout algorithm. Compare:

g = graphs.DodecahedralGraph()
g.show()

to

g = graphs.DodecahedralGraph()
g.plot(layout='planar')

If you think adding the stereographic projection embedding is worthwhile, I'd be happy to have you add it to this method. (I found creating patches and the like to be non-intuitive ... I'm willing to work on the code, but then have you upload it to this site :-)

Best, Ed

1d7ec08f-60ae-4512-91a6-8324c06eab9f commented 12 years ago
comment:6

Dear Ed,

That all sounds good. I think a graph can carry an embedding, as a logical construction - the neighbors of a vertex as an ordered list, we ought to capture that at a minimum. (Need to double-check on that.) Then if a general layout algorithm can utilize that information, the visual appeal might improve in the future. But I would like to see if the actual coordinates from the stereographic projection are useful as well. And I may appeal to the sage-devel list for ideas.

So, please send me any ideas for code off-list at beezer@ups.edu and I'll see what I can do. Next two weeks are very hectic - finishing a course in Cape Town and starting new ones at home, so there may be a delay until life settles down.

Thanks, Rob

fchapoton commented 10 years ago
comment:7

for the patchbot:

apply trac_10276-random-triangulation-rebase.patch

fchapoton commented 10 years ago

Attachment: trac_10276-random-triangulation-rebase_v2.patch.gz

fchapoton commented 10 years ago

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 **Apply:**

-1. [attachment: trac_10276-random-triangulation-rebase.patch](https://github.com/sagemath/sage-prod/files/10651406/trac_10276-random-triangulation-rebase.patch.gz)
+1. [attachment: trac_10276-random-triangulation-rebase_v2.patch](https://github.com/sagemath/sage-prod/files/10651407/trac_10276-random-triangulation-rebase_v2.patch.gz)
fchapoton commented 10 years ago
comment:8

for the patchbot:

apply trac_10276-random-triangulation-rebase_v2.patch

I have just rebased the patch..

fchapoton commented 10 years ago

Changed keywords from none to random graph

fchapoton commented 9 years ago

Commit: 0158086

fchapoton commented 9 years ago

Branch: u/chapoton/10276

fchapoton commented 9 years ago

New commits:

a1897a4trac #10276 -- Random triangulation (max planar graph) generator
5ac50eatrac #10276 details (pep8)
0158086trac #10276 allow to use stereo projection
dcoudert commented 9 years ago
comment:10

Hello,

I have a random error with your code, not directly caused by your code. From time to time, the following happens:

sage: g = graphs.RandomTriangulation(70, embed=True)
sage: g
Planar triangulation on 70 vertices
sage: g = graphs.RandomTriangulation(70, embed=True)
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-44-2d58770e9f2f> in <module>()
----> 1 get_ipython().magic(u'time g = graphs.RandomTriangulation(70, embed=True)')

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in magic(self, arg_s)
   2203         magic_name, _, magic_arg_s = arg_s.partition(' ')
   2204         magic_name = magic_name.lstrip(prefilter.ESC_MAGIC)
-> 2205         return self.run_line_magic(magic_name, magic_arg_s)
   2206 
   2207     #-------------------------------------------------------------------------

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/interactiveshell.pyc in run_line_magic(self, magic_name, line)
   2124                 kwargs['local_ns'] = sys._getframe(stack_depth).f_locals
   2125             with self.builtin_trap:
-> 2126                 result = fn(*args,**kwargs)
   2127             return result
   2128 

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in time(self, line, cell, local_ns)

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/magic.pyc in <lambda>(f, *a, **k)
    191     # but it's overkill for just that one bit of state.
    192     def magic_deco(arg):
--> 193         call = lambda f, *a, **k: f(*a, **k)
    194 
    195         if callable(arg):

/Users/dcoudert/sage/local/lib/python2.7/site-packages/IPython/core/magics/execution.pyc in time(self, line, cell, local_ns)
   1127         else:
   1128             st = clock2()
-> 1129             exec(code, glob, local_ns)
   1130             end = clock2()
   1131             out = None

<timed exec> in <module>()

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generators/random.pyc in RandomTriangulation(n, embed)
    835 
    836     # extract the 1-skeleton
--> 837     g = P.vertex_graph()
    838     g.rename('Planar triangulation on {} vertices'.format(n))
    839     if embed:

/Users/dcoudert/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13663)()
   2207         if self.cache is None:
   2208             f = self.f
-> 2209             self.cache = f(self._instance)
   2210         return self.cache
   2211 

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in vertex_graph(self)
   2933             True
   2934         """
-> 2935         return Graph(self.vertex_adjacency_matrix(), loops=False)
   2936 
   2937     graph = vertex_graph

/Users/dcoudert/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13663)()
   2207         if self.cache is None:
   2208             f = self.f
-> 2209             self.cache = f(self._instance)
   2210         return self.cache
   2211 

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in vertex_adjacency_matrix(self)
   1638             (0, 0, 1, 1, 0) A vertex at (3, 0)
   1639         """
-> 1640         return self._vertex_adjacency_matrix()
   1641 
   1642     adjacency_matrix = vertex_adjacency_matrix

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in _vertex_adjacency_matrix(self)
    286             M[j,i]=1
    287 
--> 288         face_lattice = self.face_lattice()
    289         for face in face_lattice:
    290             Vrep = face.ambient_Vrepresentation()

/Users/dcoudert/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13663)()
   2207         if self.cache is None:
   2208             f = self.f
-> 2209             self.cache = f(self._instance)
   2210         return self.cache
   2211 

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in face_lattice(self)
   2815         return Hasse_diagram_from_incidences\
   2816             (atoms_incidences, coatoms_incidences,
-> 2817              face_constructor=face_constructor, required_atoms=atoms_vertices)
   2818 
   2819     def faces(self, face_dimension):

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/geometry/hasse_diagram.pyc in Hasse_diagram_from_incidences(atom_to_coatoms, coatom_to_atoms, face_constructor, required_atoms, key, **kwds)
    188     # Make sure that coatoms are in the end in proper order
    189     tail = [faces[atoms, frozenset([coatom])]
--> 190             for coatom, atoms in enumerate(coatom_to_atoms)]
    191     tail.append(faces[A, frozenset()])
    192     new_order = [n for n in new_order if n not in tail] + tail

KeyError: (frozenset([]), frozenset([132]))

David.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:12

Hellooooo,

I just looked at this code, and I thank you very very much for reminding me that the normal distribution was invariant by rotation. I had totally forgotten this, and it is soooo elegant to be able to sample sphere point uniformly this easily ;-)

I added a small commit at public/10276 which does no non-trivial things. If you do not see anything wrong with it, you can change the ticket's status to positive_review.

Thankssssss,

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

Reviewer: Nathann Cohen

fchapoton commented 9 years ago
comment:13

The random failure is probably still there..

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:14

The random failure is probably still there..

needs_work then?

fchapoton commented 9 years ago
comment:15

I do not know what to do. Some time ago, I have tried to understand the failure, but did not succeed.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:16

Well.. Given that it is not caused by your code, can't we still merge this patch? There seems to be a bug alright and it will have to be fixed, but that's not a reason to hold this one back.

Nathann

dimpase commented 9 years ago

a deterministic way to get the error

dimpase commented 9 years ago
comment:17

Attachment: x.sage.gz

now we just fix this (hopefully) :-)

fchapoton commented 9 years ago
comment:18

ok, then I have no longer any objection against this ticket. Another ticket should be created for the polyhedron problem.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:19

Okayyyyyyyyyyyyyyyyyyy!

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:22

Could you decide what you want to do with my additional commit (see [comment:12])?

dimpase commented 9 years ago
comment:23

No, the bug is here, not elsewhere - it is a loss of precision issue, one cannot handle these points using RDF, you need exact field. I'll post a fix soon.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago
comment:24

I added a second commit from Dima at public/10276 (he couldn't push it himself, some git oddity).

Nathann

dimpase commented 9 years ago

Changed branch from u/chapoton/10276 to public/10276

dimpase commented 9 years ago

Changed commit from 0158086 to 1ea5a64

dimpase commented 9 years ago
comment:25

I'm happy with this branch. By the way, the example in the attachment illustrating the bug produces a polytope with 136 trianglular faces, but if the base_ring=RDF then one triangle does not contain any vertices (loss of precision happens). With base_ring=QQ it's all right, of course.

New commits:

e742c9etrac #10276: Merged with 6.8.beta6
7eef844trac #10267: Reviewer's commit
1ea5a64trac #10276: Reviewer's commit
dimpase commented 9 years ago

Changed reviewer from Nathann Cohen to Nathann Cohen, Frédéric Chapoton, Dima Pasechnik

dimpase commented 9 years ago
comment:26

docs don't build, as QQ is not imported. will fix this now.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

9a682faQQ must be imported
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 1ea5a64 to 9a682fa

dimpase commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,3 @@
 This is a new graph generator to create a random triangulation, i.e., a random planar graph all of whose faces are triangles (3-cycles). We do this by generation points iid uniformly on the surface of a sphere, finding the convex hull of those points, and returning the 1-skeleton of that polyhedron.

-**Apply:**
-
-1. [attachment: trac_10276-random-triangulation-rebase_v2.patch](https://github.com/sagemath/sage-prod/files/10651407/trac_10276-random-triangulation-rebase_v2.patch.gz)
+There might be numerical issues with the convex hull here, so we by default work over `QQ`
vbraun commented 9 years ago
comment:29

PSA: Tickets without a milestone set are not going to be merged. Not sure if its intentional, just trying to get the word out.

vbraun commented 9 years ago

Changed branch from public/10276 to 9a682fa