Find a circular dependency in a collection c#

Question

I've a collection of DataItem class.

DataItem : Property RefItem stores ref to a DataItem that could be same collection.

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

Collection:

 private List<DataItem> dataitems;

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

Now I have two methods for adding data in the collection and validating data in collection.

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

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

I want a algorithm in validate method to check if there is any circular dependency in my collection.For ex. Below is an invalid data for me. As item3 is again pointed by 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);

If items are added to collection like Item1->item2,item2-> item3,item3->item1 or any other possible combination of where a ref item of a class is pointing back. I want validation method to return false.

It's a circular dependency problem but I couldn't find any concrete algorithm to do so in c#.

Couldn't you traverse all references, keeping track of existing references? If a new reference if one you've already encountered, it's circular. — Wai Ha Lee

Slava Utesinov Slava Utesinov · Accepted Answer · 2016-03-28T09:48:48

Try something like this 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");        
}

Find a circular dependency in a collection c#

1 Answers