Determine whether a universal sink exists in a directed graph | Java program to find whether a universal sink exists in a directed graph ; constructor to initialize number of vertices and size of adjacency matrix ; make adjacency_matrix [ i ] [ j ] = 1 if there is an edge from i to 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 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 none of the checks fails , 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 ; If the index is 1 , increment the row we are checking by 1 else increment the column ; If i exceeds the number of vertices , it means that there is no valid vertex in the given vertices that can be a sink ; Driver Code ; 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 ; returns 0 based indexing of vertex . returns - 1 if no sink exits . returns the vertex number - 1 if sink is found
import java . io . * ; import java . util . * ; class Graph { int vertices ; int [ ] [ ] adjacency_matrix ; public graph ( int vertices ) { this . vertices = vertices ; adjacency_matrix = new int [ vertices ] [ vertices ] ; } public void insert ( int source , int destination ) { adjacency_matrix [ destination - 1 ] = 1 ; } public boolean issink ( 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 ; } public 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 ( ! 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 ) ; 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 ) System . out . println ( " Sink ▁ found ▁ at ▁ vertex ▁ " + ( vertex + 1 ) ) ; else System . out . println ( " No ▁ Sink " ) ; } }