Hacker News Reader

For traversing a DAG you probably still would to avoid exploring an exponential number of paths (consider a chain of diamonds [1]).

1: https://www.researchgate.net/figure/A-diamond-shaped-DAG_fig...

View on HN

But a diamond cannot occur in a Twitter-reply graph, right? It would require a Tweet to be able to reply to more than one tweet.

It can because the assumption is that we are crawling embedded links as well as native parents.

You can reply to one tweet while quote-retweeting another. Depending on how links are defined that could result in a diamond.

It’s a lot easier to just have a depth limit on such non-cyclic graphs than keep an in-memory list of previously seen nodes. its interesting for sure! but a much rarer edge-case imo

Reply on news.ycombinator.com