Answer to Question #294801 in Python for eranna

Question

Given a directed graph in adjacency matrix form, determine if it contains a universal sink – a vertex with in-degree n-1 and out-degree 0. (The number of vertices in the graph is n.) Input Format: The input is a text file which gives the adjacency matrix representation of a directed graph. Sample Input (for the graph above): 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 Sample Output: Yes 

Answer 1

import numpy as np

class Graph:

    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):
        self.adjacency_matrix[s - 1][destination - 1] = 1

    def issink(self, i):
        for j in range(self.vertices):
            if self.adjacency_matrix[i][j] == 1:
                return False
            if self.adjacency_matrix[j][i] == 0 and j != i:
                return False
        return True

    def eliminate(self):
        i = 0
        j = 0
        while i < self.vertices and j < self.vertices:
            if self.adjacency_matrix[i][j] == 1:
                i += 1
            else:
                j += 1
        if i > self.vertices:
            return -1
        elif self.issink(i) is False:
            return -1
        else:
            return i

def read_f(name_f):
    given_file = open(name_f, 'r')

    lines = given_file.readlines()
    digits = []
    for line in lines:
        for c in line:
            if c.isdigit() == True:
                digits.append(int(c))
    given_file.close()
    size_g = int(len(digits)**(1/2))
    digits = np.array(digits).reshape(size_g, size_g)

    g = Graph(size_g)
    for i in range(len(digits)):
        for j in range(len(digits)):
            if digits[i][j] == 1:
                g.insert(i+1, j+1)
    vertex = g.eliminate()
    return(vertex)

if __name__ == "__main__":
    name_f = 'test.txt'
    vertex = read_f(name_f)
    if vertex >= 0:
        print("Yes. Sink found at vertex %d" % (vertex + 1))
    else:
        print("No Sink")