在C＃中，如何找到循环依赖的链条？ [英] In C#, how to find chain of circular dependency?

问题描述

这个错误通常当一个部署项目包含第二部署项目的项目产出时，第二个项目包含的第一个项目的输出。

我有该检查循环依赖的方法。在输入中，我们有一个包含，例如，℃的字典;A，< B，C>> 和<B，< A，D>> ，这意味着 A 取决于 B 和 C ，我们必须以 A->循环依赖; b

但通常我们有一个更复杂的情况，与依赖链。
如何修改这个方法找到的依赖链？例如，我想有一个包含链可变 A-> B->将，而不是阶级 A 与类 b 的冲突。

 私人无效FindDependency（ IDictionary的<字符串的IEnumerable<串>> serviceDependence）
  

解决方案

一个简单的方式找到一个图形的周期是使用在哪些节点被标记为访问或访问的递归深度优先图着色算法。如果访问一个节点时，你会发现它已经在访问的状态，你有一个周期。标记为已访问节点可以被跳过。例如：

 公共类DependencyExtensions 
 {
枚举VisitState 
 {
 NotVisited，
访问，
拜访
}; 
 
公共静态TValue ValueOrDefault< TKEY的，TValue>（这IDictionary的< TKEY的，TValue>字典，TKEY的关键，TValue设置defaultValue）
 {
 TValue值; 
如果（dictionary.TryGetValue（键，超时值））
返回值; 
返回设置defaultValue; 
} 
 
静态无效DepthFirstSearch< T>（T节点，Func键< T，IEnumerable的< T>>查找，列表< T>家长，字典< T，VisitState>参观考察，名单，LT ;清单< T>>周期）
 {
 VAR状态= visited.ValueOrDefault（节点，VisitState.NotVisited）; 
如果（状态== VisitState.Visited）
的回报; 
，否则如果（状态== VisitState.Visiting）
 {
 //不报告不包括在周期的节点。 
 cycles.Add（parents.Concat（新[] {}节点）SkipWhile（父=方式>！EqualityComparer< T> .Default.Equals（父节点））了ToList（））; 
} 
，否则
 {
访问[节点] = VisitState.Visiting; 
 parents.Add（节点）; 
的foreach（VAR孩子查找（节点））
 DepthFirstSearch（儿童，查找，父母，走访，周期）; 
 parents.RemoveAt（parents.Count  -  1）; 
访问[节点] = VisitState.Visited; 
} 
} 
 
公共静态列表<名单，LT; T>> FindCycles< T>（这个IEnumerable的< T>的节点，Func键< T，IEnumerable的< T>>边）
 {
变种周期=新的List<名单< T>>（）; 
变种走访=新词典< T，VisitState>（）; 
的foreach（在节点VAR节点）
 DepthFirstSearch（节点，边，新的List< T>（），访问周期）; 
回报周期; 
} 
 
公共静态列表<名单，LT; T>> FindCycles< T，TValueList>（这IDictionary的< T，TValueList> listDictionary）
式TValueList：类，IEnumerable的< T> 
 {
返回listDictionary.Keys.FindCycles（键=> listDictionary.ValueOrDefault（键，NULL）?? Enumerable.Empty< T>（））; 
} 
} 
  

然后，你可以使用它，如：

  VAR serviceDependence =新词典<字符串列表<串GT;> 
 {
 {A，新的List<串GT; {A}} 
 {B，新的List<串GT; {C，D}}，
 {D，新的List<串GT; {E}}，
 {E，新的List<串GT; {F，Q}}，
 {F，新的List<串GT; {D}}，
}; 
变种周期= serviceDependence.FindCycles（）; 
的Debug.WriteLine（JsonConvert.SerializeObject（周期，Formatting.Indented））; 
的foreach（在循环周期VAR）
 {
 serviceDependence [周期[cycle.Count  -  2]]删除（循环[cycle.Count  -  1]）。 
} 
 Debug.Assert的（serviceDependence.FindCycles（）计数== 0）; 
  

更新

