Opened 22 months ago
Last modified 4 weeks ago
#26945 needs_work enhancement
Plumbing graphs
Reported by:  ghbaldursigurds  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  geometry  Keywords:  plumbing graph, 3manifolds, graph manifolds 
Cc:  pportilla  Merged in:  
Authors:  Baldur Sigurðsson  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghbaldursigurds/plumbing_graph (Commits)  Commit:  5f63b7385dcac9d56ec20e92144632c65e451f5c 
Dependencies:  Stopgaps: 
Description (last modified by )
We implement the calculus described in [Neu1981]. The plumbing construction creates a graph manifold (three dimensional) specified by a plumbing graph. Each vertex of the graph specifies an S^{1}bundle over a surface, and for each edge, the corresponding bundles are glued together in a specific way. Each vertex is decorated by the Euler number of the corresponding S^{1}bundle, the genus of the base of the fibration, and the number of boundary components of the surface, r. Each edge is decorated by +1 or 1, which specify different gluings.
The calculus of Neumann [Neu1981] consists of several operations, or moves, which can be applied to a plumbing graph to get the same manifold. The main result is that two graphs inducing homeomorphic (or, equivalently, diffeomorphic) plumbed manifolds are related by a finite sequence of these operations, or their inverses. Furthermore, each equivalence class of graphs by these operations contains a unique element, the minimal representative of this manifold, which can be obtained from any representative by applying the moves while possible.
As a special case, the resolution graph of an isolated surface singularity is a plumbing graph which describes the link of the singularity. A plumbing graph is so obtained if and only if all genera are positive, all edges are positive, and the associated intersection matrix is negative definite.
Another case related to singularity theory: As proved by N\'emethi and Szil\'ard [], the boundary of the Milnor fiber of a reduced hypersurface singularity in complex 3space is plumbed manifold. These do not necessarily have negative definite plumbing graphs, and may have negative edges as well.
We implement a class PlumbingGraph? which keeps track of the graph and the associated data. This class has as functions all the moves introduced by Neumann in [Neu1981], as well as checking all the minimality steps, and a function which reduces the graph to its minimal representative (so far, the function which reduces the graph to its minimal representative is not implemented, but it's being worked on). In the future, we should also implement a class which is associated with the graph a multiplicity system for a plumbing graph, as this allows for a lot of constructions, such as computing resolution graphs for susupension singularities, and the boundary of Milnor fibers in some special cases.
[Neu1981] Walter D. Neumann, *A calculus for plumbing applied to the topology of complex surface singularities and degenerating complex curves*, Transactions of the American Mathematical Society, Vol. 268, No. 2 (Dec., 1981), pp. 48074823
Change History (65)
comment:1 Changed 22 months ago by
 Commit set to f5d5cc4734982fcc051711040b6b38409045872f
comment:2 Changed 22 months ago by
 Description modified (diff)
comment:3 Changed 22 months ago by
 Commit changed from f5d5cc4734982fcc051711040b6b38409045872f to 96b5a63e42f3f41ba1b9b2836b1ad952bea7a6f7
Branch pushed to git repo; I updated commit sha1. New commits:
96b5a63  Added the function step_3() to the class PlumbingGraph, and an example.

comment:4 Changed 22 months ago by
 Commit changed from 96b5a63e42f3f41ba1b9b2836b1ad952bea7a6f7 to ab62c43d53a2005e1a2412787071aa72450046f7
Branch pushed to git repo; I updated commit sha1. New commits:
ab62c43  fixed a simple typo in the example for step_3()

comment:5 Changed 21 months ago by
 Milestone changed from sage8.6 to sage8.7
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sagepending or sagewishlist.
comment:6 Changed 21 months ago by
 Commit changed from ab62c43d53a2005e1a2412787071aa72450046f7 to 6e79dc16264227a1b6299caab167a6f297372d6d
Branch pushed to git repo; I updated commit sha1. New commits:
6e79dc1  at this point, all the functions for the algorithm for the minimal

comment:7 Changed 21 months ago by
 Branch changed from u/ghbaldursigurds/plumbing_graph to u/pportilla/plumbing_graph
comment:8 Changed 21 months ago by
 Cc pportilla added
 Commit changed from 6e79dc16264227a1b6299caab167a6f297372d6d to f9b45490ef45ccfd2203c96b685b8c092f1d46e8
Last 10 new commits:
97647c5  Merge branch 'develop' into t/22016/tat_graph22016

40c5042  Merge branch 'master' into u/pportilla/tat_graph22016

d10022a  Merge remotetracking branch 'origin/develop' into u/pportilla/tat_graph22016

e738728  Merge branch 'develop' of git://trac.sagemath.org/sage into t/22016/tat_graph22016

f37725f  fixing some error and preparing to start doc writing

fa3701e  Added references and some documentation of main object.

43f936e  ç

1dd6793  Merge branch 'u/pportilla/tat_graph22016' of git://trac.sagemath.org/sage into t/26945/plumbing_graph

5dda721  Merge branch 'u/ghbaldursigurds/plumbing_graph' of git://trac.sagemath.org/sage into t/26945/plumbing_graph

f9b4549  fixing intersection matrix plus allpy

comment:9 Changed 21 months ago by
 Branch changed from u/pportilla/plumbing_graph to u/ghbaldursigurds/plumbing_graph
 Commit changed from f9b45490ef45ccfd2203c96b685b8c092f1d46e8 to 2ba6beb01e7858680ab8eac3dc8af44bd7b57174
New commits:
2ba6beb  Many examples added, many still left to be written.

comment:10 Changed 20 months ago by
 Commit changed from 2ba6beb01e7858680ab8eac3dc8af44bd7b57174 to 4c1fd8a497709397abc228b00ffee0638cbe343c
Branch pushed to git repo; I updated commit sha1. New commits:
4c1fd8a  more examples

comment:11 Changed 20 months ago by
 Commit changed from 4c1fd8a497709397abc228b00ffee0638cbe343c to 1a35f8842362ed7c5e819d20709d8b4bda1976fb
Branch pushed to git repo; I updated commit sha1. New commits:
1a35f88  added a few more examples

comment:12 Changed 20 months ago by
 Commit changed from 1a35f8842362ed7c5e819d20709d8b4bda1976fb to a561f5b7bd72e44f240a1254a6f1be51e4fb91c2
Branch pushed to git repo; I updated commit sha1. New commits:
a561f5b  Finished first runthorough, so everybody has an example :)

