Tarjan循環檢測幫助C＃

Question

以下是一個工作的C＃實現的tarjan循環檢測。

的算法在這裏找到： 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年，quickgraph支持這種算法。請參閱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); 
    } 

我添加了一個id屬性設置爲頂點對象，因此它是簡單的看到正在做什麼，它不是」嚴格要求。我還清理了一些代碼，作者使用頁面僞代碼的命名，這是比較好的，但它沒有很多信息。