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

Я реализовал алгоритм сильно связанных компонентов Тарьяна, согласно wikipedia , на Python, но он не работает. Алгоритм довольно короткий, и я не могу найти никакой разницы, поэтому не могу сказать, почему он не работает. Я попытался проверить исходную статью, но не смог ее найти.

Вот код.

def strongConnect(v):
  global E, idx, CCs, c, S
  idx[v] = (c, c) #idx[v][0] for v.index # idx[v][1] for v.lowlink
  c += 1
  S.append(v)  
  for w in [u for (v2, u) in E if v == v2]:
    if idx[w][0] < 0:
      strongConnect(w)
      # idx[w] = (idx[w][0], min(idx[v][1], idx[w][1])) #fixed, thx
      idx[v] = (idx[v][0], min(idx[v][1], idx[w][1]))
    elif w in S:
      idx[v] = (idx[v][0], min(idx[v][1], idx[w][0]))
  if (idx[v][0] == idx[v][1]):
    i = S.index(v)
    CCs.append(S[i:])
    S = S[:i]

E = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A'), ('A', 'E'), ('C', 'A'), ('C', 'E'), ('D', 'F'), ('F', 'B'), ('E', 'F')]
idx = {}
CCs = []
c = 0
S = []
for (u, v) in E:
  idx[u] = (-1, -1)
  idx[v] = (-1, -1)
for v in idx.keys():
  if idx[v][0] < 0:
    strongConnect(v)

print(CCs)

Вы можете проверить график визуально , если хотите. Как видите, это довольно прямой перевод псевдокода из Википедии. Однако вот результат:

[['D', 'E', 'F'], ['B', 'C'], ['A']]

Должен быть только один сильно связанный компонент, а не три. Я надеюсь, что вопрос правильный во всех отношениях, если не простите. В любом случае большое спасибо.

13
задан jmora 24 July 2012 в 17:38
поделиться