Как перезаписать элементы, имеющие циклические зависимости

Question

Я ищу лучший способ рекурсии элементов, которые могут иметь циклические зависимости. В настоящее время я передаю список уже обработанных элементов, чтобы не обрабатывать их снова, но это, вероятно, не лучший способ сделать это.

Вот что я сейчас делаю:

---

 /// <summary> 
    /// caching dependencies in order to increase performance 
    /// </summary> 
    private static readonly IDictionary<string, IEnumerable<OwnedItem>> dependencies 
     = new Dictionary<string, IEnumerable<OwnedItem>>(); 

     /// <summary> 
    /// recursively find OwnedItem this oi depends upon 
    /// in order to correctly handle cyclic dependencies, already considered 
    /// dependencies need to be supplied as well (can be null or empty) 
    /// </summary> 
    /// <param name="oi"></param> 
    /// <param name="parentDeps"></param> 
    /// <returns></returns> 
    private static IEnumerable<OwnedItem> GetDependencies(
     OwnedItem oi, 
     IEnumerable<OwnedItem> parentDeps) 
    { 
     if (null == oi) 
     { 
      return Enumerable.Empty<OwnedItem>(); 
     } 
     if (dependencies.ContainsKey(oi.UniqueId)) 
     { 
      return dependencies[oi.UniqueId]; 
     } 
     var comparer = new TCObjectComparer<OwnedItem>(); 
     var result = new HashSet<OwnedItem>(comparer); 
     result.Add(oi); 
     result.UnionWith(parentDeps ?? Enumerable.Empty<OwnedItem>()); 
     foreach (var oi2 in oi.AllUsedOwnedItemsToBeIncluded.Except(
       result, comparer)) 
     { 
      result.UnionWith(GetDependencies(oi2, result)); 
     } 
     dependencies[oi.UniqueId] = result; 
     return result; 
    } 

---

элементы находятся типа «OwnedItem» и сохранить список (IEnumerable<OwnedItem>) своих прямых зависимостей в собственности AllUsedOwnedItemsToBeIncluded, но в основном это должен применяться всякий раз, когда «элементы» сохраняют список «элементов», где могут возникать циклические зависимости. Использование словаря просто позволяет избежать одного и того же вычисления более одного раза; это не существенно. Кроме того, необходим только один экземпляр TCObjectComparer, но это также не является существенным. Любые предложения? Я думаю, что для этого должен существовать какой-то классический алгоритм, но я не могу его найти.

Answer 1

То, что вы пытаетесь сделать, в основном проходит через все узлы связного графа. Свойство AllUsedOwnedItemsToBeIncluded - это список узлов, подключенных к вашему текущему узлу.

Вы можете посмотреть здесь, чтобы найти graph traversal algorithms, который может помочь.

Алгоритм является одним из способов совершения обхода графика. Вам нужно будет пройти через каждый узел и сохранить список посещенных узлов, чтобы не посещать его дважды.

Еще один алгоритм, который уменьшает количество прохождений может быть:

list nodesToExplore; 
list exploredNodes; 
nodesToExplore.add(startNode); 

for all node in nodesToExplore 
{ 
    nodesToExplore.remove(node); 
    exploredNodes.add(node); 

    for all child in node.childs 
    { 
     if(child not in exploredNodes) 
      nodesToExplore.add(child); 
    } 
} 

Когда заканчивается, exploredNodes будет содержать то, что вам нужно. Использование hashset/dictionnary вместо списка улучшит производительность.

Answer 2

Алгоритм может быть извлечен в класс, сохраняя ваш код более аккуратным и избавиться от этого вонючего статического поля.

private static IEnumerable<T> GetDependencies(T oi) 
{ 
    return new FlattenedCircularTree<OwnedItem>(oi, o => o.AllUsedOwnedItemsToBeIncluded) 
     .AllNodes(); 
} 

И общий алгоритм реализован следующим образом:

