python中的Tarjan強連通組件算法不起作用

Question

我在Python中根據wikipedia實現了Tarjan的強連通組件算法，但它不起作用。該算法很短，我找不到任何區別，所以我不知道它爲什麼不起作用。我試圖檢查原始文件，但找不到它。

這是代碼。

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對於的每條邊的意思是（如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))