找到一個集合中的循環依賴關係c＃

Question

我收集了一個DataItem類。

的DataItem：PropertyRefItem店REF到DataItem可能是同一個集合。

public class DataItem 
{ 
    public int ID { get; set; } 
    public string Name { get; set; } 
    public DataItem RefItem { get; set; } 
} 

收藏：

private List<DataItem> dataitems; 

    public List<DataItem> DataItems 
    { 
     get { return dataitems; } 
     set { dataitems = value; } 
    } 

現在我有一個在收集集合中添加數據和驗證數據的兩種方法。

public void AddItem(DataItem item) 
    { 
     DataItems.Add(item); 
    } 

    public bool ValidateDataItems() 
    { 
     //Logic for circular reference 
     // 
     return true; 
    } 

我想要一個驗證方法中的算法來檢查我的collection中是否有任何循環依賴。以下是我的無效數據。由於item3再次由item1指向。

 var item1 = new DataItem() {ID=1,Name="First Item",RefItem =null}; 
     var item2 = new DataItem() { ID = 1, Name = "First Item", RefItem = item1 }; 
     var item3 = new DataItem() { ID = 1, Name = "First Item", RefItem = item2 }; 
     item1.RefItem = item3; 
     AddItem(item1); 
     AddItem(item2); 
     AddItem(item3); 

如果項目被添加到集合像Item1-> ITEM2，item2->項目3，item3-> ITEM1或其中一類的ref項指向後面的任何其他可能的組合。我想驗證方法返回false。

這是一個循環依賴問題，但我找不到任何具體的算法在c＃中這樣做。

Answer 1

嘗試是這樣的solution：

public class DataItem 
{ 
    public int ID { get; set; } 
    public string Name { get; set; } 
    public DataItem RefItem { get; set; } 
}  

public class Checker 
{ 
    public static bool Check(DataItem item) 
    { 
     var chain = new Dictionary<DataItem, DataItem>(); 
     chain.Add(item, null); 
     try 
     { 
      ProcessNodes(chain, item); 
      return true; 
     } 
     catch (ArgumentException) 
     { 
      return false; 
     } 
    } 

    private static void ProcessNodes(Dictionary<DataItem, DataItem> chain, DataItem item) 
    { 
     if (item.RefItem != null) 
     {     
      chain.Add(item.RefItem, null); 
      ProcessNodes(chain, item.RefItem); 
     } 
    } 

    public static bool ValidateDataItems(List<DataItem> items) 
    { 
     foreach(var item in items) 
      if(!Check(item)) 
       return false; 
     return true;     
    } 
} 

public static void Main() 
{ 
    var item1 = new DataItem() { ID = 1, Name = "First Item", RefItem = null }; 
    var item2 = new DataItem() { ID = 1, Name = "First Item", RefItem = item1 }; 
    var item3 = new DataItem() { ID = 1, Name = "First Item", RefItem = item2 }; 
    item1.RefItem = item3; 

    Console.WriteLine(Checker.Check(item1)); 
    item1.RefItem = null; 
    Console.WriteLine(Checker.Check(item1)); 

    //Sample how to check all existing items  
    Console.WriteLine(Checker.ValidateDataItems(new List<DataItem>{item1, item2, item3}) ? "items is OK" : "One or more items have dependency");   
}