Тарджан сильно связанными компонентами алгоритм в python не работает

Ответ 1

Хорошо, у меня было еще немного времени подумать об этом. Я уже не уверен, что фильтрация краев была проблемой, как я уже говорил. На самом деле, я думаю, что существует двусмысленность в pseudocode; означает for each (v, w) in E для каждого ребра (как предполагает буквальное значение for each), или только каждое ребро, начинающееся с v (как вы разумно предполагаете)? Затем, после цикла for, отвечает v конечный v из цикла for, как это было бы в Python? Или это возвращается к оригиналу v? В этом случае псевдокод не имеет четко определенного поведения в этом случае! (Было бы действительно странно, если бы конец v в конце должен был быть последним, произвольным значением v из цикла. Это говорит о том, что фильтрация правильная, поскольку в этом случае v означает одно и то же на всем пути.)

Однако при любых обстоятельствах явная ошибка в вашем коде:

  idx[w] = (idx[w][0], min(idx[v][1], idx[w][1]))

В соответствии с псевдокодом это определенно должно быть

  idx[v] = (idx[v][0], min(idx[v][1], idx[w][1]))

Как только вы сделаете это изменение, вы получите ожидаемый результат. Честно говоря, меня не удивляет, что вы допустили эту ошибку, потому что вы используете действительно странную и противоречивую структуру данных. Здесь я думаю, что это улучшение - оно добавляет еще несколько строк, и я считаю, что это гораздо более читаемо.

import itertools

def strong_connect(vertex):
    global edges, indices, lowlinks, connected_components, index, stack
    indices[vertex] = index
    lowlinks[vertex] = index
    index += 1
    stack.append(vertex)

    for v, w in (e for e in edges if e[0] == vertex):
        if indices[w] < 0:
            strong_connect(w)
            lowlinks[v] = min(lowlinks[v], lowlinks[w])
        elif w in stack:
            lowlinks[v] = min(lowlinks[v], indices[w])

    if indices[vertex] == lowlinks[vertex]:
        connected_components.append([])
        while stack[-1] != vertex:
            connected_components[-1].append(stack.pop())
        connected_components[-1].append(stack.pop())

edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), 
         ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), 
         ('D', 'F'), ('F', 'B'), ('E', 'F')]
vertices = set(v for v in itertools.chain(*edges))
indices = dict((v, -1) for v in vertices)
lowlinks = indices.copy()
connected_components = []

index = 0
stack = []
for v in vertices:
    if indices[v] < 0:
        strong_connect(v)

print(connected_components)

Однако, я считаю, что использование глобальных переменных здесь неприятно. Вы можете скрыть это в своем собственном модуле, но я предпочитаю идею создания класса, вызывающего вызов. После более пристального изучения Tarjan исходного псевдокода (который подтверждает, что, кстати, "отфильтрованная" версия верна), я написал это. Он включает простой класс Graph и выполняет пару базовых тестов:

from itertools import chain
from collections import defaultdict

class Graph(object):
    def __init__(self, edges, vertices=()):
        edges = list(list(x) for x in edges)
        self.edges = edges
        self.vertices = set(chain(*edges)).union(vertices)
        self.tails = defaultdict(list)
        for head, tail in self.edges:
            self.tails[head].append(tail)

    @classmethod
    def from_dict(cls, edge_dict):
        return cls((k, v) for k, vs in edge_dict.iteritems() for v in vs)

class _StrongCC(object):
    def strong_connect(self, head):
        lowlink, count, stack = self.lowlink, self.count, self.stack
        lowlink[head] = count[head] = self.counter = self.counter + 1
        stack.append(head)

        for tail in self.graph.tails[head]:
            if tail not in count:
                self.strong_connect(tail)
                lowlink[head] = min(lowlink[head], lowlink[tail])
            elif count[tail] < count[head]:
                if tail in self.stack:
                    lowlink[head] = min(lowlink[head], count[tail])

        if lowlink[head] == count[head]:
            component = []
            while stack and count[stack[-1]] >= count[head]:
                component.append(stack.pop())
            self.connected_components.append(component)

    def __call__(self, graph):
        self.graph = graph
        self.counter = 0
        self.count = dict()
        self.lowlink = dict()
        self.stack = []
        self.connected_components = []

        for v in self.graph.vertices:
            if v not in self.count:
                self.strong_connect(v)

        return self.connected_components

strongly_connected_components = _StrongCC()

if __name__ == '__main__':
    edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'),
             ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'),
             ('D', 'F'), ('F', 'B'), ('E', 'F')]
    print strongly_connected_components(Graph(edges))
    edge_dict = {'a':['b', 'c', 'd'],
                 'b':['c', 'a'],
                 'c':['d', 'e'],
                 'd':['e'],
                 'e':['c']}
    print strongly_connected_components(Graph.from_dict(edge_dict))