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
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.
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> |
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
Contact Us