使用Linq检测循环依赖，字符串属性

Question

想象一个这样的对象

public class ContentType
{
    public string Alias { get; set;}
    public string ParentAlias { get; set;}
}

和这些对象的平面集合

List<ContentType> contentTypes...;

如何使用linq链语法查询来确定集合中是否存在循环引用?

//Example
ContentType #50
Alias: Truck
ParentAlias: Vehicle
ContentType #90
Alias: Vehicle
ParentAlias: Truck

这将是一个循环依赖，它将破坏创建内容类型的代码(它将陷入无限循环遍历父层次结构…)

因此，在处理父/子内容类型之前，我希望首先检测集合中是否存在循环依赖，如果检测到，则停止操作。

Answer 1

所以我们将从两个助手方法开始。首先，我们需要一个方法，当给定该项时，它会产生该项的所有祖先，以及一个获取该项父项的委托:

public static IEnumerable<T> Ancestors<T>(T item, Func<T, T> parentSelector)
{
    while (item != null)
    {
        item = parentSelector(item);
        yield return item;
    }
}

我们还将编写一个方法，通过存储之前生成的所有项并查看每个新项是否在该集合中来确定序列是否重复:

public static bool Repeats<T>(
    this IEnumerable<T> sequence,
    IEqualityComparer<T> comparer = null)
{
    comparer = comparer ?? EqualityComparer<T>.Default;
    var set = new HashSet<T>(comparer);
    foreach (var item in sequence)
        if (!set.Add(item))
            return true;
    return false;
}

从这里，我们可以通过计算每个元素的祖先并确定这些集合是否有重复来确定任何序列是否包含循环:

public static bool ContainsCycles<T>(IEnumerable<T> sequence,
    Func<T, T> parentSelector,
    IEqualityComparer<T> comparer = null)
{
    comparer = comparer ?? EqualityComparer<T>.Default;
    return sequence.Any(item => Ancestors(item, parentSelector).Repeats(comparer));
}

剩下的就是编写一个方法来计算每个项的父项，因为这不是您的类已经支持的操作，这可以通过创建从别名到项的查找然后使用它来完成:

IEnumerable<ContentType> types = CreateContentTypes();
var lookup = types.ToDictionary(type => type.Alias);
bool anyCycles = ContainsCycles(types, type => lookup[type.ParentAlias]);

---

就性能和可能的改进而言，如果您正在处理特别大的树/子树，则可以缓存中间计算的结果。例如，如果我们有节点a，父节点B，和祖父节点C，这是一个根结点，那么在计算a是否在一个循环中时，我们也需要确定B是否在一个循环中。如果我们之前已经确定了B是否在一个循环中，并且缓存了它，我们可以跳过这一步。如果我们不这样做，那么我们可以在为A做循环计算器时缓存它，然后在稍后检查B时不需要再做一次。

这会使代码变得相当复杂，所以如果你没有一个特别大/深度的图，你可以选择不缓存这些中间结果，只选择为每个项重新计算它们:

public static bool IsInCycle<T>(
    this IEnumerable<T> sequence,
    HashSet<T> itemsNotInASequence,
    IEqualityComparer<T> comparer = null)
{
    comparer = comparer ?? EqualityComparer<T>.Default;
    var set = new HashSet<T>(comparer);
    foreach (var item in sequence)
    {
        if (itemsNotInASequence.Contains(item))
            return false;
        else if (!set.Add(item))
            return true;
    }
    itemsNotInASequence.UnionWith(set);
    return false;
}
public static bool ContainsCycles<T>(IEnumerable<T> sequence,
    Func<T, T> parentSelector,
    IEqualityComparer<T> comparer = null)
{
    comparer = comparer ?? EqualityComparer<T>.Default;
    var itemsNotInASequence = new HashSet<T>(comparer);
    return sequence.All(item => Ancestors(item, parentSelector)
        .IsInCycle(itemsNotInASequence));
}