तर्जन चक्र पहचान सहायता सी #

Question

यहां तर्जन के चक्र का पता लगाने का एक सी # कार्यान्वयन है।

एल्गोरिथ्म यहाँ पाया जाता है: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

public class TarjanCycleDetect 
    { 
     private static List<List<Vertex>> StronglyConnectedComponents; 
     private static Stack<Vertex> S; 
     private static int index; 
     private static DepGraph dg; 
     public static List<List<Vertex>> DetectCycle(DepGraph g) 
     { 
      StronglyConnectedComponents = new List<List<Vertex>>(); 
      index = 0; 
      S = new Stack<Vertex>(); 
      dg = g; 
      foreach (Vertex v in g.vertices) 
      { 
       if (v.index < 0) 
       { 
        strongconnect(v); 
       } 
      } 
      return StronglyConnectedComponents; 
     } 

     private static void strongconnect(Vertex v) 
     { 
      v.index = index; 
      v.lowlink = index; 
      index++; 
      S.Push(v); 

      foreach (Vertex w in v.dependencies) 
      { 
       if (w.index < 0) 
       { 
        strongconnect(w); 
        v.lowlink = Math.Min(v.lowlink, w.lowlink); 
       } 
       else if (S.Contains(w)) 
       { 
        v.lowlink = Math.Min(v.lowlink, w.index); 
       } 
      } 

      if (v.lowlink == v.index) 
      { 
       List<Vertex> scc = new List<Vertex>(); 
       Vertex w; 
       do 
       { 
        w = S.Pop(); 
        scc.Add(w); 
       } while (v != w); 
       StronglyConnectedComponents.Add(scc); 
      } 

     } 

नोट एक DepGraph सिर्फ वर्टेक्स की एक सूची है। और वेरटेक्स में अन्य वेरटेक्स की एक सूची है जो किनारों का प्रतिनिधित्व करती है। इसके अलावा इंडेक्स और लोलिंक को -1

संपादित करें: यह काम कर रहा है ... मैंने अभी परिणामों का गलत व्याख्या किया है।

Answer 1

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

मेरा मानना ​​है कि उपर्युक्त काम कर रहा है। यदि आपको इसकी ज़रूरत है तो इसका उपयोग करने के लिए स्वतंत्र महसूस करें!

Answer 2

2008 के क्विकग्राफ ने इस एल्गोरिदम का समर्थन किया है। कार्यान्वयन के लिए StronglyConnectedComponentsAlgorithm कक्षा, या उपयोग शॉर्टकट के लिए AlgorithmExtensions.StronglyConnectedComponents विधि देखें।

उदाहरण:

// Initialize result dictionary 
IDictionary<string, int> comps = new Dictionary<string, int>(); 

// Run the algorithm 
graph.StronglyConnectedComponents(out comps); 

// Group and filter the dictionary 
var cycles = comps 
    .GroupBy(x => x.Value, x => x.Key) 
    .Where(x => x.Count() > 1) 
    .Select(x => x.ToList()) 

Answer 3

उदाहरण सवाल में ऊपर प्रस्तुत किसी को जल्दी से उसके साथ खेलना चाहते हैं चाहिए कार्यात्मक नहीं है। यह भी ध्यान रखें कि यह स्टैक आधारित है, जो आपके स्टैक को विस्फोट कर देगा यदि आप कुछ भी ग्राफ के सबसे छोटे हैं। यहाँ है कि मॉडल ग्राफ Tarjan विकिपीडिया पृष्ठ पर प्रस्तुत एक इकाई परीक्षण के साथ एक काम कर उदाहरण है:

public class Vertex 
{ 
    public int Id { get;set; } 
    public int Index { get; set; } 
    public int Lowlink { get; set; } 

    public HashSet<Vertex> Dependencies { get; set; } 

    public Vertex() 
    { 
     Id = -1; 
     Index = -1; 
     Lowlink = -1; 
     Dependencies = new HashSet<Vertex>(); 
    } 

    public override string ToString() 
    { 
     return string.Format("Vertex Id {0}", Id); 
    } 

    public override int GetHashCode() 
    { 
     return Id; 
    } 

    public override bool Equals(object obj) 
    { 
     if (obj == null) 
      return false; 

     Vertex other = obj as Vertex; 

     if (other == null) 
      return false; 

     return Id == other.Id; 
    } 
} 

public class TarjanCycleDetectStack 
{ 
    protected List<List<Vertex>> _StronglyConnectedComponents; 
    protected Stack<Vertex> _Stack; 
    protected int _Index; 

    public List<List<Vertex>> DetectCycle(List<Vertex> graph_nodes) 
    { 
     _StronglyConnectedComponents = new List<List<Vertex>>(); 

     _Index = 0; 
     _Stack = new Stack<Vertex>(); 

     foreach (Vertex v in graph_nodes) 
     { 
      if (v.Index < 0) 
      { 
       StronglyConnect(v); 
      } 
     } 

     return _StronglyConnectedComponents; 
    } 

    private void StronglyConnect(Vertex v) 
    { 
     v.Index = _Index; 
     v.Lowlink = _Index; 

     _Index++; 
     _Stack.Push(v); 

     foreach (Vertex w in v.Dependencies) 
     { 
      if (w.Index < 0) 
      { 
       StronglyConnect(w); 
       v.Lowlink = Math.Min(v.Lowlink, w.Lowlink); 
      } 
      else if (_Stack.Contains(w)) 
      { 
       v.Lowlink = Math.Min(v.Lowlink, w.Index); 
      } 
     } 

     if (v.Lowlink == v.Index) 
     { 
      List<Vertex> cycle = new List<Vertex>(); 
      Vertex w; 

      do 
      { 
       w = _Stack.Pop(); 
       cycle.Add(w); 
      } while (v != w); 

      _StronglyConnectedComponents.Add(cycle); 
     } 
    } 
} 

    [TestMethod()] 
    public void TarjanStackTest() 
    { 
     // tests simple model presented on https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm 
     var graph_nodes = new List<Vertex>(); 

     var v1 = new Vertex() { Id = 1 }; 
     var v2 = new Vertex() { Id = 2 }; 
     var v3 = new Vertex() { Id = 3 }; 
     var v4 = new Vertex() { Id = 4 }; 
     var v5 = new Vertex() { Id = 5 }; 
     var v6 = new Vertex() { Id = 6 }; 
     var v7 = new Vertex() { Id = 7 }; 
     var v8 = new Vertex() { Id = 8 }; 

     v1.Dependencies.Add(v2); 
     v2.Dependencies.Add(v3); 
     v3.Dependencies.Add(v1); 
     v4.Dependencies.Add(v3); 
     v4.Dependencies.Add(v5); 
     v5.Dependencies.Add(v4); 
     v5.Dependencies.Add(v6); 
     v6.Dependencies.Add(v3); 
     v6.Dependencies.Add(v7); 
     v7.Dependencies.Add(v6); 
     v8.Dependencies.Add(v7); 
     v8.Dependencies.Add(v5); 
     v8.Dependencies.Add(v8); 

     graph_nodes.Add(v1); 
     graph_nodes.Add(v2); 
     graph_nodes.Add(v3); 
     graph_nodes.Add(v4); 
     graph_nodes.Add(v5); 
     graph_nodes.Add(v6); 
     graph_nodes.Add(v7); 
     graph_nodes.Add(v8); 

     var tcd = new TarjanCycleDetectStack(); 
     var cycle_list = tcd.DetectCycle(graph_nodes); 

     Assert.IsTrue(cycle_list.Count == 4); 
    } 

मैं वर्टेक्स वस्तु के लिए एक आईडी संपत्ति जोड़ा तो यह देखने के लिए क्या किया जा रहा है आसान है, यह नहीं ' कड़ाई से जरूरी नहीं है। मैंने कुछ कोड को थोड़ा साफ़ कर दिया, लेखक पृष्ठ छद्म कोड से नामकरण का उपयोग कर रहा था, जो तुलना के लिए अच्छा है, लेकिन यह बहुत जानकारीपूर्ण नहीं था।