public sealed class FlattenedCircularTree<T> 
{ 
    private readonly T _root; 
    private readonly Func<T, IEnumerable<T>> _getChildren; 
    private readonly HashSet<T> _visited = new HashSet<T>(); 
    private readonly List<T> _nodes = new List<T>(); 

    public FlattenedCircularTree(T root, Func<T, IEnumerable<T>> getChildren) 
    { 
     _root = root; 
     _getChildren = getChildren; 
    } 

    public IEnumerable<T> AllNodes() 
    { 
     FindNodes(_root); 
     return _nodes; 
    } 

    private void FindNodes(T current) 
    { 
     if (!_visited.Add(current)) 
      return; 
     _nodes.Add(current); 
     IEnumerable<T> children = _getChildren(current); 
     if (children != null) 
      foreach (T child in children) 
       FindNodes(child); 
    } 
} 

Answer 3

Вы можете реализовать что-то вроде этого:

public static partial class LinqGraph { 
    public static IEnumerable<T> SelectBreadthFirst<T>(this IEnumerable<T> source, 
                 Func<T, IEnumerable<T>> children) { 
     if (Object.ReferenceEquals(null, source)) 
     throw new ArgumentNullException(nameof(source)); 
     else if (Object.ReferenceEquals(null, children)) 
     throw new ArgumentNullException(nameof(children)); 

     HashSet<T> proceeded = new HashSet<T>(); 

     Queue<IEnumerable<T>> queue = new Queue<IEnumerable<T>>(); 

     queue.Enqueue(source); 

     while (queue.Count > 0) { 
     IEnumerable<T> src = queue.Dequeue(); 

     if (Object.ReferenceEquals(null, src)) 
      continue; 

     foreach (var item in src) 
      if (proceeded.Add(item)) { 
      yield return item; 

      queue.Enqueue(children(item)); 
      } 
     } 
    } 
    } 

И затем использовать его

var items = new OwnedItem[] {startItem} // root nodes 
    //TODO: provide a rule of returning children on given parent 
    .SelectBreadthFirst(parent => parent.AllUsedOwnedItemsToBeIncluded); 

Answer 4

Вот мой реализация алгоритма Винсента :

---

private static readonly TCObjectComparer<OwnedItem> comparer 
     = new TCObjectComparer<OwnedItem>(); 

    /// <summary> 
    /// caching dependencies in order to increase performance 
    /// </summary> 
    private static readonly IDictionary<string, IEnumerable<OwnedItem>> dependencies 
     = new Dictionary<string, IEnumerable<OwnedItem>>(); 

    /// <summary> 
    /// recursively find OwnedItems this oi depends upon 
    /// see http://stackoverflow.com/questions/37614469/how-to-recurse-over-items-having-cyclic-dependencies 
    /// </summary> 
    /// <param name="oi"></param> 
    /// <returns></returns> 
    private static IEnumerable<OwnedItem> GetDependencies(OwnedItem oi) 
    { 
     if (null == oi) 
     { 
      return Enumerable.Empty<OwnedItem>(); 
     } 
     if (dependencies.ContainsKey(oi.UniqueId)) 
     { 
      return dependencies[oi.UniqueId]; 
     } 
     var resultExploredNodes = new HashSet<OwnedItem>(comparer); 
     var nodesToExplore = new Queue<OwnedItem>(); 
     nodesToExplore.Enqueue(oi); 
     while (nodesToExplore.Count > 0) 
     { 
      var node = nodesToExplore.Dequeue(); 
      resultExploredNodes.Add(node); 
      // add nodes not already visited to nodesToExplore 
      node.AllUsedOwnedItemsToBeIncluded 
       .Except(resultExploredNodes, comparer) 
       .ForEach(n => nodesToExplore.Enqueue(n)); 
     } 
     dependencies[oi.UniqueId] = resultExploredNodes; 
     return resultExploredNodes; 
    } 

---

Опять же, кэширование только там для работы, это не является существенным для алгоритма.