davecom
commented
6 years ago It's okay. Thanks so much for catching this and following up. Thanks even more for adding a test.
Closed ferranpujolcamins closed 6 years ago
davecom
commented
6 years ago It's okay. Thanks so much for catching this and following up. Thanks even more for adding a test.
In https://github.com/davecom/SwiftGraph/pull/51#issuecomment-431965125 you were right! I introduced a bug when the graph has cycles. That commit was marking all the neighbours as visited when enqueueing them insted of when actually visiting them. This caused that vertices that are neighbours of a visited vertex could not be visited until unqueued. For example, on the triangle graph, the path found was always of lenght 1, when it should be of lenght 2.
I've added a test for this and reverted the commit. Sorry for introducing the bug.