GATE IT 2005 | Question: 84a

Question

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 expressions for $E_1$ and $E_2$

• A. $E_1 : A[i][j]$ and $E_2 : i = j$;
• B. $E_1 :\ !A[i][j]$ and $E_2  : i = j + 1$;
• C. $E_1:\ !A[i][j]$ and $E_2 : i = j$;
• D. $E_1 : A[i][j]$ and $E_2 : i = j + 1$;

Comments

can anybody elaborate this with the helpof diagram?????????????????/

---

vertex i is the sink in this graph

---

@Shaik Masthan sir i am facing difficulty to questions of algorithm design how can one get the intutition that what particular code is doing ..  is there any resource to understand these things ? coz some times they ask to fill a blank which doesn't click to me.. so what should i do..

---

These questions are tricky and time consuming. Initially it will difficult to get the answer in the blank part.

For understanding purpose, you write your own code for the answer, after that compare with the code given in the question. By doing such things, slowly you will learn.

---

Here we need to identify sink vertex.

Sink Vertex : Vertex whose in-degree is V-1 and and out-degree is 0.

so in adjacency matrix we need to find a row which is completely 0 and its respective column has (V-1) 1's.

---

Check this out , hope it helps .

Answer 1

If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one column and all 0's (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 doesn't 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 for 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$. 

So, answer is (C)

For $E_3$,  https://gateoverflow.in/3857/gate2005-it_84b

Comments

more discussion https://gateoverflow.in/217655/%23algorithms-gate-2005-question-self-doubt

---

@Arjun sir .. Please change E1:A[i][j] to  E1: !A[i][j]  in your answer.

 

---

hard to understand

Answer 2

We are given a directed graph represented by an $ n \times n $ adjacency matrix $ A $, where $ A[i][j] = 1 $ if there is an edge from vertex $ i $ to vertex $ j $, and $ 0 $ otherwise. A sink is a vertex $ i $ such that:

• $ A[i][j] = 0 $ for all $ j \ne i $ (no outgoing edges), and  
• $ A[j][i] = 1 $ for all $ j \ne i $ (all other vertices have an edge to $ i $).

The algorithm first identifies a candidate sink using a loop with two expressions $ E_1 $ and $ E_2 $, then verifies whether the candidate satisfies the sink conditions.

Determining $ E_1 $ and $ E_2 $

The outer loop maintains a candidate vertex $ i $. The inner loop scans vertices $ j > i $ to check whether $ i $ has any outgoing edge. If $ A[i][j] = 1 $ for some $ j $, then $ i $ cannot be a sink, and we must move to a new candidate.

The inner loop is:

j = i + 1;  
while ((j < n) && E1) j++;

This loop should continue as long as vertex $ i $ has no edge to $ j $. Therefore, $ E_1 $ must be true when $ A[i][j] = 0 $, i.e.,

$ E_1 : \texttt{!A[i][j]} $

If the loop terminates with $ j < n $, it means $ A[i][j] = 1 $, so $ i $ has an outgoing edge and is disqualified. In this case, we set the new candidate to $ j $, because any vertex between the old $ i $ and $ j $ cannot be a sink. Thus,

$ E_2 : \texttt{i = j} $

Example with Adjacency Matrix

Consider $ n = 4 $ and the following adjacency matrix:

$$
\begin{array}{c|cccc}
 & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 \\
2 & 0 & 0 & 0 & 0 \\
3 & 1 & 1 & 1 & 0 \\
\end{array}
$$

Vertex $ 2 $ has no outgoing edges and receives edges from all others, so it is a sink.

Algorithm steps:

• Start with $ i = 0 $
• $ j = 1 $: $ A[0][1] = 0 $ → $ E_1 $ true → $ j = 2 $
• $ A[0][2] = 1 $ → $ E_1 $ false → exit while
• Since $ j = 2 < 4 $, execute $ E_2 $: set $ i = 2 $
• Next iteration: $ j = 3 $, $ A[2][3] = 0 $ → $ j $ increments to $ 4 $
• Loop ends; candidate is $ i = 2 $
• Verification confirms vertex $ 2 $ is a sink

This confirms the correctness of $ E_1 = \texttt{!A[i][j]} $ and $ E_2 = \texttt{i = j} $.

$$
\boxed{\text{C. } E_1 : \texttt{!A[i][j]} \text{ and } E_2 : \texttt{i = j}}
$$

Answer 3

SINK

A vertex , that is maximum (in analogy of Lattice ) i.e. every other vertex has a directed edge to that vertex .(x,i) : For every x belongs to V & x!=i  , (x ,i) is a directed edge .

---

What are potential sink:

 (i)  No outgoing edge from that vertex , this means ,in  adjecency matrix  row corresponding to sink is all zero .

(ii) Every other vertex should be connected to that vertex, this means column with respect to that vertex should be all 1 except diagonal  (no self loop ).

---

Approach used in question :

  we will be checking row wise like A[0][1]->A[0][2]->A[0][3].....
and check for zeros (potential sink ).
If we find 1 in between we will move to next row (coz previous row cannot be sink )
at the end we will be in row that is a potential sink .
Now for confirmation we will be checking  column w.r.t that vertex , which we have just found out to be potential sink .
this could be confirmed by checking col and row of that particular vertex together , both should be different ( diagonal skipped ) i.e A[i][j] != A[j][i] given that i!=j.

At the end we will be having sink .

---

E1 : !A[i][j]   this is false when A[i][j] = 1 , means , there is edge from that ' i th vertex ' cannot be sink .
E2 : i=j  skip entire row and move to next row . ( remember we initialised j=i+1)

E3: Final confirmation check . that row and column of the potential sink vertex is not same.

---

Hope this made somewhat easier to understand .

Comments

Nice explanation :)

Answer 4

 

For better vizualization

Comments

Do you have solution for this one? : https://gateoverflow.in/2355/gate-cse-2010-question-50

 

Answer 5

(Please refer the below text for explaination and the image for only the graph and adj Matrix)

* In The First Do-while loop , the while loop will excute till  ( j < n && E1) . Here n = 3 , j = 1 initally . The loop will execute for this graph till j = 2 [ at the next iteration j = 3 , and j < n is not satified] and hence increament j to 3 .(dry run)

 Since , we are focusing on E1 and E2, so , this is checking if the current node might be the sink or not . Hence , here 0 is the sink node from our graph, so no issue , and the loop will execute smoothly 

Now , If I change A[0][2] to 1 instead of 0 , then the do-while loop will fail when j = 2 and the j is increamented to only 1 (dry run for this graph) .

Hence , now 0 is not a sink node , and now , we should better start looping for next 'i' , so i should be 1 , So E2 : i = j ( as j was 1) .  

.