y3

I added a select control that lets you switch between fixed width and radial layouts. It's nice to be able to easily compare.

This isn't a functional update, but I renamed "endeavors," the term I used for things the user is trying to do to "tasks". I wanted to avoid "task" initially because it sounds small, and the things could be really big like "Be satisfied with life".

"Endeavor," though, is long and sounds pretentious. This has bothered me for a long time, so I finally replaced all the uses of it in the code. Everything still works.

Things don't look any different, but I did get edge crossing counting in. It was quite a lot of code. Even implementing line intersection detection was more involved than I thought.

Here's my most recent commit message: ""Derive edges at end of layout process instead of maintaining them through the changes that happen to the nodes during the process. lexOrder gaps have been removed as a result, which is why all of the test fixtures have been updated."

To explain: My next step was going to be to do node position swapping to minimize edge crossings, but I realized that only works if the layers are what this book calls "proper" — meaning that no edge goes crosses a layer. That is, edges can go from layer 2 to layer 3, but not from layer 2 to layer 4.

I do not have that.

To have that, I need to work out how to insert dummy nodes. So, if I need to represent a connection between a node in layer 2 and a node in layer 4, I put a dummy node in layer 3, then make an edge from layer 2 to layer 3 and another one from layer 3 to layer 4.

The way I wrote things, nodes and edges are created early in the process and update in the various parts of the layout algorithm. The dummy node process is particularly destructive to edges. It's a lot of code.

So, I refactored to not have any formal edge objects until the very end of the layout process so that I don't have to maintain them. (Edges already exist implicitly via node members that say which other nodes point at them.) I was able to delete a bunch of code this way.

My function for finding the median node among a node's sources/ancestors assumed they were sorted, which they often weren't. That was used to set the node's position to the source nodes' median's position.

On top of that, the function that scaled the positions up for actual display were doing what I can sum up as "full justify", so the positions set weren't respected, and nodes appeared well away from their sources' median x-position.

All this took a while to figure out.

I started to work on adjacent node swapping to reduce edge crossings in the graph. I implemented the first part, which is positioning (on the x-axis) each node at the median of the positions of nodes pointing at it from previous layers.

That's when I noticed things still looked messed up and that some nodes were pointing to nodes that were in the same vertical layer. I reread the book to make sure that's not supposed to happen.

Then, I wrote a test to confirm that it was happening:

  for (
    let i = 0;
    i <= layeredNodesResult[layeredNodesResult.length - 1].layer;
    ++i
  ) {
    let layerNodes = layeredNodesResult.filter((e) => e.layer === i);
    // console.log('Layer', i, layerNodes);
    t.ok(
      layerNodes.every((node) =>
        layerNodes.every(
          (otherNode) =>
            !otherNode.nodesPointingAtThisNode.includes(node.endeavor.id)
        )
      ),
      `Layer ${i} does not have nodes pointing at each other.`
    );
  }

And yes, it is happening. So, I have to step back and see what I did wrong in the layering part of the algorithm instead moving forward with edge crossing reduction.

For edge crossing reduction, I read about algorithms that swap adjacent nodes to progressively reduce edge crossings. Then, I read about a way of doing it with integer programming, which I did not get at all. To my relief, the section after that in the book said that people usually use adjacent exchange, so hopefully, that works out for me.

Here's where I'll post about the development of the Why Why Why app.