Dark Mode

5,959 views

35 votes

A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq 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 $E_3$

- $(A[i][j] \ \&\& \ !A[j][i])$
- $(!A[i][j] \ \&\& \ A[j][i])$
- $(!A[i][j] \ \left | \right | A[j][i])$
- $(A[i][j] \ \left | \right | \ !A[j][i])$

Question is already bonkers for those who haven’t read the algorithm for finding universal sink before and then Gate professors also introduced the twist in the second part. It goes like this :

$(!A[i][j] \land A[j][i])$

But by changing the meaning of the flag variable , they’ve asked the opposite of it.

$(!A[i][j] \land A[j][i])$

But by changing the meaning of the flag variable , they’ve asked the opposite of it.

1

52 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 $E_2$, 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

$E_1: \ !A[i][j]$

and

$E_2: i = j$;

$E_1$ 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 $E_2$, 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, $E_3$ 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 $E_3$ must make flag = 0, if the found $i$ is not a sink. So, the condition should be:

$A[i][j] \ \left | \right |\ !A[j][i]$

So, **(D) is the answer**.

@Subbu. We can’t simply do $j++$.

This is because when the $while (j<n$ && $ \ !A[i][j])$ breaks, we update $i$ if the $if$ statement becomes true with $E2 : i = j$

Next time $j$ must start from $i+1$ and not random $j++$. This is why $j=i+1 $ is required.

0

12 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.

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.

7 votes

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

0

edited
Nov 28, 2017
by A_i_$_h

@srestha

in ur matrix rep ....A[4][4] should be 0 right ?

i = 0; do { j = i + 1; while ((j < n) && E1) j++; if (j < n) E2; } while (j < n); flag = 1;

lets take a 3 * 3 matrix representation

so i varies from 0 to 2

and j varies from 0 to 2

i=0 j =1 then incrementing j until less than n so at last i=0 and j=2

now if(j<n) E2;

E2 => i= j

now j is 2 which is assigned to i

again eneters do while and j =i+1 which is 2+1 =3

there is no index as 3 right?

i am suddenly getting confused because of E2 statement

whats wrong in my analysis

1