comment:13 Changed 20 months ago by
 Commit changed from a561f5b7bd72e44f240a1254a6f1be51e4fb91c2 to 79ea6f6c77ab93fef473db6932dfe8642a7c6bc7
Branch pushed to git repo; I updated commit sha1. New commits:
79ea6f6  one more example in the beginning

comment:14 Changed 20 months ago by
 Status changed from new to needs_review
At this point, I've introduced moves R18, conditions N16 and steps 16, as well as several other functions, auxiliary or otherwise. All functions have an example. Adding the examples revealed a few errors, but the thing is running more or less.
comment:15 Changed 20 months ago by
 Commit changed from 79ea6f6c77ab93fef473db6932dfe8642a7c6bc7 to 3663fcd4d011c4d873676e0dcfb6a346289a7103
Branch pushed to git repo; I updated commit sha1. New commits:
3663fcd  deleted some files which I suspect came in when Pablo was playing with

comment:16 Changed 20 months ago by
 Commit changed from 3663fcd4d011c4d873676e0dcfb6a346289a7103 to 720a72ddc296b630ba3e84a6ad9e9c502622dc8b
Branch pushed to git repo; I updated commit sha1. New commits:
720a72d  I fixed some things because patchbot tests failed. I still don't know

comment:17 Changed 20 months ago by
 Commit changed from 720a72ddc296b630ba3e84a6ad9e9c502622dc8b to dbc68b7c4f82d14b82925efabfe3e8d31f62a750
Branch pushed to git repo; I updated commit sha1. New commits:
dbc68b7  ok, there was still stuff lingering, let's see if it runs this time

