Javascript editor to manipulate knot diagrams
Jason Suagee
Hello Sage mentors and fellow posters,
My name Jason Suagee and I'm a 4th year PhD student in mathematics at George Washington University in Washington DC. I am primarily interested in working on a javascript editor for manipulating knot diagrams as part of the knot theory project. My background in knot theory comes mostly from Rolfsen's classical Knots and Links book, which was the primary textbook for a two semester course in knot theory that I am currently taking this academic year.
In my own work I focus on symmetric
combinatorial decompositions of 3-manifolds, which is a cross between
low dimensional topology and topological graph theory. Where this
intersects with knot theory is that much of knot theory is actually
used as a tool to describe 3-manifolds. In particular, one of the
most useful methods to present a 3-manifold is by performing Dehn
surgery on the components of a link in S^3. So manipulation of link
diagrams can be a big part of what low dimensional topologists do on
a regular basis.
But manipulating a link diagram on paper can be a real headache, as I have found out this year. It would be beneficial if there was a graphical way by computer to do these manipulations. I have thought out a rough framework with which to approach this design problem and will share it in the post below.
By the way, I have been a Sage user for the past 4 years and love it! I was quite happy to sport a Sage sticker at the joint math meeting this year in Baltimore.
Best,
Jason
Jason Suagee
These are just some thoughts on the direction the javascript editor might go:
We can represent link diagrams by signed planar graphs where the sign on the edges gives us the crossing information (as depicted in http://en.wikipedia.org/wiki/Knots_and_graphs). We could then fill in the arc components of the link by using Bezier curves. An advantage of using this framework is that we can leverage existing planar graph drawing algorithms that have working computer implementations.
We can enable the user to perform isotopy moves on the link diagram by using the vertices of the underlying planar graph as control points to click and drag. There are several other parameters that I can think of that can be manipulated, but I won't flood this post with all of them.
Reidemeister moves change the underlying graph, so they have to be treated differently from isotopy of the diagram. We would need a way of selecting the arc components on which we are performing a Reidemeister move (For more complex diagrams this might involve grouping 2 or more arc components together so that they act as one arc component during the move).
Also, if we want to be able to perform calculations about 3-manifolds, we have to be able to add and/or remove link components to the diagram which might drastically change the underlying graph. We also would want to keep track of surgery coefficients associated to link components, which involves computing linking numbers.
[An interesting idea would be to create the data structure for the link diagram so that it is actually a record of all of the moves performed (isotopy, Reidemeister, etc..), sort of like a word processor document. The user could undo moves because there would be a history included in the data structure.]
If additional time permits:
Might want to create useful methods for creating knots, like ways to construct satellites of knots or cables of knots. Maybe adapt this so that the user can also work with braid representations of knots and links. There is also a move called the Rolfsen Twist, which I would like to implement. A picture of it can be found in this google book link:
Some things that would be good to set up:
#connected components
Fundamental group presentations (not always a useful invariant, but it's easy to get a presentation)
Linking numbers
Maybe someone working on the other end of the project could implement methods to calculate the Torsion invariants and the Alexander Polynomial in the case where the diagram is just a knot.
Additionally, the Jone's polynomial can be calculated directly from the Tutte polynomial of the underlying graph (although this is algorithmically hard).
Possible extensions:
This all might be later extended to become a graphical Kirby Calculus tool, but that is just a thought at this point.
Miguel Angel Marco
Jason Suagee
I attempted to get knotscape working,
but the program hung when I clicked on one of the menu buttons (this
might be an issue with Tcl or Tk). I was able to check out the link
drawing utility linkscape, so I have a good idea of how that works.
Since knotscape hung I don't know how it plots a knot, is it a 3D
representation (similar to that of say Mathematica). In order to get
knotscape to work with my linux distro I would probably have to
downgrade Tcl and Tk to an older version, which I don't particularly
want to get into right now.
One of the knot theorists at my university, Alex Shumakovitch, expressed to me yesterday his desire for a particular kind of knot diagram manipulation interface that was more natural, or closer to how a person might manipulate an actual knot. While manipulating a knot diagram one often combines many Reidemeister moves into one, for instance when pulling an arc component over a complicated part of the knot. What he was saying is that it would be neat if you could do all of this manipulation on a computer without chugging through individual Reidemeister moves. I can post a scanned picture if this is unclear which will illustrate what I mean when I am at the university tomorrow.
If you try to manipulate an actual real knot though you'll quickly run into a problem: parts of the knot become very complicated, a lot goes on in a small amount of space whereas other parts of the knot may not have anything going on. If you're manipulating a diagram on a computer you would want to be able to resize/readjust the diagram to create more room for these complicated parts.
While I had originally conceived of something 2D, Alex gave me the impression that what he would like would be more useful. So I thought a bit about how his idea might be made to work:
It would be pretty hard to do. You could plot the knot using OpenGL, or WebGL since most people use Sage through the notebook interface which runs on a browser. Instead of allowing a full 3D environment with no preferred viewing angle, which could end up being disorienting for the user, you could restrict the knot to a bounding box that is a thickened plate (say if your looking at it from the point (1,1,1), the area where the knot would be depicted would be in {(x,y,z) : -1 < x < 1, -1 < y < 1, -0.1 < z < 0.1} ). Below, I'm going to call this kind of depiction of a knot a “thickened planar drawing”.
I haven't been able to come up with a good way of emulating physical knot manipulation yet, although I haven't had much time to think about it. It would have to be computationally feasible, so that probably rules out schemes which involve a lot of computational geometry (like intersection checking to make sure components of the link don't pass each other and stay reasonably spaced out). There is a whole area of knot theory called physical knot theory which might contain something useful?
Perhaps we could use the fact that the knot would be a thickened planar diagram, since it lies in a thickened plate, to reduce the amount of computational geometry that needs to be performed.
The other part of the picture is how you resize/readjust the drawing after you have performed a manipulation. All I can think of at the moment is that you could look at a planar knot diagram for the drawing (just project down into the x,y-plane). You could then use a force-directed graph drawing algorithm to re-render/adjust the underlying signed planar graph that I mentioned in the last post. The graph then could be used to re-render the knot diagram, which can be translated back into a thickened planar drawing.
If we pursued this strategy of a 3D representation I don't think that any of the other things that I said, like linking numbers and surgery coefficients, could be simultaneously accomplished over one summer by one person. According to the scheme it's conceptually easy to recover a planar knot diagram from the 3D drawing, so another programmer could work on the project from that perspective (calculating everything from some planar diagram representation), while another person works on building a 3D manipulation tool.
I acknowledge that this direction for your project might be too involved for one summer. I think it might be possible to do though. Let me know what you think. I might not respond till Thursday because I teach back to back all day today and might be pretty tired when I get home.
Miguel Angel Marco
El martes, 4 de marzo de 2014 13:25:59 UTC+1, Jason Suagee escribió:
Dima Pasechnik
>
>
> I attempted to get knotscape working, but the program hung when I clicked
> on one of the menu buttons (this might be an issue with Tcl or Tk). I was
> able to check out the link drawing utility linkscape, so I have a good idea
> of how that works. Since knotscape hung I don't know how it plots a knot,
> is it a 3D representation (similar to that of say Mathematica). In order to
> get knotscape to work with my linux distro I would probably have to
> downgrade Tcl and Tk to an older version, which I don't particularly want
> to get into right now.
Tcl/Tk vesrions involved? (perhaps by opneing an issue on the github
repo https://github.com/dimpase/knotscap)
[...]
> While I had originally conceived of something 2D, Alex gave me the
> impression that what he would like would be more useful. So I thought a bit
> about how his idea might be made to work:
>
>
> It would be pretty hard to do. You could plot the knot using OpenGL, or
> WebGL since most people use Sage through the notebook interface which runs
> on a browser.
such as tree.js
Jason Grout
> nowadays these things are normally done using higher level interfaces to WebGL,
> such as tree.js
Just FYI, we are developing a low-level three.js<->python bridge that we
plan to integrate into the sage 3d plotting system. Our (rough) work is
here: https://github.com/jasongrout/pythreejs, and I've been posting
examples to the sage-cell google group.
Regardless of whether you use pythree.js or not, I think using the
IPython comm/widget architecture would maybe be a good idea---changes to
the knot editor could easily be reflected in the python world, and vice
versa.
Thanks,
Jason
Miguel Angel Marco
Jason Grout
> Does it mean that it would be possible to edit the knot on the notebook
> (or cell) and update the sage object on real time? Or is it more like
> the graph editor, where there is a button to "save" the status of the
> editor into the sage object?
Jason
Jason Suagee
Nevermind, there was no bug in knotscape, I just forgot to read the tutorial. My apologies.
Jason Suagee
Robert Scharein’s method of smoothing the knot seems entirely reasonable to implement. What’s the legality of implementing his methods? Can we just borrow the techniques that he uses in his thesis?
Here’s more of a research question which I just thought of:
Regarding the bounding box check referred to on page 125, I wonder if in fact one could just use the Taxi-cab metric instead of the regular Euclidean distance to perform the collision avoidance calculations. Would the relaxation algorithm essentially run the same way (you might have to increase the number of beads to get it to work)? The Taxi-cab metric has the benefit that it is much easier to evaluate, which can allow you to have a lot more beads and get a smoother knot diagram. Scharein says that he got a speed increase of about five-fold by relying mostly on the bounding box method for collision avoidance.
Otherwise:
Push/Pull rockets described on page 130 could be used to interactively modify the diagram. The user would select a bead with the mouse and give it a push in a given direction. The diagram is 3 dimensional so how the user specifies the direction to move the bead would have to be worked out. However, if we could constrain the diagram to be mostly planar, then we could specify the direction by just pushing the mouse.
Also, there is some discussion on this mailing list of getting a Sage app working for tablets. Wouldn’t it be a nice idea to create a knot manipulation interface for a tablet that was touch based? The user could manipulate the knot with his fingers using the Push/Pull rockets idea.
Dima Pasechnik
>
>
> Robert Scharein’s method of smoothing the knot seems entirely reasonable to
> implement. What’s the legality of implementing his methods? Can we just
> borrow the techniques that he uses in his thesis?
It's another question whether it's legal to take someone's else
code and put it into Sage, or look at someone's else
code while doing a Sage implementation (these would depend
on the code's license). But ideas from published books/papers/theses
are pretty much up for grabs.
HTH.
Miguel Angel Marco
El jueves, 6 de marzo de 2014 20:11:10 UTC+1, Jason Suagee escribió:
Robert Scharein’s method of smoothing the knot seems entirely reasonable to implement. What’s the legality of implementing his methods? Can we just borrow the techniques that he uses in his thesis?
Here’s more of a research question which I just thought of:
Regarding the bounding box check referred to on page 125, I wonder if in fact one could just use the Taxi-cab metric instead of the regular Euclidean distance to perform the collision avoidance calculations. Would the relaxation algorithm essentially run the same way (you might have to increase the number of beads to get it to work)? The Taxi-cab metric has the benefit that it is much easier to evaluate, which can allow you to have a lot more beads and get a smoother knot diagram. Scharein says that he got a speed increase of about five-fold by relying mostly on the bounding box method for collision avoidance.
Otherwise:
Push/Pull rockets described on page 130 could be used to interactively modify the diagram. The user would select a bead with the mouse and give it a push in a given direction. The diagram is 3 dimensional so how the user specifies the direction to move the bead would have to be worked out. However, if we could constrain the diagram to be mostly planar, then we could specify the direction by just pushing the mouse.
Dima Pasechnik
>
>
> El jueves, 6 de marzo de 2014 20:11:10 UTC+1, Jason Suagee escribió:
>>
>> Robert Scharein’s method of smoothing the knot seems entirely reasonable
>> to implement. What’s the legality of implementing his methods? Can we just
>> borrow the techniques that he uses in his thesis?
>>
>
> If it is not patented (which i am not sure about, but i have seen no patent
> claim at all in his website or software) we can do our own implementation
> based on his thesis. What we could not do is to make a derivative of his
> code; but if we don't have access to his source code, we wouldn't be doing
> a derivative work, just a reimplementation of the same ideas.
No, really, there is no "practical" significance in this work.
Jason Suagee
Good that there is no possible legal issue.
So, I've been playing around with knotplot a bit, and have been looking at his thesis which explains it pretty well. There are a lot of options to play around with and I'm still trying to figure out most of them.
From my perspective, when it comes to visualization knotplot is really good at smoothing out knots and resizing/readjusting the complicated parts of the diagrams, as I referred to above. I think knot support in Sage should definitely incorporate these methods.
Editing a knot in knotplot can be pretty difficult though, at least as I experienced it. Most of the editing I was trying to do was with the push/pull rockets, where you can grab a node or a stick between nodes, and push it in some direction that you want that part of the knot to go. You can constrain the push force to lie in say the xy plane, or a single axis direction, and you can rotate the viewing orientation. Theoretically you can make any adjustments to the knot that you want by switching force directions, rotating the view as necessary, and stopping and starting the smoothing dynamics as often as needed, but its not intuitive or easy. When it comes to knot manipulation, my opinion is that knotplot is not actually a good substitute for old fashioned planar knot diagrams. Also, since everything is going on in 3D, I can see that it would be easy to loose track mid-process of what you were trying to do with the knot or link in the first place.
The only thing about planar knot diagrams is that on paper at least, you have to constantly erase and redraw your knot, and mistakes are easily made. Also, you don't have automatic smoothing and rearranging of complex parts that you get with knotplot.
I think you can combine both of these approaches though and produce a very good tool to manipulate knot diagrams (and interface to all the other calculation goodies that you need). The main idea I am considering is that you can restrict the knot drawing to be mostly planar (to be relatively near the xy-plane) by adding in an external force which compresses the knot into a region near the xy-plane. For instance a force with magnitude proportional to z^4 directed towards the xy-plane, which would keep the knot roughly within a squashed rectangular region that would look like this:
R: -20 < x < 20, -20 < y < 20, -1 < z < 1
If the user then wanted to do some manipulation on the knot, such as what would amount to a combination of Reidemeister 2 moves for instance, he could pull a piece of the knot out of the region R, apply a push/pull force with the mouse to the part of the knot he wished to move, lift it out of the region R, and then let it go when it had reached the place he wanted it to be. The affected part of the knot would then just fall back down into the region R, and the smoothing dynamics would do the rest.
(What I just wrote smooths under the rug a lot of user interface details, but its just a general idea.)
The diagram could also be made stable by basically making the thickness of the knot a large enough fraction of the height of the region R (in this case the height is 2, so if the thickness of the knot were say 2/3 the diagram would be stable).
There are some other benefits to this approach. It would be very easy to get a planar diagram (just project down into the xy-plane), and it would be easier to keep a step by step record of how the knot was rearranged during a manipulation process (also because of the ease of getting planar diagrams). It would also be fairly easy to convert other more compact representations of a knot into this form. You just have to specify a height function for points in the planar diagram.
I can start working on a proposal for this, but I just wanted to check if this sounds like something you would want, or if you have any suggestions that I should consider?
Dima Pasechnik
knotplot computes, such as Alexander polynomial, and ways to getting
them imported into Sage; as far as I remember, knotplot outputs tables
of coefficients of these polynomials; anything you would design should
produce Sage polynomials...
Miguel Angel Marco
Miguel Angel Marco
Jason Suagee
Miguel Angel Marco
Miguel Angel Marco
El martes, 4 de marzo de 2014 13:25:59 UTC+1, Jason Suagee escribió:
Amit Jamadagni
I am been working on my proposal for the implementation on the back-end. I have posted the link to my proposal on the other google thread (I kindly request to refer to it for all the details). I am really looking forward to discuss the ideas of how we can get the entire machinery (back-end + front-end) to work. I hope we (It would be great if the discussion can be done in the presence of our mentor) can discuss it here or on irc chat about what we require in common and on how one could facilitate as well compliment each other's work keeping it as independent as possible. Thanks.
--For more options, visit https://groups.google.com/d/optout.
You received this message because you are subscribed to the Google Groups "sage-gsoc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-gsoc+...@googlegroups.com.
To post to this group, send email to sage...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-gsoc.
Jason Suagee
Amit Jamadagni
I have gone through the attached document, on a quick glance I could get the structure but understanding the details is taking time for me. I would like to know how my work can compliment yours on the front end. In sense it would great if you could sketch an outline of what features from the backend (There was a section in the document on what you expected from the backend) you would like me to work on so that the editor could be more complete. I guess we need to work on this as the deadline is fast approaching. I would like to know if we could communicate via irc at some particular time. It would give a more clearer picture to construct our proposals as well. Thanks.
Burcin Erocal
I'm not a mentor for this project and I have not followed the related
discussion on this list. But here is my 5 cents...
On Tue, 18 Mar 2014 18:04:59 +0530
Amit Jamadagni <bitsja...@gmail.com> wrote:
> Hi Jason,
> I have gone through the attached document, on a quick glance I
> could get the structure but understanding the details is taking time
> for me. I would like to know how my work can compliment yours on the
> front end. In sense it would great if you could sketch an outline of
> what features from the backend (There was a section in the document
> on what you expected from the backend) you would like me to work on
> so that the editor could be more complete. I guess we need to work on
> this as the deadline is fast approaching. I would like to know if we
> could communicate via irc at some particular time. It would give a
> more clearer picture to construct our proposals as well. Thanks.
on a different project.
As we all know, it is very hard to estimate schedules for software
projects. Trying to manage such dependencies within the scope of GSoC
would complicate evaluation of individual work extremely difficult for
program admins and mentors.
Please keep it simple and base the proposals on existing functionality
only or provide clear contingency plans if you absolutely must rely on
someone else's work.
Cheers,
Burcin
Jason Suagee
Amit Jamadagni
I would like to mention that I am working on the backend of the project and Jason is working on the front end editor for the same topic, I was requesting him to present his views on what he would expect from the back end so as to make the working of the editor more complete in its functionality. I would also like to mention that we are working on completely independent ideas and have a pretty thin intersection.
@Jason are you on the gsoc channel or sagemath channel and how do I identify you ?? Thanks
Jason Suagee
Jason Suagee
Amit Jamadagni
Jason Suagee
Miguel Angel Marco
Miguel Angel Marco
Miguel Angel Marco
Jason Suagee
OK, I just submitted the proposal (I
realized that it was due in only a few hours).
Using the 3d coordinates of the vertices would be fine for exporting to the backend. It makes the job of programming the editor that much easier. Also, to reload a knot from a file all you would have to do is read back the coordinate data. For computation of invariants the backend probably will want a more simplified representation of the knot, but that is easy enough to compute within Sage given the coordinate data.
Your right, for inputing a knot from scratch it's good to have something that works like plink. This is really a different kind of thing than the rest of the project idea, which is 3D. I could implement a link drawing tool, but I'm wondering if we could just incorporate some of the plink code into Sage?
I looked at the graph_editor code. I did not know that you could just enter the following into a sage notebook input frame:
from sage.misc.html import html
html( INSERT ANY HTML HERE )
and what you get in the output frame is what you inserted. This will definitely help me to figure out the backend interface.
Miguel Angel Marco
Jason Suagee
Jason Suagee
Sorry to take so long to post back. I
have been going to conferences and haven't had much time to work on
anything the past 2 weeks.
Jason Grout recommended that we use the widget/comm idea from ipython to facilitate the communication between the front end and backend of the knot editor. He said that what was done in the past for the graph editor was a kludge (for non-native english speakers this is an expression for something which is kind of hacked together). I don't know if this is the direction that you would want to go? I could replicate the kludge idea or try this new method using the ipython notebook interface (or maybe the qtconsole, which I have not tried yet).
I have experimented some with the ipython notebook interface for sage (sage -ipython notebook). I can load some javascript into an output frame and get it to be evaluated, although I cannot as yet figure out how to sync what is going on in the output frame with the python backend. (That would be where the widget idea comes in I suppose.)
I have a question: My version of sage uses ipython 0.13, whereas ipython is now up to version 2.0, I think. Does the current source for sage use any version of ipython >= 1.0. There are no available examples that I could find of the use of widgets in ipython ver. < 1.0, and the module structure of ipython has changed from ver. < 1.0 to >= 1.0. The change in module structure is making experimentation more difficult.
I have to be honest, I feel like a fish out of water dealing with this part of the project. I can handle the algorithmic parts fine but this part of dealing with the backend/frontend communication might turn out to be pretty difficult. I have an associate/friend who is used to programming in javascript (among other things), and he offered to give me some pointers and provide a little help along the way. So I wouldn't totally be on my own.
Please let me know if there is still interest in this project going forward.
Jason Grout
>
> Sorry to take so long to post back. I have been going to conferences and
> haven't had much time to work on anything the past 2 weeks.
>
>
> Jason Grout recommended that we use the widget/comm idea from ipython to
> facilitate the communication between the front end and backend of the
> knot editor. He said that what was done in the past for the graph editor
> was a kludge (for non-native english speakers this is an expression for
> something which is kind of hacked together). I don't know if this is the
> direction that you would want to go? I could replicate the kludge idea
> or try this new method using the ipython notebook interface (or maybe
> the qtconsole, which I have not tried yet).
>
>
> I have experimented some with the ipython notebook interface for sage
> (sage -ipython notebook). I can load some javascript into an output
> frame and get it to be evaluated, although I cannot as yet figure out
> how to sync what is going on in the output frame with the python
> backend. (That would be where the widget idea comes in I suppose.)
>
>
> I have a question: My version of sage uses ipython 0.13, whereas ipython
> is now up to version 2.0, I think. Does the current source for sage use
> any version of ipython >= 1.0. There are no available examples that I
> could find of the use of widgets in ipython ver. < 1.0, and the module
> structure of ipython has changed from ver. < 1.0 to >= 1.0. The change
> in module structure is making experimentation more difficult.
>
(http://trac.sagemath.org/ticket/14713). You'd have to run a dev
version of Sage to get that.
I don't think it'd be very hard at all to upgrade to IPython 2.0 (which
is what you need for widgets). I'm running it on the Sage cell server
right now with (I think) no changes to Sage.
>
> I have to be honest, I feel like a fish out of water dealing with this
> part of the project. I can handle the algorithmic parts fine but this
> part of dealing with the backend/frontend communication might turn out
> to be pretty difficult. I have an associate/friend who is used to
> programming in javascript (among other things), and he offered to give
> me some pointers and provide a little help along the way. So I wouldn't
> totally be on my own.
communicate with Sage backends:
* sage notebook (e.g., *.sagenb.org): I don't know anyone actively
working on this. This is the hack I mentioned above.
* sage cell server: we piggy-backed on the IPython infrastructure and
messaging/widget system. I think it's a nice design and lends itself to
clear, simple communication.
* sage cloud: William's the one to talk about this...
* well, really I guess there's a fourth, and that is with standard
interacts.
Going forward, I'd say that one possible good route would be to get the
IPython widget/comm message system working in the cloud sage worksheets
(or a close approximation thereof) and use that. If that layer is
compatible with IPython, then the same widget will work from the IPython
notebook and the cell server too.
Thanks,
Jason
Jason Suagee
dev version of sage and got it working with ipython 2.0. I forgot how
long sage can take to compile!
One thing is that the sage extension has trouble loading with the
newer version of ipython.
if I run:
%load_ext sage.misc.sage_extension
I get an error that ends with
/home/jason/opt/sage-6.1.beta1/local/lib/python2.7/site-packages/sage/misc/sage_extension.py
in <module>()
257 # apparently we will have stateful transformations then.
258 # see also https://github.com/ipython/ipython/pull/2402>
--> 259 from IPython.core.inputsplitter import (transform_ipy_prompt,
transform_classic_prompt,
260 transform_help_end,
transform_escaped,
261
transform_assign_system, transform_assign_magic,
ImportError: cannot import name transform_ipy_prompt
I can send the full error report if you want.
What I noticed is that there might have been a name change from
ipython 0.xx to 2.0 (of transform_ipy_prompt,
transform_classic_prompt, etc..). I made some changes in the code in
the sage_extension.py file and it then loaded the extension, although
I'm not sure it's doing anything now because, for instance, 2^3
returns 1 and not 8.
I'll look into how to use the widgets later today after I finish teaching.