Tarjan के अजगर में प्रभावशाली तरीके से कनेक्ट घटकों एल्गोरिथ्म

Question

काम नहीं कर रहा wikipedia के अनुसार Tarjan के प्रभावशाली तरीके से कनेक्ट घटकों एल्गोरिथ्म लागू किया, पायथन में, है, लेकिन यह काम नहीं कर रहा। एल्गोरिदम काफी छोटा है और मुझे कोई अंतर नहीं मिल रहा है, इसलिए मैं नहीं बता सकता कि यह क्यों काम नहीं कर रहा है। मैंने मूल कागज की जांच करने की कोशिश की, लेकिन इसे नहीं मिला।

यहाँ कोड है।

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) 

आप check the graph visually आप पसंद करते हैं कर सकते हैं। जैसा कि आप देख सकते हैं यह विकिपीडिया में छद्म कोड का एक बहुत आगे अनुवाद है। हालांकि, यह आउटपुट है:

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

केवल एक दृढ़ता से जुड़े घटक होना चाहिए, तीन नहीं। मुझे आशा है कि प्रश्न अपने सभी पहलुओं में सही होगा, अगर मुझे खेद नहीं है। किसी भी मामले में, बहुत बहुत धन्यवाद।

Answer 1

ठीक है, मैं इस बारे में सोचने के लिए कुछ और समय था। अब मैं निश्चित नहीं हूं कि किनारों को फ़िल्टर करना समस्या थी, जैसा कि मैंने पहले कहा था। वास्तव में, मुझे लगता है कि pseudocode में एक अस्पष्टता है; for each (v, w) in Eके लिए क्या मतलब है प्रत्येक किनारे (के रूप में for each का शाब्दिक अर्थ पता चलता है), या केवल एक किनारे v के साथ शुरुआत, (आप यथोचित मान लिया के रूप में)? फिर, पाश के लिए के बाद, अंतिम vfor पाश से प्रश्न में v, के रूप में यह अजगर में होगा है? या क्या यह मूल 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])) 

एक बार जब आप यह परिवर्तन कर लेंगे, तो आपको अपेक्षित परिणाम मिलेंगे। सच कहूं यह मुझे आश्चर्य नहीं है कि आप, कि गलती की है क्योंकि आप एक बहुत अजीब और counterintuitive डेटा संरचना का उपयोग कर रहे हैं। यहां मुझे लगता है कि एक सुधार है - यह केवल कुछ और लाइनों को जोड़ता है, और मुझे लगता है कि यह अधिक पढ़ने योग्य है।

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 के original pseudocode, (जो पुष्टि की है कि "फ़िल्टर किए गए" संस्करण सही है, जिस तरह से) पर और अधिक बारीकी से देखने के बाद, मैं इस लिखा था। यह एक सरल 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))