找到一个集合中的循环依赖关系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");   
}