您的问题已更新要求最有效的算法寻找循环依赖。在原来的答案代码是递归的，所以有一个 StackOverflowException 为依存关系链数千深层次的机会。这里有一个非递归版本明确的堆栈变量：

 公共静态类DependencyExtensions 
 {
枚举VisitState 
 {
 NotVisited，
访问，
拜访
}; 
 
公共静态TValue ValueOrDefault< TKEY的，TValue>（这IDictionary的< TKEY的，TValue>字典，TKEY的关键，TValue设置defaultValue）
 {
 TValue值; 
如果（dictionary.TryGetValue（键，超时值））
返回值; 
返回设置defaultValue; 
} 
 
私有静态无效TryPush< T>（T节点，Func键< T，IEnumerable的< T>>查找，堆叠式和LT; KeyValuePair< T，IEnumerator的< T>>>堆栈，字典< T，VisitState>参观考察，列表与LT;名单< T>>周期）
 {
 VAR状态= visited.ValueOrDefault（节点，VisitState.NotVisited）; 
如果（状态== VisitState.Visited）
的回报; 
，否则如果（状态== VisitState.Visiting）
 {
 Debug.Assert的（stack.Count大于0）; 
无功名单= stack.Select（双= GT; pair.Key）.TakeWhile（父=>！EqualityComparer< T> .Default.Equals（父节点））了ToList（）。 
 list.Add（节点）; 
 list.Reverse（）; 
 list.Add（节点）; 
 cycles.Add（名单）; 
} 
，否则
 {
访问[节点] = VisitState.Visiting; 
 stack.Push（新KeyValuePair< T，IEnumerator的< T>>（节点，查找（节点）.GetEnumerator（）））; 
} 
} 
 
静态列表<名单，LT; T>> FindCycles< T>（T根，Func键< T，IEnumerable的< T>>查找，字典< T，VisitState>参观）
 {
变种堆栈=新的堆栈< KeyValuePair< T，IEnumerator的< T> ;>>（）; 
变种周期=新的List<名单，LT; T>>（）; 
 
 TryPush（根，查找，栈，走访，周期）; 
，而（stack.Count大于0）
 {
变种对= stack.Peek（）; 
如果（pair.Value.MoveNext（）！）
 {
 stack.Pop（）; 
访问[pair.Key] = VisitState.Visited; 
 pair.Value.Dispose（）; 
} 
，否则
 {
 TryPush（pair.Value.Current，查找，堆栈，访问周期）; 
} 
} 
回报周期; 
} 
 
公共静态列表<名单，LT; T>> FindCycles< T>（这个IEnumerable的< T>的节点，Func键< T，IEnumerable的< T>>边）
 {
变种周期=新的List<名单< T>>（）; 
变种走访=新词典< T，VisitState>（）; 
的foreach（在节点VAR节点）
 cycles.AddRange（FindCycles（节点，边参观））; 
回报周期; 
} 
 
公共静态列表<名单，LT; T>> FindCycles< T，TValueList>（这IDictionary的< T，TValueList> listDictionary）
式TValueList：类，IEnumerable的< T> 
 {
返回listDictionary.Keys.FindCycles（键=> listDictionary.ValueOrDefault（键，NULL）?? Enumerable.Empty< T>（））; 
} 
} 
  

本应在 N *日志（N）+ E ，其中 N 是节点的数量和电子是边缘的数目。在日志（N）来自建访问哈希表并且可以通过使每个节点记住它的<$被淘汰C $ C> VisitState 。这似乎是合理的高性能;在下面的测试工具，及时发现平均长度为4393的17897个周期与125603总依赖10000节点大约是10.2秒：

 公共类识别TestClass 
 {
公共静态无效TestBig（）
 {
变种经过= TestBig（10000）; 
的Debug.WriteLine（elapsed.ToString（））; 
} 
 
静态字符串的GetName（int i）以
 {
返回ServiceDependence+ i.ToString（）; 
} 
 
公共静态时间跨度TestBig（诠释计数）
 {
变种serviceDependence =新词典<字符串列表<串>>（）; 
为（INT的iItem = 0;&的iItem LT;计数;的iItem ++）
 {
变种名称=的GetName（的iItem）; 
 //添加几个向前引用。 
表示（中间体IREF =的iItem  -  1; IREF大于0; IREF = IREF / 2）
 serviceDependence.Add（姓名，的GetName（IREF））; 
 //添加一些向后引用。 
如果（的iItem大于0&放大器;及（的iItem％5 == 0））
 serviceDependence.Add（姓名，的GetName（的iItem + 5））; 
} 
 
 //新增一个向后的参考，这将创造出一些极长的周期。 
 serviceDependence.Add（的GetName（1）的GetName（计数 -  1））; 
 
名单，LT;名单<串GT;>循环; 
 
变种秒表=新的秒表（）; 
 stopwatch.Start（）; 
试
 {
周期= serviceDependence.FindCycles（）; 
} 
终于
 {
 stopwatch.Stop（）; 
} 
 
变种经过= stopwatch.Elapsed; 
 
 VAR averageLength = cycles.Average（L =>（双）l.Count）; 
无功总= serviceDependence.Values.Sum（L => l.Count）; 
 
的foreach（在循环周期VAR）
 {
 serviceDependence [周期[cycle.Count  -  2]]删除（循环[cycle.Count  -  1]）; 
} 
 Debug.Assert的（serviceDependence.FindCycles（）计数== 0）; 
 
 Console.WriteLine（的String.Format（找点时间，{0}平均长度循环{1}在{2}与{3}总依赖节点：{4}，cycles.Count ，averageLength，算上，总共经过））; 
到Console.ReadLine（）; 
 System.Environment.Exit（0）; 
 
返回已过; 
} 
} 
  

