El algoritmo de componentes fuertemente conectados de Tarjan en python no funciona

Question

Implementé el algoritmo de componentes fuertemente conectados de Tarjan, de acuerdo con wikipedia, en Python, pero no está funcionando. El algoritmo es bastante corto y no puedo encontrar ninguna diferencia, por lo que no puedo decir por qué no está funcionando. Traté de revisar el documento original, pero no pude encontrarlo.

Aquí está el código.

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) 

Puede check the graph visually si lo prefiere. Como puede ver, esta es una traducción bastante directa del pseudocódigo en wikipedia. Sin embargo, este es el resultado:

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

Solo debe haber un componente fuertemente conectado, no tres. Espero que la pregunta sea correcta en todos sus aspectos, si no lo siento. En cualquier caso, muchas gracias.

Answer 1

Ok, tuve algo más de tiempo para pensar en esto. Ya no estoy seguro de que el problema sea filtrar los bordes, como dije anteriormente. De hecho, creo que hay una ambigüedad en el pseudocode; ¿for each (v, w) in E significa cada borde (como sugiere el significado literal de for each), o solo cada borde que comienza con v, (como razonablemente asumió)? Entonces, después del bucle for, ¿está el v en cuestión el v final del bucle for, como lo estaría en Python? ¿O eso vuelve a ser el original v? ¡El seudocódigo no tiene un comportamiento de alcance claramente definido en este caso! (Sería realmente extraño si el v al final fuera el último valor arbitrario de v del ciclo. Eso sugiere que el filtrado es correcto, porque en ese caso, v significa lo mismo durante todo el proceso).

Sin embargo, bajo ninguna circunstancia, el claro error en su código está aquí:

idx[w] = (idx[w][0], min(idx[v][1], idx[w][1])) 

de acuerdo con el pseudocódigo, que sin duda debe haber

idx[v] = (idx[v][0], min(idx[v][1], idx[w][1])) 

Una vez que realice ese cambio, obtendrá el resultado esperado. Francamente, no me sorprende que hayas cometido ese error, porque estás usando una estructura de datos realmente extraña y contradictoria. Esto es lo que creo que es una mejora: agrega solo algunas líneas más, y creo que es mucho más legible.

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) 

Sin embargo, me parece desagradable el uso de variables globales aquí. Podrías esconder esto en su propio módulo, pero prefiero la idea de crear una clase invocable. Después de mirar más de cerca el original pseudocode de Tarjan, (que confirma que la versión "filtrada" es correcta, por cierto), escribí esto. Incluye un simple clase Graph y hace par de pruebas básicas:

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))