# Determine whether a universal sink exists in a directed graph

Determine whether a universal sink exists in a directed graph. A universal sink is a vertex which has no edge emanating from it, and all other vertices have an edge towards the sink.

```Input :
v1 -> v2 (implies vertex 1 is connected to vertex 2)
v3 -> v2
v4 -> v2
v5 -> v2
v6 -> v2
Output :
Sink found at vertex 2

Input :
v1 -> v6
v2 -> v3
v2 -> v4
v4 -> v3
v5 -> v3
Output :
No Sink
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We try to eliminate n – 1 non-sink vertices in O(n) time and check the remaining vertex for the sink property.
To eliminate vertices, we check whether a particular index (A[i][j]) in the adjacency matrix is a 1 or a 0. If it is a 0, it means that the vertex corresponding to index j cannot be a sink. If the index is a 1, it means the vertex corresponding to i cannot be a sink. We keep increasing i and j in this fashion until either i or j exceeds the number of vertices.
Using this method allows us to carry out the universal sink test for only one vertex instead of all n vertices. Suppose we are left with only vertex i.
We now check for whether row i has only 0s and whether row j as only 1s except for A[i][i], which will be 0.

Illustration :

```v1 -> v2
v3 -> v2
v4 -> v2
v5 -> v2
v6 -> v2
We can visualize the adjacency matrix for
the above as follows:
0 1 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0
0 1 0 0 0 0
0 1 0 0 0 0 ```

We observe that vertex 2 does not have any emanating edge, and that every other vertex has an edge in vertex 2. At A[0][0] (A[i][j]), we encounter a 0, so we increment j and next
look at A[0][1]. Here we encounter a 1. So we have to increment i by 1. A[1][1] is 0, so we keep increasing j. We notice that A[1][2], A[1][3].. etc are all 0, so j will exceed the
number of vertices (6 in this example). We now check row i and column i for the sink property. Row i must be completely 0, and column i must be completely 1 except for the index A[i][i]

Second Example:

```v1 -> v6
v2 -> v3
v2 -> v4
v4 -> v3
v5 -> v3
We can visualize the adjacency matrix
for the above as follows:
0 0 0 0 0 1
0 0 1 1 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
```

In this example, we observer that in row 1, every element is 0 except for the last column. So we will increment j until we reach the 1. When we reach 1, we increment i as long as
the value of A[i][j] is 0. If i exceeds the number of vertices, it is not possible to have a sink, and in this case, i will exceed the number of vertices.

 `// Java program to find whether a universal sink ` `// exists in a directed graph ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `Graph ` `{ ` `    ``int` `vertices; ` `    ``int``[][] adjacency_matrix; ` ` `  `    ``// constructor to initialize number of vertices and ` `    ``// size of adjacency matrix ` `    ``public` `graph(``int` `vertices) ` `    ``{ ` `        ``this``.vertices = vertices; ` `        ``adjacency_matrix = ``new` `int``[vertices][vertices]; ` `    ``} ` ` `  `    ``public` `void` `insert(``int` `source, ``int` `destination) ` `    ``{ ` `        ``// make adjacency_matrix[i][j] = 1 if there is ` `        ``// an edge from i to j ` `        ``adjacency_matrix[destination-``1``] = ``1``; ` `    ``} ` ` `  `    ``public` `boolean` `issink(``int` `i) ` `    ``{ ` `        ``for` `(``int` `j = ``0` `; j < vertices ; j++) ` `        ``{ ` `            ``// if any element in the row i is 1, it means ` `            ``// that there is an edge emanating from the ` `            ``// vertex, which means it cannot be a sink ` `            ``if` `(adjacency_matrix[i][j] == ``1``) ` `                ``return` `false``; ` ` `  `            ``// if any element other than i in the column ` `            ``// i is 0, it means that there is no edge from ` `            ``// that vertex to the vertex we are testing ` `            ``// and hence it cannot be a sink ` `            ``if` `(adjacency_matrix[j][i] == ``0` `&& j != i) ` `                ``return` `false``; ` `        ``} ` `        ``//if none of the checks fails, return true ` `        ``return` `true``; ` `    ``} ` ` `  `    ``// we will eliminate n-1 non sink vertices so that ` `    ``// we have to check for only one vertex instead of ` `    ``// all n vertices ` `    ``public` `int` `eliminate() ` `    ``{ ` `        ``int` `i = ``0``, j = ``0``; ` `        ``while` `(i < vertices && j < vertices) ` `        ``{ ` `            ``// If the index is 1, increment the row we are ` `            ``// checking by 1 ` `            ``// else increment the column ` `            ``if` `(adjacency_matrix[i][j] == ``1``) ` `                ``i = i + ``1``; ` `            ``else` `                ``j = j + ``1``; ` ` `  `        ``} ` ` `  `        ``// If i exceeds the number of vertices, it ` `        ``// means that there is no valid vertex in ` `        ``// the given vertices that can be a sink ` `        ``if` `(i > vertices) ` `            ``return` `-``1``; ` `        ``else` `if` `(!issink(i)) ` `            ``return` `-``1``; ` `        ``else` `return` `i; ` `    ``} ` `} ` ` `  `public` `class` `Sink ` `{ ` `    ``public` `static` `void` `main(String[] args)``throws` `IOException ` `    ``{ ` `        ``int` `number_of_vertices = ``6``; ` `        ``int` `number_of_edges = ``5``; ` `        ``graph g = ``new` `graph(number_of_vertices); ` `        ``/* ` `        ``//input set 1 ` `        ``g.insert(1, 6); ` `        ``g.insert(2, 6); ` `        ``g.insert(3, 6); ` `        ``g.insert(4, 6); ` `        ``g.insert(5, 6); ` `        ``*/` `        ``//input set 2 ` `        ``g.insert(``1``, ``6``); ` `        ``g.insert(``2``, ``3``); ` `        ``g.insert(``2``, ``4``); ` `        ``g.insert(``4``, ``3``); ` `        ``g.insert(``5``, ``3``); ` ` `  `        ``int` `vertex = g.eliminate(); ` ` `  `        ``// returns 0 based indexing of vertex. returns ` `        ``// -1 if no sink exits. ` `        ``// returns the vertex number-1 if sink is found ` `        ``if` `(vertex >= ``0``) ` `            ``System.out.println(``"Sink found at vertex "` `                                     ``+ (vertex + ``1``)); ` `        ``else` `            ``System.out.println(``"No Sink"``); ` `    ``} ` `} `

Output:

```input set 1:
Sink found at vertex 6
input set 2:
No Sink
```

This program eliminates non-sink vertices in O(n) complexity and checks for the sink property in O(n) complexity.

You may also try The Celebrity Problem, which is an application of this concept

Graph Graph