elementary-circuits-directed-graph icon indicating copy to clipboard operation
elementary-circuits-directed-graph copied to clipboard

Some circuits missing - doesn't unblock as stack unwinds

Open asteadman opened this issue 5 months ago • 0 comments

Compared to networkx's simple_cycles, which is supposed to implement the same algorithm, the results are different.

In particular, consider this adjacency: [ [ 3, 4, 1, 5 ], [ 2, 5 ], [ 3, 1 ], [ 2, 0 ], [ 0, 1 ], [ 1 ] ]

This code: output: [ [ 0, 3, 0 ], [ 0, 4, 0 ], [ 1, 2, 1 ], [ 1, 5, 1 ], [ 2, 3, 2 ] ]

NetworkX: output: [[0, 1, 2, 3], [0, 3], [0, 4], [0, 4, 1, 2, 3], [0, 5, 1, 2, 3], [1, 2], [1, 5], [2, 3]]

In particular [0, 1, 2, 3], [0, 4, 1, 2, 3], and [0, 5, 1, 2, 3] are missing.

After some debugging, it appears to be that when circuit(v) unwinds - it doesn't unblock nodes as it pops them off the stack. I've switched stack.pop() to unblock(stack.pop()), and the missing circuits start appearing. I'm not 100% if this is the proper fix or not, but it appears to be working for my use case.

asteadman avatar Sep 27 '24 11:09 asteadman