davecom / SwiftGraph

A Graph Data Structure in Pure Swift
Apache License 2.0
758 stars 80 forks source link

Dfs improvement #56

Closed ferranpujolcamins closed 6 years ago

ferranpujolcamins commented 6 years ago

This change dramatically improves the performance of dfs on dense graphs. I've also added some more performance tests.

On the Dfs we can't mark as visited a node until we pop it from the stack (unlike Bfs). This means that we potentially add a node to the stack several times until the first time we pop it.

Before this PR: For each time we pop a vertex v from the stack, we push its un-visited neighbors on the stack. For the first time we visit v this is fine, but on the following times, we will be pushing vertices that are already pushed on the stack. Those vertices, in turn, have also been pushed twice or more on the stack, so the same problem happens for them.

After this PR: We don't push to the stack the neighbors of vertices that have already been visited.

Notes: This is the reason why #55 improved performance over master dramatically on the complete graph dfs test: I've also introduced this improvement there without noticing.

As food for thought about the discussion on #55: notice that this improvement is implemented both in the goalTest: and toIndex: versions of the dfs, but I could only add a unit test on the goalTest:version. The toIndex: version does not allow to inject anything that gets called over all the visited vertices. Both versions share 95% of code, but one of them cannot be tested on this behaviour. On the other hand, modifying the code to make it testable introduces performance degradation. Unsettling...

ferranpujolcamins commented 6 years ago

Note As you see, now the code looks like the example on wikipedia.

Of course this is not a proof of correctness. But it gives me some confidence ;)

davecom commented 6 years ago

Thank you; I think with the tests you implemented we can be pretty sure this is safe!