わかりました、私はこれについて考える時間がもう少しありました。前に述べたように、エッジのフィルタリングが問題であったかどうかはわかりません。実際、疑似コードにはあいまいさがあると思います。は各エッジfor each (v, w) in Eを意味しますか（の文字通りの意味が示唆するように）、または , で始まる各エッジのみを意味しますか（あなたが合理的に想定したように）？次に、for ループの後、問題のループは Python の場合のように、ループの最終的なものですか? それとも元に戻るのでしょうか？この場合、疑似コードには明確に定義されたスコープ動作がありません! (もし最後に が最後で任意のfor eachvvvforvvvループから。これは、フィルタリングが正しいことを示唆しています。その場合、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))
