Trabalho proposto para turma de LFA. Implementar fecho transitivo-reflexivo de uma relação representada como um grafo. Versão não otimizada, apenas uma possível solução.

lista-2.py

import sys

# Leitura do arquivo de entrada no formato especificado. Linhas iniciadas com 
# "#" sao comentarios. Nao era necessario os alunos implementarem isso.

grafoin = []
try:
    infilename = sys.argv[1]
    infile = open(infilename,'r')
    for line in infile:
        if line[0] != "#":
            try:
                a, b = line.split()
                grafoin.append( (a,b) )
            except:
                pass
except:
    print 'Erro passar arquivo com grafo', grafoin
    sys.exit(1)


# reflexivo
grafoin = set(grafoin)
grafoout = set()
for a in grafoin:
    grafoout.add(a)
    grafoout.add( (a[0], a[0]) )
    grafoout.add( (a[1], a[1]) )

# transitivo
nodes = set([x[0] for x in grafoout]) | set([x[1] for x in grafoout])
changed = True
while changed:
    tmp = grafoout
    for n in nodes:
        arestas1 = filter(lambda x: x[0] == n, grafoout)
        for a in arestas1:
            arestas2 = filter(lambda x: x[0] == a[1], grafoout)
            for b in arestas2:
                grafoout = grafoout | set( [(a[0], b[1])] )
    if len(grafoout) == len(tmp):
        changed = False

print " In: %02d - %s" %(len(grafoin), grafoin)
print "Out: %02d - %s" %(len(grafoout), grafoout)