Aptitude Overflow
+8 votes
949 views

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.

 

i = 0;
do {
    j = i + 1;
    while ((j < n) && E1) j++;
    if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists") ;
else printf ("Sink does not exist");

Choose the correct expression for E3

  1. (A[i][j] && !A[j][i])
  2. (!A[i][j] && A[j][i])
  3. (!A[i][j] | |  A[j][i])
  4. (A[i][j] | | !A[j][i])
asked in Algorithms by (21.2k points) 120 154 154 | 949 views

5 Answers

+19 votes
Best answer

If there is a sink in the graph, the adjacency matrix will contain all 1s (except diagonal) in one column and all 0s (except diagonal) in the corresponding row of that vertex. The given algorithm is a smart way of doing this as it finds the sink in $O(n)$ time complexity.

The first part of the code, is finding if there is any vertex which does not have any outgoing edge to any vertex coming after it in adjacency matrix. The smart part of the code is E2, which makes rows skip when there is no edge from i to it, making it impossible them to form a sink. This is done through

E1: !A[i][j]
and
E2: i = j;

E1 makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If A[i][j] becomes 1, i can no longer be a sink, similarly all previous j can also not be a sink (as there was no edge from i to them and a sink requires an edge from all other vertices). Now, the next potential candidate for sink is j. So, in E2, we must make i = j.

Now, the loop breaks when we found a potential sink- that is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix. So, if the column in which this vertex comes is all 1s and the row is all 0s (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, E3 is checking this condition. 

But in the code $\text{flag}$ is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present.  So, the condition in E3  must make flag = 0, if the found $i$ is not a sink. So, the condition should be: 

A[i][j] || !A[j][i]

So, (D) is the answer.

answered by (319k points) 39 55 89
edited by
Thank you sir :)
Everything is perfect and nicely illustrated.
Please also add one more line to tell us why in 3rd line we are writing  "j=i+1", why not j is incremented sequentially ? (at each iteration +1)
why not and logical operator
+5 votes
Everything is well explained no need to add something new but at final answer for E3 is wrong somehow.

Lemme correct it with the concept of

"Logics"

A vertex would be sink iff there is an edge from every vertex to this vertex and there are not a single edge from this vertex to some other.

Now at E3 we have to tell condition for a non-sink vertex..

!(p and q) equals !p or !q

A vertex i would not be sink iff either there is an edge from it to some other vertex or there is atleast one vertex that dont have any edge to i.

So i mean answer is D.
answered by (559 points)
+1 vote
If you have no idea of the algorithm, a better way to do this during GATE would be to assume a sink (say vertex 2) and see which of the given cases works.
answered by (319k points) 39 55 89
+1 vote

According the definition given to sink

 

Now according to the definition we are checking the program. So, there must be incoming edge for the vertex of sink but those are not diagonal or not outgoing edges.

Now for i=0,j=1 , we check the condition if A[j][i] exists i.e !A[i][j] exists then take that vertex

like that i=0,j=2

            i=0,j=3

Now, if()  condition satisfies we make i=1 and j=2 (so here we are ignoring i=1 and j=1, means diagonal part)

 

Same thing happens while i=1,j=2

                                        i=1,j=3

and if() condition checking.(as scope of j is local inside while loop , so post increment not change j value of outside while loop) makes i=2

...............

like that we can say E1: !A[i][j] and E2 : i = j;

------------------------------------------------------------------------------------------------------------------------------------

Now, flag initially 1 , we got a upper triangular matrix from the above code.

But according to the definition we have to get a lower triangular matrix

So, to change upper triangular matrix to lower triangular matrix

E3 will be B)(A[i][j] && !A[j][i]) where flag=0

                                 

answered by (64.9k points) 5 15 35
edited by
According to your graph a[4][4] = 0
Any easy way to solve?
I really could not understand what are you trying to do?

i=0;j=1,2,3...

then from where i=1;j=1,2,3..

It would be great if you could explain :)
0 votes
Xpln
answered by (11 points)

Related questions

2,704 questions
980 answers
386 comments
31,351 users