Использование 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, а grandparent 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)); 
}