我应该如何解决 "flat" 数据结构中的逻辑依赖关系？

Question

我目前有一个 Dictionary<string, List<string> 或依赖项。

键是属性名称，值是依赖属性列表。

这是一个简单的例子：

{key: "a", value: ["b", "d"]},
{key: "b", value: null},
{key: "c", value: ["a"]},
{key: "d", value: ["b", "e", "f"]},
{key: "e", value: null},
{key: "f", value: null}

first 级别依赖项如下所示：

a -> b,d
b -> nothing
c -> a
d -> b,e,f
e -> nothing
f -> nothing

找到第一级依赖关系后，second 级依赖关系将如下所示：

a -> b,d,e,f (d has a dependency to e and f).
b -> nothing
c -> a,b,d (a has a dependency to b and d).
d -> b,e,f
e -> nothing
f -> nothing

third 和最后一级（在这个案例中）看起来像：

a -> b,d,e,f
b -> nothing
c -> a,b,d,e,f
d -> b,e,f
e -> nothing
f -> nothing

现在我的词典比我在这个例子中显示的条目多得多（超过一千）。

我的想法是做一些类似于 angularjs 的摘要。我会创建一个阈值，比如说 10 或 20 运行s。在每个运行中，我将检查每个属性依赖项并更新模型。如果至少有一次更新，则执行递归调用。

我很确定这是一个 "known problem" 更好的方法。

无论如何：

我该如何解决这个问题？
我如何知道我需要迭代的级别数，直到我不再有依赖项。
我如何知道是否存在循环依赖？我有很多数据，很难分析？

Answer 1

你只需要写几个递归算法。看这里：

internal static class Program
{
    private static Dictionary<string, List<string>> _dependencies;

    static void Main(string[] args)
    {
        _dependencies = new Dictionary<string, List<string>>
        {
            {"a", new List<string>{"b","d"}},
            {"b", new List<string>()},
            {"c", new List<string>{"a"}},
            {"d", new List<string>{"b","e","f"}},
            {"e", new List<string>()},
            {"f", new List<string>()}
        };
        Console.WriteLine(string.Join(",", DeepWalkDependencies("a", new HashSet<string>())));
        Console.ReadLine();
    }

    static IEnumerable<string> DeepWalkDependencies(string key, HashSet<string> alreadyVisitedKeys)
    {
        foreach (var d in _dependencies[key])
        {
            if (alreadyVisitedKeys.Add(d))
            {
                yield return d;
                foreach (var dd in DeepWalkDependencies(d, alreadyVisitedKeys))
                {
                    yield return dd;
                }
            }
        }
    }
}

检测循环依赖可以类似地实现。您需要 List<string> currentPath 而不是 HashSet<string> alreadyVisitedKeys ，它将在每次调用递归函数之前重新创建。实现这个算法是一个很好的练习。享受吧！

我应该如何解决 "flat" 数据结构中的逻辑依赖关系？

How should I resolve logic dependencies I have in a "flat" data structure?

c#

dependencies