01 December 2008

Strongly connected components, idiot

I'm an idiot. The "proof" I gave for my SCC "algorithm" is wrong because DFS does not recursively explore all reachable unseen nodes: only unseen nodes reachable only thru unseen nodes. Sometimes I amaze even myself with the kind of mistakes I can make. I should have gotten used to it by now, right? Remember: Whenever you have a result that is too good to be true then it is too good to be true; you are better off trying to break it than convincing yourself that it works. Great! Now I'm talking to myself.

edit: A counter-example is scc({1:[2,3], 2:[1], 3:[]}). There should be two SCCs, not one as my code says. And, yes, I will continue with part 2 in which I'll describe Tarjan's algorithm. Hopefully his is better than mine :P.

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.