python - Tarjan 在 python 中的强连接组件算法不起作用

Question

我根据 wikipedia 实现了 Tarjan 的强连通分量算法，在 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)

您可以 check the graph visually如果你更喜欢。如您所见，这是对维基百科中伪代码的相当前向的翻译。然而，这是输出:

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

应该只有一个强连通分量，而不是三个。我希望这个问题在所有方面都是正确的，如果不是，我很抱歉。无论如何，非常感谢。

Answer 1

好吧，我还有更多时间考虑这个问题。正如我之前所说，我不再确定过滤边缘是问题所在。事实上，我认为 pseudocode 中存在歧义。 ; for each (v, w) in E 是指 each edge(如 for each 的字面意思所示)，还是仅表示每条边以 v 开头，(正如您合理假设的那样)？然后，在 for 循环之后，v 是否是 for 循环中的最终 v，就像在 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 的 original pseudocode 之后，(顺便说一下，这证实了“过滤”版本是正确的)，我写了这个。它包括一个简单的 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))