GridTree DevLog 014: Delete Complete!

I’m going to make an effort to be less verbose, but write more frequently!

I’m at an interesting stage of my research, where I have more freedom to focus on the problems that matter to me, but still have to channel my thinking to those elements which will create forward progress in my degree. This became important during the last couple of weeks, when in designing a solution to the current problem, I discovered better potential solutions to my entire insert functionality as well. My insertion code is a confusing recursive mess, and needs redone—but I can’t justify doing so quite yet. On the other hand, a little diverted time confirmed that my hypothetical improvement should work, which could very well be a prime feature of a second publication, after the initial algorithms are published. But messy algorithms are difficult to explain, so I’ve been sort of tweaking as I continue the current implementations, to try to clean it up.

If you read any of my last post, you might remember that I had nearly completed the Delete functionality in my GridTree prototype, and that the final stage is called collapse, where vacated space is reclaimed by moving surrounding nodes into it. This sounds simple, but defining algorithmically how to do this kind of shape packing, and not move things around too terribly much, is not straightforward.

The simple concept of the algorithm is this:

• Identify neighbors of the space to be collapsed, and put them in a queue.

• One at a time, pull one off of the queue, and see if it can move in a useful direction.

• If it can move, move it, and identify the neighbors of the spaces it vacates; put these on the queue.

• Keep doing this until the queue is empty, then clean up by trimming and collapsing any vacated areas.

This has some major complexities. For example, I have to carefully constrain their movement directions to be decreasing their distance to their parent, or I end up with infinite loops. (While not always optimal, this gives a simple enough rule that guarantees it will converge and not loop infinitely. And it WILL loop infinitely if I don’t. I tried.) I also should call the trim function on any spaces that get vacated by anything that moves, to clean them up. These extra steps sort of create an explosion of complexity, because trim can call collapse at higher levels of the tree—but this is to be expected, and actually is still within the complexity bounds I need. I think... Anyhow, in practice this works well enough.

But, this created a conundrum for me—a very similar algorithm could be used to push out, as to collapse in, providing a tidy matching pair of algorithms for both delete and insert, with a much easier to explain solution, even if the complexity bounds might be more difficult to prove. I didn’t want to use the new algorithm design on one but not the other; they should either both be updated, or neither.

I hummed and hawed over this conundrum for a while, tinkering, and debugging. One of the first things I did is write some new tree generator code to show evolving trees. No longer limited to insertion, I could finally make a generator which would add nodes up to a point, delete a random node or branch, and repeat! This creates a lovely visual of a continuously evolving tree.

And I realized, that even without collapsing at all, the tree is not nearly as full of awkward empty space as I thought it would be. I could actually simply make my first publication without the complex collapse function at all, and still have it be a complete implementation. Of course, I still have to implement move, but that should be relatively straightforward. A second publication could present the improvements, and measure the memory cost of not collapsing and the speed cost of collapsing.

I was chewing on these thoughts as I finalized the collapse function and got it working. It WORKS. And, lo and behold, it’s not too slow to be usable. Branch deletions are uncommon, so I can definitely collapse on deletion. Even collapsing on insertion works (in the space behind anything that gets pushed apart), though a quick test appears to show around 30% slowdown (ouch). So, it’s a little up in the air whether I will have collapse enabled for insertion by default or not.

Getting collapse to work on insertion was tricky, by the way. I needed to make it work, at least to see how inefficient my collapse algorithm was, but it meant going into the guts of my old insert code and fixing some of my previous mess. Since I probably need to do that to publish code anyway, or even just sensible algorithms, this was good.

I am eager to eventually try the new idea I have for insert, though I’m leery of the time cost it will have. In theory it should make much tidier trees. However, it is not priority #1, the move operation is.

Speaking of which, I’m already nearly done writing the code for the move operation, but don’t have anything working to show yet. The ability to move branches is, of course, needed for a complete implementation, so the GridTree can be used as a dynamic data structure, but, you see, I’m doing more than that. I’m working to make it so that you can specify a precise location—this will be instrumental in graphical interfaces, when a user wants to drag a branch to manually relocate it, not only under a different parent node, but within the same node. I see this as an eventual organizational necessity for my intended target applications for GridTrees.

I wanted to give you all a quick life update! Last summer I met Lily, and she and I were married in the Kansas City Temple in November. We are now expecting two little twin girls in October, and we are very excited! This also means I will be quite busy this fall, being a new dad. Nevertheless, I’ll keep working on my degree, and hopefully that means you will all still get occasional updates.

By the way, if you know of any computer scientists who might be intrigued by my work, please feel free to help me network with them by passing my Substack info along :)

Thank you to all of you who actually read my crazy writings, I genuinely appreciate you!

Share Links Labs Development Log