comment:18 Changed 20 months ago by
 Commit changed from dbc68b7c4f82d14b82925efabfe3e8d31f62a750 to b12cb8918126392e107eda82daed23d499a032e4
Branch pushed to git repo; I updated commit sha1. New commits:
b12cb89  Why is docbuild trying to compile tat_graph?

comment:19 Changed 20 months ago by
 Commit changed from b12cb8918126392e107eda82daed23d499a032e4 to 5a03aea83e92c6bdbe8a106576c49e4ba5d39b80
Branch pushed to git repo; I updated commit sha1. New commits:
5a03aea  just get the checks done

comment:20 Changed 20 months ago by
 Commit changed from 5a03aea83e92c6bdbe8a106576c49e4ba5d39b80 to 1bf25d7f791ed141decbe5737756913b1abda7a3
Branch pushed to git repo; I updated commit sha1. New commits:
1bf25d7  let's see if the tests run through with lazy_import

comment:21 Changed 19 months ago by
Why does this contain the têteàtête branch ? Does this ticket depend on #22016 ?
comment:22 Changed 19 months ago by
So yeah, this is a bit embarrasing, the ticket does not depend on #22016. The ticket got pulled into a directory where work was being conducted on that ticket, and by magical reasons, it got merged or something. The ticket should really only modify three files, that is the new file plumbing_graph.py, the corresponding sage/geometry/all.py, and then a reference to the article by Neumann in the appropriate bibliography. When I noticed that some extra files are in there, I tried deleting them, but I haven't figured out how to simply undo the merge somehow using appropriate git commands.
comment:23 Changed 19 months ago by
I would suggest :
 to copy the file plumbing_graph.py somewhere outside of sage,
 to recreate a clean new branch from the most recent develop, recopy the file plumbing_graph.py in sage and redo the other minor changes.
 commit and then
 push force the new branch here
comment:24 Changed 19 months ago by
 Commit changed from 1bf25d7f791ed141decbe5737756913b1abda7a3 to 4f6074a3f3011b8333361f83d9fb1d69efadf205
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
4f6074a  cleaning up, copying develop and adding plumbing_graph.py and oter things

comment:25 Changed 19 months ago by
good. Much better with a clean branch.
There should be an empty line after every line EXAMPLES::
You should build the doc and glance at the doc of your new module, to check that it looks fine.
comment:26 Changed 19 months ago by
I would rather not import 'genus_hash', 'big_genus_hash'
in the global namespace.
comment:27 Changed 19 months ago by
The doc is not formatted correctly
typically, instead of
+ EXAMPLES:: + + We test all the examples on p. 315 of [Neu1981]. + + The first example, only one vertex: + + sage: P = PlumbingGraph()
the double colon after EXAMPLES should be a single one, and the single colon after vertex should be a double one. Double colons should be followed by an indented block.
 one typo:
+ EXAPMLES::
 The first verb in any documentation string should be in imperative mode (no final s), for example: Check, Return, Compute, etc
 typos "apprears", chechs"
 this could be written in one line
+ if self.N6_c_find_candidate() == 1: + return False + else: + return True
could be
return self.N6_c_find_candidate() != 1
and then the method itself becomes rather useless..
 calls to references take a final underscore:
[Neu1981]_
 This
+ if len(L) == 0:
could be if not L:
 typo
realation
comment:28 Changed 19 months ago by
I will go through everything with your comments in mind soon. Some questions:
The functions genus_hash and big_genus_hash are used inside some functions in PlumbingGraph?, and so if I change the line in all.py so that it only imports PlumbingGraph?, then running ./sage t gives errors. What line should I put in all.py so that 'correct' things are imported?
Do you know a good reference for where these double colons are explained in details? I'm really just imitating other code, I haven't found the actual protocols for this.
Also, if it makes sense, I'll add a line to src/doc/en/reference/discrete_geometry/index.rst in order to make the documentation get built. I'm getting errors now, so I'll have something to work on. I'll get on it and push something later today.
comment:29 Changed 19 months ago by
 Commit changed from 4f6074a3f3011b8333361f83d9fb1d69efadf205 to 9c6e81524a75a8fbae04eaef9c48f32399b6dbe4
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
a561f5b  Finished first runthorough, so everybody has an example :)

