Нахождение сильно связных компонентов в графе (python)

Меня попросили написать маленькую программу по нахождению сильно связных компонентов. И так как я на данный момент изучаю python, то решил  реализовать эту программу именно на этом (на мой взгляд афигенном языке!!!).

 

Задача заключалась в следующем:  Вершины графа и ребра, которые соединяют их вводятся в файл (допустим input), а на выход в файл (как Вы уже поняли out) записываются все сильно связные компоненты этого графа.

 

Примерно так: 

2 5 6 - то есть из вершины 2 идет ребро к вершинам 5 и 6

4 4 5 - из вершины 4 идет только одно ребро к вершине 5, так как ребра от вершины 4 к самой вершине 4 нам ненужно. Так что можно было и написать 4 5. Но это нам погоду не меняет.   

 

Этак немного WIKI - для самообразования:

Компонента сильной связности в орграфе

Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы.

 

 

Алгоритмы

Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:

1. При помощи транзитивного замыкания проверяем, достижима ли t из s, и s из t, для всех пар s и t.
2. Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.
3. Поиск компонент связности такого неориентированного графа даст нам компоненты сильной связности нашего орграфа.

Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.
Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмы Косарайю, Габова и Тарьяна.

 ===================================================

Ну и сама реализация (Я пошел по 1-му алгоритму):

 

def slovar_graf(adress):
    points = {}
    for line in open(adress):
        line = line.split('\n')
        line = line[0]
        line = line.split(' ')
        points[line[0]] = line[1:]
       
    graphs = {}
    for line in open(adress):
        line = line.split('\n')
        line = line[0]
        line = line.split(' ')
        graphs[line[0]] = line[1:]                
    return graphs

//считывание input файла
abc=slovar_graf('/home/Documents/Aptana Studio 3 Workspace/grafs/1.txt')






def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath
        return None
   

def connect(x1,x2):
    if x1!=None and x2!=None:
        return "silno svyazni"
    else:
        return ""


print len(abc)

i=1
j=1

//Открываем и записываем наш результат
f1 = open("/home/Documents/Aptana Studio 3 Workspace/grafs/out.txt", 'w')
f1.write("Rezultat\n")

while i<len(abc):
   
    i=str(i)
   
    j=1
   
    while j<len(abc):
        j=str(j)
        graf1=find_path(abc, i, j)
        graf2=find_path(abc, j, i)
        if connect(graf1,graf2)=="silno svyazni":
            if i!=j:
                print 'Put tuda'
                f1.writelines("Put tuda ")
                print graf1
                f1.writelines("[")
                f1.writelines(graf1)
                f1.writelines("]")
                f1.writelines(" Put ot tuda ")
                print graf2
                f1.writelines("[")
                f1.writelines(graf2)
                f1.writelines("]")
                print '\n'
                f1.writelines("\n\n")

          
        j=int(j)+1
   
    i=int(i)+1
===================================================