My wheel reinvention project is a web app that displays a network of Twitter threads, allowing to view them side by side, navigate quote-links and jumping to a random thread. It is built with 97% C++/GLSL, just because I'm not a fan of web technologies.
You can play with the app here: https://visa-viz.github.io/jam
I've been working on it for a few months. It started with me encountering a guy on Twitter who posts a lot of interesting threads and links related tweets to each other. It is a big maze and official apps make it hard to keep track of what is read and which paths haven't been explored, so it's easy to get lost. I figured it would be interesting to build a dedicated web tool to view these threads as a graph, and to do it with C++/wasm/WebGL to spice up the challenge. It was cool to not deal with arbitrary restrictions that DOM puts on the building blocks available and to see what it takes to build a UI from pixels.
In this jam I wanted to experiment with laying out the threads on the virtual space. Initially the layout was represented as a linear sequence - you start with one thread, clicking on a quote-link spawns the other thread in the next column, you can have as many columns as you want, but only one thread in each. The approach I wanted to try was to allow multiple threads per column, which sounds simple until you realize it's a whole graph layout problem: threads should not overlap, arrows should not intersect, their length should ideally be minimal, and a great-great-grandchild of one thread can push its 3nd cousin, affecting all the parents.
There are established projects that deal with graph layouting, like GraphViz and yEd, but both of them treat nodes like dimensionless objects - you can set the width and height, but the arrows will anyway try to connect the centers. In my case, threads are very vertical, and arrows should come and go to their very specific spots, which will impact the layout. So I decided to reinvent another wheel and roll out my own algorithm.
How it started:
How it went:
I started with working out an overall approach that covers all the cases. Optimizing the whole network at once would be computationally hard (that's why graph layouting software is slow), and I need something that can run in a click handler, so I decided to limit its shape to a tree and handle every level independently. Determining the shortest (in terms of least squares) configuration of arrows that avoids thread overlaps turned out to be known as a Quadratic Programming problem with linear constraints. I found a paper describing an algorithm for it and spent several days working out the matrix math for different cases, only to find out that some important details are not explained. I then discovered that there is a generic term for this sort of algorithm but the part I'm missing involves more math I'm not familiar with, which would exceed my math budget for the project. Morale: when you venture into a space you don't know, it can turn out to be more complex than you thought, and you won't be able to distinguish good directions from bad ones.
Around Saturday morning it occurred to me that there is a more intuitive way to look at this than shuffling matrices. For a given tree level, consider a parent node and child subtrees, with each subtree having a known height at every level. It is easy to place the first subtree (right in the optimal spot), for every next one it is easy to say whether its optimal spot is taken or not, and it is easy to glue the conflicting children together and optimize for the group, knowing there won't be a need to unglue them. Being able to imagine the threads at every step, it turned out to be much easier to code than faceless matrix math. Morale: a deep but unsuccessful attempt to solve a problem may still give you an intuition which will eventually help, but it's hard to predict in advance.
After integrating the new layout system into the main app, I discovered that many threads are longer than I thought. Putting two of them in a same column is likely to move things way up or way down, which makes the experience more janky. Wondering, how is this avoided in the actual products: through more initial brainstorming on the UX side, having good engineering expertise to make prototypes faster, or some other technology/magic.
Overall, this jam was quite an educational experience for me, and a good motivator to attack a hard problem. Thanks to the organizers and other participants!