Trợ giúp phát hiện chu kỳ Tarjan C#

Question

Đây là một C# thực hiện việc phát hiện chu trình của tarjan.

Thuật toán được tìm thấy ở đây: 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); 
      } 

     } 

Lưu ý một DepGraph chỉ là một danh sách các Vertex. và Vertex có danh sách các Vertex khác đại diện cho các cạnh. Đồng thời chỉ mục và liên kết được khởi tạo thành -1

EDIT: Làm việc này ... Tôi vừa giải thích sai kết quả.

Answer 1

Điều trên thực sự chính xác, tôi không hiểu thành phần được kết nối mạnh mẽ là gì. Tôi đã mong đợi hàm trả về một danh sách rỗng của các thành phần được kết nối mạnh mẽ, nhưng nó đã trả về một danh sách các nút đơn.

Tôi tin rằng những điều trên đang hoạt động. Hãy sử dụng nếu bạn cần!

Answer 2

Kể từ năm 2008, thuật toán nhanh đã hỗ trợ thuật toán này. Xem lớp StronglyConnectedComponentsAlgorithm để triển khai hoặc phương pháp AlgorithmExtensions.StronglyConnectedComponents cho lối tắt sử dụng.

Ví dụ:

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

Ví dụ trình bày ở trên trong câu hỏi không phải là chức năng bất cứ ai nên muốn nhanh chóng chơi với nó. Cũng lưu ý rằng nó là dựa trên stack, mà sẽ kích nổ ngăn xếp của bạn nếu bạn đưa ra bất cứ điều gì nhưng tầm thường nhất của đồ thị. Dưới đây là một ví dụ làm việc với một đơn vị kiểm tra rằng các mô hình đồ thị trình bày trên trang wikipedia 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); 
    } 

tôi đã thêm một tài sản Id đến đối tượng Vertex vì vậy nó rất đơn giản để xem những gì đang được thực hiện, nó isn' t cần thiết. Tôi cũng làm sạch một số mã một chút, tác giả đã sử dụng đặt tên từ trang giả mã, đó là tốt để so sánh, nhưng nó không phải là rất nhiều thông tin.