This error usually occurs when one deployment project contains the project outputs of a second deployment project, and the second project contains the outputs of the first project.

I have a method that check circular dependency. In input, we have a dictionary that contains, for example, <"A", < "B", "C" >> and <"B", < "A", "D" >>, this means that A depends on B and C and we have circular dependency with A->B.

But usually we have a more complex situation, with a chain of dependency. How to modify this method to find a chain of dependency? For example, I want to have a variable that contains chain A->B->A, rather than class A has a conflict with class B.

private void FindDependency(IDictionary<string, IEnumerable<string>> serviceDependence)

解决方案

A simple way to find cycles in a graph is to use a recursive depth-first graph-coloring algorithm in which nodes are marked as "visiting" or "visited". If, when visiting a node, you find it is already in the "visiting" state, you have a cycle. Nodes marked as "visited" can be skipped. For instance:

public class DependencyExtensions
{
    enum VisitState
    {
        NotVisited,
        Visiting,
        Visited
    };

    public static TValue ValueOrDefault<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TKey key, TValue defaultValue)
    {
        TValue value;
        if (dictionary.TryGetValue(key, out value))
            return value;
        return defaultValue;
    }

    static void DepthFirstSearch<T>(T node, Func<T, IEnumerable<T>> lookup, List<T> parents, Dictionary<T, VisitState> visited, List<List<T>> cycles)
    {
        var state = visited.ValueOrDefault(node, VisitState.NotVisited);
        if (state == VisitState.Visited)
            return;
        else if (state == VisitState.Visiting)
        {
            // Do not report nodes not included in the cycle.
            cycles.Add(parents.Concat(new[] { node }).SkipWhile(parent => !EqualityComparer<T>.Default.Equals(parent, node)).ToList());
        }
        else
        {
            visited[node] = VisitState.Visiting;
            parents.Add(node);
            foreach (var child in lookup(node))
                DepthFirstSearch(child, lookup, parents, visited, cycles);
            parents.RemoveAt(parents.Count - 1);
            visited[node] = VisitState.Visited;
        }
    }

    public static List<List<T>> FindCycles<T>(this IEnumerable<T> nodes, Func<T, IEnumerable<T>> edges)
    {
        var cycles = new List<List<T>>();
        var visited = new Dictionary<T, VisitState>();
        foreach (var node in nodes)
            DepthFirstSearch(node, edges, new List<T>(), visited, cycles);
        return cycles;
    }

    public static List<List<T>> FindCycles<T, TValueList>(this IDictionary<T, TValueList> listDictionary)
        where TValueList : class, IEnumerable<T>
    {
        return listDictionary.Keys.FindCycles(key => listDictionary.ValueOrDefault(key, null) ?? Enumerable.Empty<T>());
    }
}

Then, you could use it like:

        var serviceDependence = new Dictionary<string, List<string>>
        {
            { "A", new List<string> { "A" }},
            { "B", new List<string> { "C", "D" }},
            { "D", new List<string> { "E" }},
            { "E", new List<string> { "F", "Q" }},
            { "F", new List<string> { "D" }},
        };
        var cycles = serviceDependence.FindCycles();
        Debug.WriteLine(JsonConvert.SerializeObject(cycles, Formatting.Indented));
        foreach (var cycle in cycles)
        {
            serviceDependence[cycle[cycle.Count - 2]].Remove(cycle[cycle.Count - 1]);
        }
        Debug.Assert(serviceDependence.FindCycles().Count == 0);

Update

Your question has been updated to request the "most efficient algorithm" for finding cyclic dependencies. The code in the original answer is recursive, so there's a chance of a StackOverflowException for dependency chains thousands of levels deep. Here's a non-recursive version with an explicit stack variable:

public static class DependencyExtensions
{
    enum VisitState
    {
        NotVisited,
        Visiting,
        Visited
    };

