Determine whether a universal sink exists in a directed graph

Last Updated : 20 Feb, 2023

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

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]

Adjacency Matrix

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.

Adjacency Matrix

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 100;
 
class Graph {
    int vertices;
    int adjacency_matrix[MAX][MAX];
 
public:
    Graph(int vertices)
    {
        this->vertices = vertices;
        memset(adjacency_matrix, 0,
               sizeof(adjacency_matrix));
    }
    void insert(int source, int destination)
    {
        adjacency_matrix[destination - 1] = 1;
    }
 
    bool is_sink(int i)
    {
        for (int j = 0; j < vertices; j++) {
            if (adjacency_matrix[i][j] == 1)
                return false;
            if (adjacency_matrix[j][i] == 0 && j != i)
                return false;
        }
        return true;
    }
 
    int eliminate()
    {
        int i = 0, j = 0;
        while (i < vertices && j < vertices) {
            if (adjacency_matrix[i][j] == 1)
                i = i + 1;
            else
                j = j + 1;
        }
 
        if (i > vertices)
            return -1;
        else if (!is_sink(i))
            return -1;
        else
            return i;
    }
};
 
int main()
{
    int number_of_vertices = 6, number_of_edges = 5;
    Graph g(number_of_vertices);
    g.insert(1, 6);
    g.insert(2, 3);
    g.insert(2, 4);
    g.insert(4, 3);
    g.insert(5, 3);
 
    int vertex = g.eliminate();
 
    if (vertex >= 0)
        cout << "Sink found at vertex " << (vertex + 1)
             << endl;
    else
        cout << "No Sink" << endl;
 
    return 0;
}
//This Code is Contributed by chinmaya121221

Java

// 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");
    }
}

Python3

# Python3 program to find whether a 
# universal sink exists in a directed graph
class Graph:
 
    # constructor to initialize number of 
    # vertices and size of adjacency matrix
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjacency_matrix = [[0 for i in range(vertices)]
                                    for j in range(vertices)]
 
    def insert(self, s, destination):
 
        # make adjacency_matrix[i][j] = 1 
        # if there is an edge from i to j
        self.adjacency_matrix[s - 1][destination - 1] = 1
 
    def issink(self, i):
        for j in range(self.vertices):
 
            # 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 self.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 self.adjacency_matrix[j][i] == 0 and 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
    def eliminate(self):
        i = 0
        j = 0
        while i < self.vertices and j < self.vertices:
 
            # If the index is 1, increment the row 
            # we are checking by 1
            # else increment the column
            if self.adjacency_matrix[i][j] == 1:
                i += 1
            else:
                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 > self.vertices:
            return -1
        elif self.issink(i) is False:
            return -1
        else:
            return i
 
# Driver Code
if __name__ == "__main__":
 
    number_of_vertices = 6
    number_of_edges = 5
    g = 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)
 
    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:
        print("Sink found at vertex %d" % (vertex + 1))
    else:
        print("No Sink")
 
# This code is contributed by
# sanjeev2552

C#

// C# program to find whether a universal sink 
// exists in a directed graph 
using System;
using System.Collections.Generic;
 
class graph 
{ 
    int vertices, itr; 
    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 = 1; 
    } 
 
    public bool 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)
    { 
        int number_of_vertices = 6; 
        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) 
            Console.WriteLine("Sink found at vertex "
                                    + (vertex + 1)); 
        else
            Console.WriteLine("No Sink"); 
    } 
} 
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program to find whether a
// universal sink exists in a directed graph
class Graph{
 
    // constructor to initialize number of
    // vertices and size of adjacency matrix
    constructor(vertices){
        this.vertices = vertices
        this.adjacency_matrix = new Array(this.vertices).fill(0).map(()=>new Array(this.vertices).fill(0))
    }
 
    insert(s, destination){
 
        // make adjacency_matrix[i][j] = 1
        // if there is an edge from i to j
        this.adjacency_matrix[s - 1][destination - 1] = 1
    }
 
    issink(i){
        for(let j=0;j<this.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(this.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(this.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
    eliminate(){
        let i = 0
        let j = 0
        while(i < this.vertices && j < this.vertices){
 
            // If the index is 1, increment the row
            // we are checking by 1
            // else increment the column
            if(this.adjacency_matrix[i][j] == 1)
                i += 1
            else
                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 > this.vertices)
            return -1
        else if(this.issink(i) == false)
            return -1
        else
            return i
    }
}
 
// Driver Code
 
let number_of_vertices = 6
let number_of_edges = 5
let 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)
 
let 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)
    document.write(`Sink found at vertex ${(vertex + 1)}`,"</br>")
else
    document.write("No Sink","</br>")
 
// This code is contributed by shinjanpatra
 
</script>

Output

No Sink

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

Time complexity: O(V^2)

We have used a 2-D array of size V x V to store the adjacency matrix of the given graph. The time complexity of the algorithm is O(V^2) as we need to traverse the complete adjacency matrix to find the sink vertex.

Time complexity: O(V^2)

The space complexity of the algorithm is also O(V^2) since we need to store the adjacency matrix.

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

Deepak Srivatsav

Improve

Construct a graph from given degrees of all vertices

Number of sink nodes in a graph

BFS and DFS on Graph

Cycle in a Graph

Shortest Paths in Graph

Minimum Spanning Tree in Graph

Topological Sorting in Graph

Connectivity of Graph

Maximum flow in a Graph

Some must do problems on Graph

Determine whether a universal sink exists in a directed graph

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?