You are reading content from Scuttlebutt
@Dominic %QRHIiYJqaqpY7P3cyEwM3LxTxmVjF0OvF7ABwayc4zo=.sha256
Re: %FOyO23xiO

Thoughts: I need an efficient way to process changes to the follow graph incrementally. The current code takes ~200 ms to traverse the graph. That's good if it's one time, but if you have to recalculate that on every follow that becomes very slow. If you do that just 5 times, it's blocked the CPU for 1 second.

Adding an edge is easy, because adding an edge only makes paths to other nodes shorter. But removing an edge (also adding a block) is harder.

Some observations: If you block or unfollow someone that you previously followed, some feeds may be further away now. But one thing we know for sure: feeds that were already closer than the blocked feed do not change - The shortest path to a node cannot go through a more distant node! So a block means we only need to recalculate more distant nodes.

Hmm, so we take feeds that the blocked feed follows, and check if their distance has changed. If they had another edge from a feed at a lower distance than the blocked feed, then we know that edge doesn't change. Otherwise, we remove that node?

Join Scuttlebutt now