Circularized semilinear layout

[fedarko]

One of the slight downsides of using a semilinear layout is that some types of assembly graph components (e.g. almost-finished circular bacterial chromosomes) could be best represented as a circle, depending on whom you ask. See, for example, Figure 4a in the metaFlye paper:

Representing this chromosome linearly would work, but it necessitates the presence of at least one long "back edge" in the graph visualization.

Given a DOT layout that is oriented from left --> right (using standard Cartesian coordinates), representing a graph that is mostly linear but still has an overall circular structure, we should be able to convert the positions of nodes within this layout to be kinda like a circle.

We can do this by mapping nodes' Cartesian coordinates to polar coordinates (not converting: we'd be scaling the coordinates to fit on a "circle"), and then converting these polar coordinates back to Cartesian.

1. Map nodes' x-coordinates to theta values, and nodes' y-coordinates to r values (there will be some weird details that come up, but the broad idea here is pretty straightforward). This will yield a circular representation of a linear graph.

   • There are a few parameters here -- e.g. we could adjust where on the circle (i.e. in the range [0, 2pi]) we "start" the graph, we'd probably need to mess around with radius scaling in the case of really "tall" parts of the graph, etc.

2. Convert these (r, theta) values from polar to Cartesian coordinates (using x = rcos(theta), y = rsin(theta)). The graph can then be drawn as normal.

Sticking points:

• We could try converting edge control points, also, but I suspect that would look gross and be too much work for its own good. It'd probably be best to just represent edges here as simple bezier curves in Cytoscape.js -- also, since one of the goals of this is removing back edges, ignoring control points would account for that.
• As I remember (like, years ago when I had dynamic rotation as a setting in MetagenomeScope), the custom polygons used for representing contig shapes could look weird when rotated.
  • This is partly due to how I've been defining polygons: see shape-polygon-points -- when we represent a node as something that hits the corner of the 2x2 "box", rotating this node by anything that isn't a multiple of 90 degrees forces the node to extend past the boundary of the box, resulting in weirdly truncated shapes.
  • I think it should be possible to fix this by limiting contigs to a smaller subset of the box's area such that all rotations stay within the box; however, not sure if this will cause extra problems with clicking on the nodes, etc.
  • Worst case scenario, we can just use the same rotation for all nodes, or approximate things (e.g. declare 4, 8, 16, etc. distinct polygon classes, and then pick the best fit based on the node's theta value in polar coordinates).
• This might look really ugly with node groups -- not sure. Worst case scenario, we can represent node groups as just lines (making the interior of the boxes transparent), change child nodes' borders, etc.