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

Este dilema se puede tratar de diferentes maneras, por lo tanto te enseñamos la solución más completa para nosotros.

Solución:

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

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, eso definitivamente debería ser

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

Una vez que realiza ese cambio, obtiene el resultado esperado. Francamente, no me sorprende que hayas cometido ese error, porque estás usando una estructura de datos realmente extraña y contraria a la intuición. Esto es lo que creo que es una mejora: agrega solo unas pocas 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, encuentro el uso de variables globales aquí de mal gusto. Podría ocultar esto en su propio módulo, pero prefiero la idea de crear una clase invocable. Después de mirar más de cerca el pseudocódigo original de Tarjan (que, por cierto, confirma que la versión "filtrada" es correcta), escribí esto. Incluye un sencillo Graph clase y hace un 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))

Aquí puedes ver las reseñas y valoraciones de los usuarios

Agradecemos que desees reafirmar nuestro análisis mostrando un comentario y dejando una valoración te lo agradecemos.

---

---

Utiliza Nuestro Buscador