एक अनियंत्रित ग्राफ

Question

में सभी साइकिल अड्डों की पहचान करने के लिए एल्गोरिदम मेरे पास वर्टेक्स V और एज E के साथ एक अप्रत्यक्ष ग्राफ है। मैं उस ग्राफ में सभी चक्र अड्डों की पहचान करने के लिए एक एल्गोरिदम की तलाश में हूं।

मुझे लगता है कि Tarjans algorithm एक अच्छी शुरुआत है। लेकिन the reference मैं चक्र, नहीं चक्र आधार के सभी खोजने के बारे में है है (जो, by definition चक्र है कि अन्य चक्र के संघ द्वारा निर्माण नहीं किया जा सकता है)।

उदाहरण के लिए, नीचे ग्राफ पर एक नज़र डालें:

तो, एक एल्गोरिथ्म उपयोगी होगा। यदि कोई मौजूदा कार्यान्वयन है (अधिमानतः सी # में), यह भी बेहतर है!

Answer 1

जो मैं कह सकता हूं, न केवल ब्रायन की हंच स्पॉट है, बल्कि एक मजबूत प्रस्ताव भी है धारण करता है: प्रत्येक किनारे जो न्यूनतम स्पैनिंग पेड़ में नहीं है, बिल्कुल एक नया "आधार चक्र" जोड़ता है।

इसे देखने के लिए, देखते हैं कि क्या होता है जब आप एक बढ़त ई जोड़ते हैं जो एमएसटी में नहीं है। चलो चीजों को जटिल बनाने और कुछ नोटेशन जोड़ने के लिए पसंदीदा गणित तरीका करते हैं;) मूल ग्राफ जी, ई जी जोड़ने से पहले ग्राफ, और ई जी जोड़ने के बाद ग्राफ को कॉल करें। इसलिए हमें यह जानने की ज़रूरत है कि "बेस चक्र गणना" जी से 'जी' में कैसे बदलती है।

ई जोड़ने से कम से कम एक चक्र बंद होना चाहिए (अन्यथा ई पहली जगह जी के एमएसटी में होगा)। तो जाहिर है कि इसे जी में पहले से मौजूद मौजूदा लोगों को कम से कम एक "आधार चक्र" जोड़ना होगा। लेकिन क्या यह एक से अधिक जोड़ता है?

यह दो से अधिक नहीं जोड़ सकता है, क्योंकि कोई किनारा दो से अधिक आधार चक्रों का सदस्य नहीं हो सकता है। लेकिन यदि ई दो आधार चक्रों का सदस्य है, तो इन दो बेस चक्रों का "संघ" जी में आधार चक्र होना चाहिए, इसलिए फिर हम पाते हैं कि चक्रों की संख्या में परिवर्तन अभी भी एक है।

एर्गो, प्रत्येक किनारे के लिए एमएसटी में नहीं, आपको एक नया आधार चक्र मिलता है। तो "गिनती" हिस्सा सरल है। प्रत्येक आधार चक्र के लिए सभी किनारों ढूँढना है एक छोटे से जटिल काम है, लेकिन ऊपर के तर्क के बाद, मुझे लगता है कि यह यह कर सकता है (छद्म अजगर में):

for v in vertices[G]: 
    cycles[v] = [] 

for e in (edges[G] \ mst[G]): 
    cycle_to_split = intersect(cycles[e.node1], cycles[e.node2]) 
    if cycle_to_split == None: 
     # we're adding a completely new cycle 
     path = find_path(e.node1, e.node2, mst[G]) 
     for vertex on path: 
      cycles[vertex].append(path + [e]) 
     cycles 
    else: 
     # we're splitting an existing base cycle 
     cycle1, cycle2 = split(cycle_to_split, e) 
     for vertex on cycle_to_split: 
      cycles[vertex].remove(cycle_to_split) 
      if vertex on cycle1: 
       cycles[vertex].append(cycle1) 
      if vertex on cycle2: 
       cycles[vertex].append(cycle2) 

base_cycles = set(cycles) 

संपादित: कोड सभी आधार खोजना चाहिए एक ग्राफ में चक्र (नीचे स्थित बेस_साइकिल)।

• एक ग्राफ (MST [जी]) की न्यूनतम फैले पेड़ खोजने के
• दो सूचियों के बीच अंतर (किनारों \ MST [जी])
• खोजें: मान्यताओं आप जानते हैं कि कैसे करने के लिए कर रहे हैं

यह (विभाजन समारोह) के लिए एक अतिरिक्त बढ़त जोड़कर दो भागों में एक चक्र विभाजित दो सूचियों

के एक चौराहे एक MST

पर दो कोने के बीच पथ खोजने के लिए और यह मुख्य रूप से उपर्युक्त चर्चा का पालन करता है। प्रत्येक किनारे के लिए एमएसटी में नहीं, आपके पास दो मामले हैं: या तो यह एक बिल्कुल नया आधार चक्र लाता है, या यह दो में मौजूदा एक को विभाजित करता है। यह पता लगाने के लिए कि दोनों में से कौन सा मामला है, हम सभी बेस चक्रों को ट्रैक करते हैं कि एक कशेरुक चक्र चक्र का उपयोग करने का एक हिस्सा है।

Answer 2

एक चक्र का पता लगाने का मानक तरीका दो पुनरावृत्तियों का उपयोग करना है - प्रत्येक पुनरावृत्ति के लिए, एक कदम आगे बढ़ता है और दूसरा दो। एक चक्र होना चाहिए, वे किसी बिंदु पर एक दूसरे को इंगित करेंगे।

