undefined | Better HN

0 pointskps2y ago0 comments

Detecting a cycle in a directed graph is useful (in certain domains I've worked in), but doesn't have a cute trick answer.

[Edit: I in mind ‘Detecting the cycles’ rather than ‘Detecting a cycle’ but wrote the wrong thing. Mea culpa.]

Your actual job will be more like implementing a maximally performant directed graph in safe Rust. (Not really. It won't be that interesting.)

0 comments

addaon2y ago

> Detecting a cycle in a directed graph is useful (in certain domains I've worked in), but doesn't have a cute trick answer.

Doesn't the standard cute trick answer for a linked list (tortoise and hare) work fine? Do two parallel breadth-first traversals of the graph starting at the root node, one at twice the speed of the other. (If there's multiple root nodes, introduce a unique super-root that points to the roots.) If there's at least one cyclic path, both iterations will enter the same cyclic path because iteration order is the same, at which point it reduces to the linked list problem.

kpsOP2y ago

Yes, I phrased my comment incorrectly; I had in mind identifying (all) the cycles, and that for a linked list they're the same thing. For a DAG it doesn't generalize because you can't find more cycles without storage to exclude the earlier ones.

addaon2y ago

Fair enough. I imagine a simple (but O(cycles) space, not O(1)) way to do this is to still tortoise-and-hare, and on detecting a cycle, break the link behind you (by recording it in a table) and continue the BFS. If O(cycles) = O(n) this isn't terribly interesting compared to other approaches, but if O(cycles) < O(n) it might be helpful.

1 more reply

Freire_Herval2y ago

if you can mutate the graph and mark a node as traversed that's the easiest way. If you can't then save the addresses to a hash set. Both are extra memory but you don't have to deal with "parallel BFS," which honestly is just over complicated imo.

With "parallel bfs" comparing "layers" of traversal has runtime cost that effects the big oh so I think the above solution is better overall even though it feels cheap.

addaon2y ago

But the whole point of the "cute solution" is to solve with O(1) memory; if you're willing to allow O(n) then the linked list also admits more sane solutions.

I'm not sure what you mean by comparing "layers" of traversal. Tortoise and hare is about provide a termination condition in the case that a cycle exists. In the case that there's no cycle, every algorithm must inspect each node, so is O(n). In both the linked list and the DAG case, if there is at least one cycle, (a) both pointers will enter it in at most O(n) time, and they will match in at most O(n) additional time, so this stays big-oh optimal.

3 more replies

j / k navigate · click thread line to collapse

0 comments

addaon2y ago

> Detecting a cycle in a directed graph is useful (in certain domains I've worked in), but doesn't have a cute trick answer.

kpsOP2y ago

addaon2y ago

1 more reply

Freire_Herval2y ago

With "parallel bfs" comparing "layers" of traversal has runtime cost that effects the big oh so I think the above solution is better overall even though it feels cheap.

addaon2y ago

But the whole point of the "cute solution" is to solve with O(1) memory; if you're willing to allow O(n) then the linked list also admits more sane solutions.

3 more replies

j / k navigate · click thread line to collapse