aysylu/loom — pull request #38 by gshopov (2014-06-28 17:45:10+00:00)
Title: Pre traverse fix

Hi!

After reading the code of pre-traverse i thought that there was a problem and i think was able to find an example that proves it.

The problem i saw was that after visiting a node the algorithms was marking all of its successors as visited(it put them in the seen set), which is common for BFS but not DFS. Therefore if we take that example graph:

:a
/ | \
v v v
:e :b :c
| ^
| /
| /
| /
| /
|/
v
:d

and start the traversal from :a, what the algorithm will do is actually:

1) visit :a and mark :e, :b, and :c as visited
2) visit :e
3) visit :d
4) try visiting :c but its already in the seen set, so its visited
5) backtrack to :a
6) visit :b
7) visit :c

So it produces the result (:a :e :d :b :c) which is incorrect.

I chose the names of the vertices specifically for this example in order to force the algorithm to go through the branches in this exact order, otherwise it could just go through the branch from :e, go to :d, backtrack to
:a and then choose :c and then :b. In that case the result is (:a :e :d :c :b) which is correct but the :c vertex was not visited when it had to be.