79ea6f6  one more example in the beginning

3663fcd  deleted some files which I suspect came in when Pablo was playing with

720a72d  I fixed some things because patchbot tests failed. I still don't know

dbc68b7  ok, there was still stuff lingering, let's see if it runs this time

b12cb89  Why is docbuild trying to compile tat_graph?

5a03aea  just get the checks done

1bf25d7  let's see if the tests run through with lazy_import

2331ef8  Merge branch 'u/ghbaldursigurds/plumbing_graph' of git://trac.sagemath.org/sage into t/26945/plumbing_graph

9c6e815  added a line to the docs, it seems to compile

comment:30 Changed 19 months ago by
 for genus_hash and the other one, you should just start their own doctests with one line importing them.
for precise instructions on how the doc should be formatted
comment:31 Changed 19 months ago by
Why did you go back to your bad branch on top of teteatete ???
comment:32 Changed 19 months ago by
 Commit changed from 9c6e81524a75a8fbae04eaef9c48f32399b6dbe4 to 7f8b361ca4420857664c64ad21ae24768152a7d9
Branch pushed to git repo; I updated commit sha1. New commits:
7f8b361  Revert "Merge branch 'u/ghbaldursigurds/plumbing_graph' of git://trac.sagemath.org/sage into t/26945/plumbing_graph"

comment:33 Changed 19 months ago by
 Commit changed from 7f8b361ca4420857664c64ad21ae24768152a7d9 to f5140ad149f2c9e4c1e37f9d41717283c9fe536f
Branch pushed to git repo; I updated commit sha1. New commits:
f5140ad  the examples have double colons in the right places

comment:34 Changed 19 months ago by
Ok, the merge was not supposed to happen, I reverted it. The colons and double colons should be correct now, as well as the underscores for citations. I looked through the docs, they seem fine. The actual code will get some work asap.
comment:35 Changed 19 months ago by
concerning imports of genus_hash and big_genus_hash:
 remove their lazy imports
 add
sage: from sage.geometry.plumbing_graph import genus_hash
before the first test line here:+ EXAMPLES:: + + sage: genus_hash(2,3)
and the same thing in the doctests of big_genus_hash
comment:36 Changed 19 months ago by
 Commit changed from f5140ad149f2c9e4c1e37f9d41717283c9fe536f to 85118c82f2bcaa9b3c887a4e6a6b6013ed5a7f20
Branch pushed to git repo; I updated commit sha1. New commits:
85118c8  Went through it and simplified a couple of things, notably, got rid

comment:37 Changed 19 months ago by
 Commit changed from 85118c82f2bcaa9b3c887a4e6a6b6013ed5a7f20 to 0010ef0c9a2465a7d2371252823be3ad03bab90f
Branch pushed to git repo; I updated commit sha1. New commits:
0010ef0  one block corrected, what about \dh, or ð?

comment:38 Changed 19 months ago by
 this is missing a final :
+ OUTPUT
 Do not use this kind of doctest:
+ sage: P.nodes + <bound method PlumbingGraph.nodes of A plumbing graph with 7 vertices>
but rather doctests that really call the methods.
 This
+ if mc == set():
should rather be if not mc
which is faster
comment:39 Changed 19 months ago by
 Commit changed from 0010ef0c9a2465a7d2371252823be3ad03bab90f to d92b20b7e70d7d60c56bf10e573efd55c8f1a812
Branch pushed to git repo; I updated commit sha1. New commits:
d92b20b  Made some fixes pointed out by chapoton. Also added a missing reference

comment:40 Changed 19 months ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:41 Changed 18 months ago by
 Comparison to None should use
is not
instead ofj != None
 add some crossreferences using
