CODEWITHSUNDEEP
graphcycledepth-first-search
Nekuromento
Nekuromento

Reputation: 2235

Removing false cycles in DFS-XOR cycle detection for undirected graphs algorithm results

I was implementing algorithms defined in this paper and I can't quite get the proposed way of removing false cycles from the results.

Quote from the paper: The method will find non-existing cycles in case there are no overlapping edges at all between the two cycles in base. This can be fixed by first applying AND on each two cycles in base.

At what moment should I apply AND?

Is there a more detailed explanation of removal of false-cyles in this algorithm?

Upvotes: 0

Views: 318

Answers (1)

Irit Katriel
Irit Katriel

Reputation: 3564

I think the intention is that just before computing the XOR of two cycles to obtain a new cycle, you check to make sure that they are not disjoint. This is because the XOR of two disjoint cycles is two disjoint cycles, and this is not what you wanted.

In fact, I think it is more efficient to combine the AND and the XOR stage - in order to compute the XOR you need to identify edges that belong to both cycles so as to exclude them. So just keep track of whether you threw away any edges, and if you didn't then you did not find a new cycle.

Upvotes: 1

Related Questions