Get all GraphViz edges working properly in Cytoscape.js (eliminate need to fall back to straight-line Beziers)

[fedarko]

Bezier curves are really just a more specific form of splines. Right now we're reading the B-spline control points directly into Cytoscape.js, which seems to be working fairly well—but we could maybe (key word here is "maybe") get more accurate edges + reduce errors by drawing these edges more carefully.

See this, from one of the GraphViz developers—

For our purposes, a B-spline is a series of overlapping cubic Beziers with the property that the last point of one Bezier is the first point of the next, and that the lines determined by the last two points in one Bezier and first two points in the next are the same. So B-splines will always have 3*n + 1 points. To draw a spline, draw the cubic Bezier determined by the first 4 points, then take the last point and the next four points and draw that cubic Bezier. Continue until you run out of points.

For your example above, you just have 4 points, so just draw the single cubic Bezier determined by those four points.

There doesn't seem to be any way in Cytoscape.js for us to draw multiple bezier curves for a single edge. However (this might be silly), one workaround I thought of is:

• Draw the first bezier curve
• If we're out of points, we're done
• Else, create an invisible and hidden node at the end of that bezier curve and have the edge point to that node
• And then draw the next bezier curve from the invisible/hidden node (repeating the invisible node placement if necessary)

The issues here are:

• Edges might look strange and not-necessarily contiguous
• This might add a decent amount of overhead for large graphs

It's worth looking into sometime, I guess. Definitely not super-important, though.

[fedarko]

IMO, this is one of the major things I need to fix in the application. I'm not really sure what can be done within the confines of Cytoscape.js as is, but I could maybe hack its edge valdity testing/rendering stuff to make it more lenient (?). Either that, or -- as outlined above -- I'm converting edges from GraphViz to Cytoscape.js incorrectly, or at least in such a way that there is a resulting loss of precision that results in invalid edges.

[fedarko]

http://math.stackexchange.com/questions/417859/convert-a-b-spline-into-bezier-curves

Look into the mathematical specifications of how to do this (Boehm's Algorithm? see this), and see how my current code compares. Adjust code accordingly -- consider overhauling code entirely, honestly.

Although "drawing multiple beziers" might not be very doable within Cytoscape.js, as is? I'm not sure if Boehm's Algorithm provides a one-to-one (or something like that) conversion of B-spline control points to bezier control points, or if it requires (as Gansner says in the link from the first post in this thread) drawing multiple overlapping bezier curves. (I got a bit lost in the math while doing a cursory overview of the algorithm. take some time and figure it out.)

[fedarko]

Also: have to fix edges to/from child nodes in node groups now (that involve a node from outside the node group in question -- although edges between nodes in different node groups are also problematic currently). See #80 for details on this.

[fedarko]

Another concern: the edge-distances parameter -- how does GraphViz create control points? We should match that in Cytoscape.js, as closely as possible.

Also, we discard the first control point from every sequence of GraphViz control points. Why exactly do we do this...? I remember I had a good reason for it at one point a while ago, but it's lost on me now. (Including the first control point just results in bad-looking edges in cytoscape.js.)

[fedarko]

And -- if converting B-splines to bezier curves seems to be too much, then just use polyline/ortho splines in GraphViz and corresponding segments edges in Cytoscape.js.

[fedarko]

We should also pay closer attention to edge formats. Currently, we assume every edge position will have endp defined but startp not defined -- I don't know if this is always a good assumption (although it's worked fine for pretty much everything we've tried thus far). It might be due to our use of arrows in edge positioning -- maybe try experimenting with that and seeing how things go.

[fedarko]

Update to above comment -- now, the python code detects if startp/endp positions are present and ignores them accordingly. So we don't have to worry about that, at least.

[fedarko]

Consider this, maybe?

[fedarko]

^^yep, that ended up doing the trick :D

so thankful this issue got resolved. (although I feel a bit silly, since I didn't really do much on this front but sit back and realize later that they added a feature that accounted for it...)