Хорошо, у меня было еще немного времени, чтобы подумать об этом.Я больше не уверен, что фильтрация краев была проблемой, как я уже говорил.На самом деле, я думаю, что в псевдокоде есть двусмысленность;for each (v, w) in E означает для каждого ребра (как предполагает буквальное значение for each) или только каждое ребро, начинающееся с v (как вы разумно предположили)?Затем, после цикла for, является ли рассматриваемый v последним v из цикла for, как это было бы в Python?Или это восходит к тому, чтобы быть оригинальным v?Псевдокод не имеет четко определенного поведения в этом случае!(Было бы очень странно, если бы v в конце было последним, произвольным, значением v из цикла. Это говорит о том, что фильтрация верна, потому что в этом случае v означает то же самоедо конца.)
Однако при любых обстоятельствах ошибка clear в вашем коде есть здесь:
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)
Однако использование глобальных переменных здесь мне неприятно.Вы можете скрыть это в своем собственном модуле, но я предпочитаю идею создания вызываемого класса.Посмотрев более внимательно на оригинальный псевдокод Тарьяна (который, кстати, подтверждает, что «отфильтрованная» версия верна), я написал это.Он включает в себя простой класс 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))