In problem -Is Graph 2 exists -16.4 - Is check for Black vertex valid?

#1

In Problem 16.4 's solution, we assume a connected undirected graph. So, every node is reachable from any node. The test is to see if there is at least one cycle. I am not clear on how it is possible to encounter a ‘black’ node in the neighbors list, without having seen that cycle before in the check for ‘grey’ node. Are we to check for ‘grey’ instead? Even that is taken care of by the exit criteria of the recursion, no?

I feel this if is not needed:
if(next != pre && next->color != GraphVertex::black)

Please correct me, if I am not seeing the light!

0 Likes
#2

This is rephrased to deadlock detection problem since 2nd edition. You can find the updated solution at http://elementsofprogramminginterviews.com/solutions/cpp/2_exists.cc

0 Likes
#3

I do not understand. Is this a new question altogether or the same problem? Could you please explain the difference from the version 1.3.3 I own. Or point me to the diff on the latest for the question? Thank you!

0 Likes
#4

It is the same problem but we change the problem description to deadlock detection problem. The difference between 1.3.3 to the latest version is quite a few as we change and improve a lot since then.

0 Likes