.. SEEALSO
between the variousadd_something
methods
 do not use abreviated forms of verbs (Can't, don't, isn't, etc)
 When possible, the first sentence of the doc of each method should be a short description, followed by a blank line.
 This
+ if len(self.adj[e]) == 1: + return True + else: + return False
could be just
return len(self.adj[e]) == 1

+ if len(L) == 0:
should be if L
(and same at least in another place)
 range(0,n) should be range(n)
while not S == set({}):
should bewhile S
 This
if s%2 == 1:
could be justif s % 2:
comment:42 Changed 18 months ago by
 Commit changed from d92b20b7e70d7d60c56bf10e573efd55c8f1a812 to f1603e8a2715a72bf4f6d6fa81589aeeb593cea5
Branch pushed to git repo; I updated commit sha1. New commits:
f1603e8  A couple of improvements.

comment:43 Changed 17 months ago by
This
 if s%2 == 0: + if not s%2: self.add_vertex(e, 1, 0)  if s%2 == 1: + if s%2: self.add_vertex(e, 2, 0)
could use an elif
comment:44 Changed 17 months ago by
 Commit changed from f1603e8a2715a72bf4f6d6fa81589aeeb593cea5 to 573ebf1d7724ab9ea000771976839edeb722ebdf
Branch pushed to git repo; I updated commit sha1. New commits:
573ebf1  Simplified an if statement in step 6

comment:45 Changed 15 months ago by
 Milestone changed from sage8.8 to sage8.9
Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).
comment:46 Changed 15 months ago by
Hi Baldur, I didn't know that you were working on this, it is a nice addition.
Did you consider inheriting from graph (I think it would make sense since plumbing graphs are basically graphs with some extra decoration, but maybe that would be too much overhead). That way, for example, you would have methods to compute connectivity invariants, or to plot them, for free.
comment:47 Changed 15 months ago by
Hi Miguel,
I first used the graph class to encode the graph, but the problem I ran into is that in that class, you have vertices enumerated by a list, but the edges are just specified by the associated vertices. It feels a lot more natural to me to have a list of vertices, a list of edges, and a set of adjacent vertices associated with each edge. This way you can add and delete edges in a way that feels more natural.
More importantly, if you have an actual set of edges, you can define functions on that set, such as the plus/minus decoration. In further development, this kind of decorations will probably show up more and more, especially in algorithms translating one graph to another, such as between plumbing and splice graphs. Therefore, I would not like to express the +/ decorations by specifying the number of positive and number of negative edges joining any given pair of vertices, it seems that the code for that would be incomprehensible.
If anybody knows of a standard way to specify a function on the set of edges of a graph (using the graph class), let me know, it would probably be better, since you have all those graph theoretic functions for free. But this would mean that the graph class held on to an actual list of named edges, like it does for vertices, and it doesn't seem to me that this is the case.
If you have specific plumbing related algorithms in mind, let me know (or you can implement them when you want :). I thought about a few things to do with this, such as Oka's algorithm for Newton nondegenerate surface singularities, the splicequotient construction, the zeta function of Némethi or CampilloDelgadoGuseinZade. There are also some algorithms that compute the boundary of the Milnor fiber of a nonisolated hypersurface. I haven't started these, but they will each get a ticket in good time.
comment:48 Changed 15 months ago by
I see. In that case, at least a method to construct the underlying graph with the corresponding decorations would be nice (and would certainly be less work that writing a plot method).
comment:49 Changed 13 months ago by
 Status changed from needs_review to needs_work
red branch, meaning that it needs to be rebased on the latest beta
comment:50 Changed 10 months ago by
Hi, sorry for the absence. And also for for the ignorance. How do I rebase on the latest beta?
comment:51 Changed 9 months ago by
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:52 Changed 8 months ago by
 Commit changed from 573ebf1d7724ab9ea000771976839edeb722ebdf to 7293e399d491af544b5e70538babe83a2bce080f
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
bf584e8  cleaning up, copying develop and adding plumbing_graph.py and oter things

5d30199  added a line to the docs, it seems to compile

0dc50c4  Revert "Merge branch 'u/ghbaldursigurds/plumbing_graph' of git://trac.sagemath.org/sage into t/26945/plumbing_graph"

91be69e  the examples have double colons in the right places

