Optimal detection of circular reference in object (currently brute forcing)

Question

I have a Product object, which can depend on other products.

This dependency information is stored in a ServiceTemplate object.

These dependencies can be chained (i use the arrow to indicate that 3 depends on 2, and 2 depends on 1):

1 <= 2 <= 3

I need to prevent circular references, where with the above 1 could be set to depend on 3 this causing a loop.

This is hashed up from how i think it may work but is brute forcing the solution - what would be the optimal algorithm approach or is this already the best way?

class Program
{
    class Product
    {
        public Product(int id)
        {
            this.id = id;
        }

        private readonly int id;

        public int Id { get { return this.id; } }
    }

    class ServiceTemplate
    {
    // stores the list of other products that a product depends on
        Dictionary<int, List<int>> relationships = new Dictionary<int, List<int>>();

        public void SetRequires(Product on, Product requires)
        {
            if (WouldCauseCircularDepdndency(on.Id, requires.Id) == true)
                throw new ArgumentException("circular dependencies not allowed");

            List<int> list = null;
            this.relationships.TryGetValue(on.Id, out list);

            if(list==null)
            {
                list = new List<int>();
                this.relationships.Add(on.Id, list);
            }

            list.Add(requires.Id);
        }

        private bool WouldCauseCircularDepdndency(int on, int requires)
        {
            // get relationships of product we will depend on
            List<int> list = null;                    
            this.relationships.TryGetValue(requires, out list);

            if (list == null)
            {
                return false;
            }
            else if (list.Contains(on))
            {
                return true;
            }
            else
            {
                foreach (var id in list)
                {
                    // traverse each child recursively
                    if (WouldCauseCircularDepdndency(on, id))
                        return true;
                }
            }

            return false; // if we got this far, no circular references detected
        }
    }

    static void Main(string[] args)
    {
        var windows = new Product(1);
        var linux = new Product(2);
        var mySql = new Product(3);
        var ms_sql = new Product(4);
        var cluster = new Product(5);
        var other = new Product(6);

        var config = new ServiceTemplate();
        config.SetRequires(mySql, windows); // mySql requires windows
        config.SetRequires(mySql, linux); // mySql requires linux
        config.SetRequires(ms_sql, windows); // microsoft sql requires windows
        config.SetRequires(cluster, ms_sql); // cluster requires microsoft sql
        config.SetRequires(other, cluster);

        // this should throw an exception due to circular dependency
        config.SetRequires(windows, other);

        /* at this point the config relationships dictionary is as follows:

        3 => 1,2
        4 => 1
        5 => 4
        5 => 6
        1 => 6

        */
    }
}

Answer 1

I ended up using the QuickGraph nuget package and an AdjacencyGraph<int,Edge<int>>, once the relationship is added i try and to a TopologicalSort() as advised by @Vesi:

class Program
{
    class Product
    {
        public Product(int id)
        {
            this.id = id;
        }

        private readonly int id;

        public int Id { get { return this.id; } }
    }

    class ServiceTemplate
    {
        // stores the list of other products that a product depends on
        AdjacencyGraph<int, Edge<int>> relationshipGraph = new AdjacencyGraph<int, Edge<int>>();

        public void SetRequires(Product on, Product requires)
        {
            var toAdd = new Edge<int>(on.Id, requires.Id);
            this.relationshipGraph.AddVerticesAndEdge(toAdd);

            try
            {
                var list = this.relationshipGraph.TopologicalSort();
            }
            catch (NonAcyclicGraphException)
            {
                this.relationshipGraph.RemoveEdge(toAdd);
                throw new ArgumentException("Circular dependencies not allowed");
            }
        }
    }

    static void Main(string[] args)
    {
        var windows = new Product(1);
        var linux = new Product(2);
        var mySql = new Product(3);
        var ms_sql = new Product(4);
        var cluster = new Product(5);
        var other = new Product(6);

        var config = new ServiceTemplate();
        config.SetRequires(mySql, windows); // mySql requires windows
        config.SetRequires(mySql, linux); // mySql requires linux
        config.SetRequires(ms_sql, windows); // microsoft sql requires windows
        config.SetRequires(cluster, ms_sql); // cluster requires microsoft sql
        config.SetRequires(other, cluster);

        // this should throw an exception due to circular dependency
        config.SetRequires(windows, other);
    }
}

Answer 2

You could try topological sorting. If it can be constructed, you have no circular dependency. Otherwise, you have a cycle.