L'algoritmo di componenti fortemente collegato di Tarjan in python non funziona

Question

Ho implementato l'algoritmo di componenti fortemente connessi di Tarjan, in base a wikipedia, in Python, ma non funziona. L'algoritmo è piuttosto breve e non riesco a trovare alcuna differenza, quindi non posso dire perché non funziona. Ho provato a controllare il documento originale, ma non sono riuscito a trovarlo.

Ecco il codice.

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) 

Si può check the graph visually se si preferisce. Come puoi vedere questa è una traduzione abbastanza avanzata dello pseudocodice in wikipedia. Tuttavia, questo è l'output:

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

Ci dovrebbe essere solo un componente fortemente connesso, non tre. Spero che la domanda sia giusta in tutti i suoi aspetti, se non mi dispiace. In ogni caso, grazie mille.

Answer 1

Ok, ho avuto un po 'di tempo per pensarci. Non sono più sicuro che il filtraggio dei bordi fosse il problema, come ho affermato in precedenza. In effetti, penso che ci sia un'ambiguità nel pseudocode; corrisponde a for each (v, w) in E per per ogni spigolo (come suggerisce il significato letterale di for each) o solo a ciascun fronte che inizia con v (come si presuppone ragionevolmente)? Quindi, dopo il ciclo for, lo v in questione è l'v finale dal ciclo for, come sarebbe in Python? O quello torna ad essere l'originale v? Lo pseudocodice non ha un comportamento di scoping definito chiaramente in questo caso! (Sarebbe davvero strano se il v alla fine dovesse essere l'ultimo, arbitrario, valore di v dal ciclo. Ciò suggerisce che il filtro è corretto, perché in quel caso, v significa la stessa cosa fino in fondo.)

Tuttavia, in nessun caso, la chiara errore nel codice è qui:

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

Secondo il pseudocodice, che deve assolutamente essere

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

Una volta apportata questa modifica, si ottiene il risultato previsto. Francamente non mi sorprende che tu abbia commesso questo errore, perché stai usando una struttura di dati davvero strana e controintuitiva. Ecco quello che penso sia un miglioramento - aggiunge solo poche righe in più, e trovo che sia molto più leggibile.

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) 

Tuttavia, ritengo che l'uso di variabili globali sia sgradevole. Potresti nasconderlo nel suo modulo, ma preferisco l'idea di creare una classe chiamabile. Dopo aver osservato più da vicino Tarjan original pseudocode (che conferma che la versione "filtrata" è corretta, comunque), ho scritto questo. Esso comprende una semplice classe Graph e fa paio di test di base:

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