1

我正在寻找一种更好的方法来递归可能具有循环依赖关系的项目。目前，我传递了一个已处理项目的列表，以便不再处理它们，但这可能不是最好的方法。

这是我目前正在做的事情：

        /// <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，但这也不是必需的。有什么建议么？我认为必须存在一些经典算法来处理这个问题，但我找不到它。

4

4 回答 4

1

您要做的基本上是遍历连接图的所有节点。您的 AllUsedOwnedItemsToBeIncluded 属性是连接到当前节点的节点列表。

您可以在这里查看一些可能有帮助的图遍历算法。

您的算法是进行图遍历的一种方法。您必须遍历每个节点并保留已访问节点的列表，以免两次访问他。

另一种减少遍历次数的算法可以是：

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 将包含您需要的内容。使用哈希集/字典而不是列表将提高性能

于 2016-06-03T12:50:36.823 回答
1

该算法可以提取到一个类中，使您的代码更整洁并摆脱那个臭的静态字段。

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);
    }
}
于 2016-06-03T13:14:14.167 回答
1

你可以实现这样的事情：

  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);
于 2016-06-03T13:19:56.553 回答
0

这是我对文森特算法的实现：

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

同样，缓存只是为了提高性能，对算法来说并不是必需的。

于 2016-06-03T14:43:57.777 回答