コレクション内の循環依存関係を見つけるC＃

Question

私はDataItemクラスのコレクションを持っています。

のDataItem：PropertyRefItem店が同じコレクションである可能性がありDataItemへのREF。

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; 
    } 

私のコレクションに循環依存性があるかどうかを確認するアルゴリズムをバリデーションメソッドで確認します。以下は私にとって無効なデータです。 item3が再びitem1によってポイントされるとき。 ITEM1またはクラスのREF項目バック指している場合の他の可能な組み合わせのアイテムがItem1-> ITEM2、item2-> ITEM3、item3-ようなコレクションに追加された場合

 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); 

>。検証メソッドが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");   
}