search

emory-courses / dsa-java

Data Structures and Algorithms in Java
https://emory.gitbook.io/dsa-java/
42 stars 55 forks source link

[QZ#6] Edge case testing #167

Closed chenda2000 closed 3 years ago

chenda2000 commented 3 years ago

crop I looking at this graph right now, and my implementation for numberOfCycles() first finds the cycle (0,5,2,0), and then (2,4,3,2). But when it gets to the 3->0 edge, it can't find the cycle (0,3,2,0), as all the nodes in it are already visited.

I've tried many different ways to try to fix this, such as removing nodes from visited[] when backtracking, but I can't think of an implementation that doesn't overcount the cycles or requires rewriting the whole method.

Dr. Choi said in lecture that the implementation is supposed to be simple and just a modification of containsCycle(), so I was wondering if we're expected to be able to handle this case? Maybe I'm missing something but there seems to be no simple way to solve this?

alexbingqi commented 3 years ago

I encounter the same problem and I tried to change the condition. Yet, it always reports StackOverflow.

marvinquiet commented 3 years ago

Yes, in total there should be 3 circles. Instead of trying to find out if it is visited, maybe you can count the incoming and outcoming edges. Once you find a circle, either mark them or simply remove those edges from the graph, and then detect the next one. Once all the nodes are with either only incoming or outcoming edges, the algorithm is done

marvinquiet commented 3 years ago

But yeah, similar to my answer in #170, please directly consult Dr. Choi in class to make sure if the cases will be designed this complicated.

Shreya3554 commented 3 years ago

So in this example, would 4->2->5->0->2->3->4 be considered a cycle?

marvinquiet commented 3 years ago

According to Dr. Choi's answer in #166, I assume that this is just considered as two separate cycles.

chenda2000 commented 3 years ago

Answered on assignment page