Checking Circular dependency in expression

Question

I have tried many solutions but none of dem is giving me a correct answer.

I have a variable which is dependent on few other variables and they are called operands.There is a list of such variables each containing a list of its operands. Everytime I create expression of new variable I want to check the if there if there is a circular dependency like

A (or any of its operands)-> B (or any of its operands)-> C (or any of its operands)-> D(or any of its operands)-> A

so far I have come up wid this

foreach (var newVar in newlyCreatedVars)
            {
                newVar.Rank = 0;
                List<string> tags = newVar.Operands.ToList();
                List<string> temp;
                while (tags.Count > 0)
                {   
                    var dependentVars= newlyCreatedVars.Where(t => tags.Contains(t.Name)).ToList();
                    temp = new List<string>();
                    tags.Clear();
                    temp.AddRange(dependentVars.SelectMany(t => t.Operands).ToArray());
                    if (temp.Count > 0)
                    {
                        newVar.Rank++;
                        tags = temp;
                    }
                    var dep = newlyCreatedVars.Where(t=> newVar .Operands.Contains(t.Name)).ToList();
                    if(dep.Exists(t=> t.Rank > newVar .Rank))
                       return false;
                }
            }

Please help.

Thanks :)

score 4 · Accepted Answer · edited May 23 '17 at 12:13

4

This is a pretty standard problem if you think of your variables as the nodes of a directed graphs, with edges from each variable to its operands; you want to find a cycle in this graph.

Then this SO question should be helpful: Best algorithm for detecting cycles in a directed graph

edited May 23 '17 at 12:13

Community

1
1

answered Aug 01 '12 at 07:53

Danica

28,423
6
90
122

Checking Circular dependency in expression

1 Answers1