Determine whether a universal sink exists in a directed graph | Python3 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
class Graph : NEW_LINE INDENT def __init__ ( self , vertices ) : NEW_LINE INDENT self . vertices = vertices NEW_LINE self . adjacency_matrix = [ [ 0 for i in range ( vertices ) ] for j in range ( vertices ) ] NEW_LINE DEDENT def insert ( self , s , destination ) : NEW_LINE INDENT self . adjacency_matrix [ s - 1 ] [ destination - 1 ] = 1 NEW_LINE DEDENT def issink ( self , i ) : NEW_LINE INDENT for j in range ( self . vertices ) : NEW_LINE INDENT if self . adjacency_matrix [ i ] [ j ] == 1 : NEW_LINE INDENT return False NEW_LINE DEDENT if self . adjacency_matrix [ j ] [ i ] == 0 and j != i : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def eliminate ( self ) : NEW_LINE INDENT i = 0 NEW_LINE j = 0 NEW_LINE while i < self . vertices and j < self . vertices : NEW_LINE INDENT if self . adjacency_matrix [ i ] [ j ] == 1 : NEW_LINE INDENT i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT j += 1 NEW_LINE DEDENT DEDENT if i > self . vertices : NEW_LINE INDENT return - 1 NEW_LINE DEDENT elif self . issink ( i ) is False : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT number_of_vertices = 6 NEW_LINE number_of_edges = 5 NEW_LINE g = Graph ( number_of_vertices ) NEW_LINE g . insert ( 1 , 6 ) NEW_LINE g . insert ( 2 , 3 ) NEW_LINE g . insert ( 2 , 4 ) NEW_LINE g . insert ( 4 , 3 ) NEW_LINE g . insert ( 5 , 3 ) NEW_LINE vertex = g . eliminate ( ) NEW_LINE if vertex >= 0 : NEW_LINE INDENT print ( " Sink ▁ found ▁ at ▁ vertex ▁ % d " % ( vertex + 1 ) ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No ▁ Sink " ) NEW_LINE DEDENT DEDENT