logoalt Hacker News

ww52004/01/20251 replyview on HN

At every round of the algorithm, all nodes with 0 in-degree (i.e. they are not depending on anyone) are collected as a dependence-free subset.

They serve as the root set to the rest of the graph for the current round. The depending nodes reached from root set have their in-degree decremented. When their in-degrees reach 0, they are added to the next root set.

I'm using double-buffering to maintain the current root set for processing and to collect the next root set for the next round, instead of using a queue as in Kahn's algorithm. At the end of the round, I simply swap the double-buffers. It's very efficient. When the next root set is empty, all nodes have been processed.


Replies

duped04/02/2025

Do you define "in degree" as the number of incoming edges from nodes that have not been visited/sorted yet?

I believe what you've implemented is equivalent to Kahn's algorithm. Your double buffer is the queue.

show 1 reply