इस दृष्टिकोण को चक्रों को रिकॉर्ड करने और आगे बढ़ने के लिए बढ़ाया जा सकता है।

Answer 3

मेरे सिर के ऊपर से, मैं किसी भी न्यूनतम स्पैनिंग ट्री एल्गोरिदम (प्राइम, क्रस्कल, आदि) को देखकर शुरू करूंगा। एमएसटी में नहीं हैं किनारों की तुलना में अधिक आधार चक्र (यदि मैं इसे सही ढंग से समझता हूं) नहीं हो सकता है ....

Answer 4

निम्नलिखित मेरे वास्तविक अपरीक्षित सी # इन सभी "आधार चक्र 'को खोजने के लिए कोड है:

public HashSet<List<EdgeT>> FindBaseCycles(ICollection<VertexT> connectedComponent) 
{ 
    Dictionary<VertexT, HashSet<List<EdgeT>>> cycles = 
     new Dictionary<VertexT, HashSet<List<EdgeT>>>(); 

    // For each vertex, initialize the dictionary with empty sets of lists of 
    // edges 
    foreach (VertexT vertex in connectedComponent) 
     cycles.Add(vertex, new HashSet<List<EdgeT>>()); 

    HashSet<EdgeT> spanningTree = FindSpanningTree(connectedComponent); 

    foreach (EdgeT edgeNotInMST in 
      GetIncidentEdges(connectedComponent).Except(spanningTree)) { 
     // Find one cycle to split, the HashSet resulted from the intersection 
     // operation will contain just one cycle 
     HashSet<List<EdgeT>> cycleToSplitSet = 
      cycles[(VertexT)edgeNotInMST.StartPoint] 
       .Intersect(cycles[(VertexT)edgeNotInMST.EndPoint]); 

     if (cycleToSplitSet.Count == 0) { 
      // Find the path between the current edge not in ST enpoints using 
      // the spanning tree itself 
      List<EdgeT> path = 
       FindPath(
        (VertexT)edgeNotInMST.StartPoint, 
        (VertexT)edgeNotInMST.EndPoint, 
        spanningTree); 

      // The found path plus the current edge becomes a cycle 
      path.Add(edgeNotInMST); 

      foreach (VertexT vertexInCycle in VerticesInPathSet(path)) 
       cycles[vertexInCycle].Add(path); 
     } else { 
      // Get the cycle to split from the set produced before 
      List<EdgeT> cycleToSplit = cycleToSplitSet.GetEnumerator().Current; 
      List<EdgeT> cycle1 = new List<EdgeT>(); 
      List<EdgeT> cycle2 = new List<EdgeT>(); 
      SplitCycle(cycleToSplit, edgeNotInMST, cycle1, cycle2); 

      // Remove the cycle that has been splitted from the vertices in the 
      // same cicle and add the results from the split operation to them 
      foreach (VertexT vertex in VerticesInPathSet(cycleToSplit)) { 
       cycles[vertex].Remove(cycleToSplit); 
       if (VerticesInPathSet(cycle1).Contains(vertex)) 
        cycles[vertex].Add(cycle1); 
        if (VerticesInPathSet(cycle2).Contains(vertex)) 
         cycles[vertex].Add(cycle2); ; 
      } 
     } 
    } 
    HashSet<List<EdgeT>> ret = new HashSet<List<EdgeT>>(); 
    // Create the set of cycles, in each vertex should be remained only one 
    // incident cycle 
     foreach (HashSet<List<EdgeT>> remainingCycle in cycles.Values) 
      ret.AddAll(remainingCycle); 

     return ret; 
} 

Oggy's कोड था बहुत अच्छा और स्पष्ट लेकिन मैं यकीन है कि यह एक में शामिल कर रहा हूँ त्रुटि, या यह मुझे है कि आपके छद्म अजगर कोड :) समझ में नहीं आता है

cycles[v] = [] 

एक शीर्ष अनुक्रमित ढ़ंग नहीं किया जा सकता किनारों की सूचियों की आरी। मेरी राय में, इसे किनारों के सूचियों के सेटों का एक वर्टेक्स अनुक्रमित शब्दकोश होना चाहिए।

और, एक precisation जोड़ने के लिए:

for vertex on cycle_to_split: 

चक्र विभाजन शायद इसलिए कोने कोने आप का एक सेट में परिवर्तित करने के लिए है के माध्यम से यह दोहराना चाहते किनारों के आदेश दिया सूची है। यहां आदेश नगण्य है, इसलिए यह एक बहुत ही सरल अलौकिक है।

मैं फिर कहता हूँ, इस अपरीक्षित और uncomplete कोड है, लेकिन एक कदम आगे है। इसके लिए अभी भी एक उचित ग्राफ संरचना की आवश्यकता है (मैं एक घटना सूची का उपयोग करता हूं) और कई ग्राफ़ अल्घोरिटम्स जिन्हें आप कॉर्मन जैसी पाठ्य पुस्तकों में पा सकते हैं। मैं पाठ्य पुस्तकों में FindPath() और SplitCycle() को खोजने में सक्षम नहीं था, और बहुत ग्राफ में किनारों की संख्या के रैखिक समय में उन्हें कोड करने के लिए कठिन है। जब मैं उनका परीक्षण करूंगा तो उन्हें यहां रिपोर्ट करूंगा।

धन्यवाद बहुत ओग्गी!