    public static TValue ValueOrDefault<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TKey key, TValue defaultValue)
    {
        TValue value;
        if (dictionary.TryGetValue(key, out value))
            return value;
        return defaultValue;
    }

    private static void TryPush<T>(T node, Func<T, IEnumerable<T>> lookup, Stack<KeyValuePair<T, IEnumerator<T>>> stack, Dictionary<T, VisitState> visited, List<List<T>> cycles)
    {
        var state = visited.ValueOrDefault(node, VisitState.NotVisited);
        if (state == VisitState.Visited)
            return;
        else if (state == VisitState.Visiting)
        {
            Debug.Assert(stack.Count > 0);
            var list = stack.Select(pair => pair.Key).TakeWhile(parent => !EqualityComparer<T>.Default.Equals(parent, node)).ToList();
            list.Add(node);
            list.Reverse();
            list.Add(node);
            cycles.Add(list);
        }
        else
        {
            visited[node] = VisitState.Visiting;
            stack.Push(new KeyValuePair<T, IEnumerator<T>>(node, lookup(node).GetEnumerator()));
        }
    }

    static List<List<T>> FindCycles<T>(T root, Func<T, IEnumerable<T>> lookup, Dictionary<T, VisitState> visited)
    {
        var stack = new Stack<KeyValuePair<T, IEnumerator<T>>>();
        var cycles = new List<List<T>>();

        TryPush(root, lookup, stack, visited, cycles);
        while (stack.Count > 0)
        {
            var pair = stack.Peek();
            if (!pair.Value.MoveNext())
            {
                stack.Pop();                    
                visited[pair.Key] = VisitState.Visited;
                pair.Value.Dispose();
            }
            else
            {
                TryPush(pair.Value.Current, lookup, stack, visited, cycles);
            }
        }
        return cycles;
    }

    public static List<List<T>> FindCycles<T>(this IEnumerable<T> nodes, Func<T, IEnumerable<T>> edges)
    {
        var cycles = new List<List<T>>();
        var visited = new Dictionary<T, VisitState>();
        foreach (var node in nodes)
            cycles.AddRange(FindCycles(node, edges, visited));
        return cycles;
    }

    public static List<List<T>> FindCycles<T, TValueList>(this IDictionary<T, TValueList> listDictionary)
        where TValueList : class, IEnumerable<T>
    {
        return listDictionary.Keys.FindCycles(key => listDictionary.ValueOrDefault(key, null) ?? Enumerable.Empty<T>());
    }
}

This should be reasonably efficient at N*log(N) + E where N is the number of nodes and E is the number of edges. The Log(N) comes from building the visited hash table and could be eliminated by making each node remember its VisitState. This seems reasonably performant; in the following test harness, the time to find 17897 cycles of average length 4393 in 10000 nodes with 125603 total dependencies is around 10.2 seconds:

public class TestClass
{
    public static void TestBig()
    {
        var elapsed = TestBig(10000);
        Debug.WriteLine(elapsed.ToString());
    }

    static string GetName(int i)
    {
        return "ServiceDependence" + i.ToString();
    }

    public static TimeSpan TestBig(int count)
    {
        var serviceDependence = new Dictionary<string, List<string>>();
        for (int iItem = 0; iItem < count; iItem++)
        {
            var name = GetName(iItem);
            // Add several forward references.
            for (int iRef = iItem - 1; iRef > 0; iRef = iRef / 2)
                serviceDependence.Add(name, GetName(iRef));
            // Add some backwards references.
            if (iItem > 0 && (iItem % 5 == 0))
                serviceDependence.Add(name, GetName(iItem + 5));
        }

        // Add one backwards reference that will create some extremely long cycles.
        serviceDependence.Add(GetName(1), GetName(count - 1));

        List<List<string>> cycles;

        var stopwatch = new Stopwatch();
        stopwatch.Start();
        try
        {
            cycles = serviceDependence.FindCycles();
        }
        finally
        {
            stopwatch.Stop();
        }

        var elapsed = stopwatch.Elapsed;

        var averageLength = cycles.Average(l => (double)l.Count);
        var total = serviceDependence.Values.Sum(l => l.Count);

        foreach (var cycle in cycles)
        {
            serviceDependence[cycle[cycle.Count - 2]].Remove(cycle[cycle.Count - 1]);
        }
        Debug.Assert(serviceDependence.FindCycles().Count == 0);

        Console.WriteLine(string.Format("Time to find {0} cycles of average length {1} in {2} nodes with {3} total dependencies: {4}", cycles.Count, averageLength, count, total, elapsed));
        Console.ReadLine();
        System.Environment.Exit(0);

        return elapsed;
    }
}

这篇关于在C＃中，如何找到循环依赖的链条？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！