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

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

Вот код.

  • Как Python реализовал встроенную функцию pow ()?
  • Код для генерации e на одну цифру за раз
  • Алгоритм генерации следующего элемента из последовательности, путем нахождения шаблона
  • Как проследить путь в первом поиске?
  • Каков наилучший способ получить все делители числа?
  • Как найти целые n-ые корни?
  • 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']] 

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

  • Как Python реализовал встроенную функцию pow ()?
  • Код для генерации e на одну цифру за раз
  • Алгоритм генерации следующего элемента из последовательности, путем нахождения шаблона
  • Как проследить путь в первом поиске?
  • Каков наилучший способ получить все делители числа?
  • Как найти целые n-ые корни?
  • One Solution collect form web for “Тархан сильно связанными компонентами в python не работает”

    Хорошо, у меня было еще немного времени подумать об этом. Я уже не уверен, что фильтрация краев была проблемой, как я уже говорил. На самом деле, я думаю, что существует двусмысленность в псевдокоде ; for each (v, w) in E для каждого ребра (как буквальное значение for each предложения), или только каждое ребро, начинающееся с v , (как вы разумно предполагаете)? Затем, после цикла for, является ли рассматриваемый v конечным v из цикла for , как это было бы в 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) 

    Однако я считаю, что использование глобальных переменных здесь неприятно. Вы можете скрыть это в своем собственном модуле, но я предпочитаю идею создания класса, вызывающего вызов. После более пристального изучения оригинального псевдокода Тарьяна (который, кстати, подтверждает, что «отфильтрованная» версия верна), я написал это. Он включает простой класс 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)) 
    Python - лучший язык программирования в мире.