from graph.graph import Graph_Mat

def top_ord(g):
	t_order = []
	vertices = g.vertices()
	#print(vertices)

	while vertices != None:
		nwnee = node_with_no_entering_edges(g, vertices)
		if nwnee == 0:
			break
		if nwnee == 404:
			return "There is a cycle"
		else:
			t_order.append(nwnee)
			g = free_node(g, nwnee)
			vertices.remove(nwnee)
			#print(nwnee, vertices)
	return t_order


def free_node(g, v):
	vNum = g.vertex_number(v)
	nuMatrix = g.matrix()
	for row in range(len(g.vertices())):
		for column in range(len(g.vertices())):
			if row == vNum or column == vNum:
				nuMatrix[row][column] = 0
	return Graph_Mat(nuMatrix)

def node_with_no_entering_edges(g, vertices):
	for column in range(len(g.vertices())):
		testEdge = g.vertex_name(column)
		if testEdge in vertices:
			isGood = True
			for row in range(len(g.vertices())):
				weight = g.matrix()[row][column]
				if weight > 0:
					isGood=False
					break
			if isGood == True:
				return testEdge
	if g.matrix() == [[0]*len(g.vertices())]*len(g.vertices()):
		return 0
	return 404

if __name__ == '__main__':
    g = [   [0,1,0,1,0,0],
            [0,0,0,1,1,0],
            [0,0,0,0,1,0],
            [1,0,0,0,0,0],
            [0,0,1,0,0,0],
            [0,1,0,0,0,0]]
    grap = Graph_Mat(g)
    print()
    print('Topological order:', top_ord(grap))
    print()

    g = [   [0,1,0,1,0,0],
            [0,0,0,0,0,0],
            [0,0,0,0,0,1],
            [0,0,1,0,0,0],
            [0,1,0,0,0,0],
            [0,0,0,0,0,0]]
    grap = Graph_Mat(g)
    print()
    print('Topological order:', top_ord(grap))
    print()
