c# - 检查表达式中的循环依赖

Question

我尝试了很多解决方案，但没有一个给我正确的答案。

我有一个依赖于其他几个变量的变量，它们被称为操作数。有一个这样的变量列表，每个变量都包含一个操作数列表。每次我创建新变量的表达式时，我都想检查是否存在循环依赖，例如

A(或其任何操作数)-> B(或其任何操作数)-> C(或其任何操作数)-> D(或其任何操作数)-> A

到目前为止我已经想出了这个

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

请帮忙。

谢谢:)

Answer 1

如果您将变量视为有向图的节点，并且从每个变量到其操作数都有边，那么这是一个非常标准的问题；您想在此图中找到一个循环。

那么这个 SO 问题应该会有帮助:Best algorithm for detecting cycles in a directed graph