5fa1fff  Went through it and simplified a couple of things, notably, got rid

f8adf0c  one block corrected, what about \dh, or ð?

db882a0  Made some fixes pointed out by chapoton. Also added a missing reference

74392d1  A couple of improvements.

1d6e7f8  Simplified an if statement in step 6

7293e39  Merge branch 'u/ghbaldursigurds/plumbing_graph' of git://trac.sagemath.org/sage into u/ghbaldursigurds/plumbing_graph

comment:53 Changed 8 months ago by
 Commit changed from 7293e399d491af544b5e70538babe83a2bce080f to b47423365dde171c7a544f3cff3c7034f11daa26
Branch pushed to git repo; I updated commit sha1. New commits:
b474233  I guess some references disappeard during some merging ...

comment:54 Changed 8 months ago by
 Commit changed from b47423365dde171c7a544f3cff3c7034f11daa26 to 438e0a7298d037c59306857ddb16b562d8bf9aaf
Branch pushed to git repo; I updated commit sha1. New commits:
438e0a7  added feature to export Graph()

comment:55 Changed 8 months ago by
 Commit changed from 438e0a7298d037c59306857ddb16b562d8bf9aaf to 312a3914e35711fef66745d9bb47b74a155d27b9
Branch pushed to git repo; I updated commit sha1. New commits:
312a391  What is this blocks error?

comment:56 Changed 8 months ago by
 Commit changed from 312a3914e35711fef66745d9bb47b74a155d27b9 to 62a316906964c34448c2212473e1c651f01c8f04
Branch pushed to git repo; I updated commit sha1. New commits:
62a3169  not use 'Returns'

comment:57 Changed 8 months ago by
 Commit changed from 62a316906964c34448c2212473e1c651f01c8f04 to 1aa4e66c7fe63fa53a74201d0c7b4ef1b3a5de01
Branch pushed to git repo; I updated commit sha1. New commits:
1aa4e66  fixed an error in intersection_matrix()

comment:58 Changed 8 months ago by
 Commit changed from 1aa4e66c7fe63fa53a74201d0c7b4ef1b3a5de01 to aa439993d05f6cff85970aba25eba8bd144a53c6
Branch pushed to git repo; I updated commit sha1. New commits:
aa43999  added determinant of a graph

comment:59 Changed 7 months ago by
 Commit changed from aa439993d05f6cff85970aba25eba8bd144a53c6 to 5f63b7385dcac9d56ec20e92144632c65e451f5c
Branch pushed to git repo; I updated commit sha1. New commits:
5f63b73  comment out Graph() stuff in case it's slowing everything down

comment:60 Changed 7 months ago by
 Status changed from needs_work to needs_review
This seems to pass the tests now. Feel welcome to review it :)
comment:61 Changed 7 months ago by
You can label the edges of the graph, which works reasonably well for multiedge graphs too. Would this work? Have you also considered just using your plumbing graph class as a façade class for a Sage graph (i.e., you implement the methods you want and store the graph as some _graph
attribute)?
Also another quick comment, I think the stepX()
methods should be hidden, i.e., _stepX()
.
comment:62 Changed 7 months ago by
When I started this project, I imagined it woud be easier to just use a Graph() for the graph, and work around that. But I got frustrated not being able to specify an edge directly, and eded up working with just a set of vertices (integers) and edges (again integers), which seems straightforward enough. At some point, I added a function which exports the graph to a Graph(), just to have access to the .plot() function, but the tests said it took too long to load, and didn't approve it, so I commented it out.
I thought about making the step functions hidden, but these are the steps in the original article, and I imagine that people who have read it might want to have them available, it coud be useful. Even if just to see what happens to their favorite graph along each step.
comment:63 Changed 6 months ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:64 Changed 7 weeks ago by
 Status changed from needs_review to needs_work
red branch => needs work
comment:65 Changed 4 weeks ago by
 Milestone changed from sage9.2 to sage9.3
Branch pushed to git repo; I updated commit sha1. New commits:
initial commit for plumbing_graph
removed some unnecessary lines