在C#中，如何找到循环依赖链？
In C#, how to find chain of circular dependency?
当一个部署项目包含第二个部署项目的项目输出，而第二个项目包含第一个项目的输出时，通常会发生此错误。
我有一个检查循环依赖的方法。在输入中，我们有一个包含 <"A", < "B", "C" >> 和 <"B", < "A", "D" >> 的字典，这意味着 A 依赖于 B 和 C，我们有循环A->B.
的依赖
但通常情况更复杂，有一系列的依赖关系。
如何修改此方法以找到依赖链？比如我想有一个包含链A->B->A的变量，而不是classA和class有冲突B.
private void FindDependency(IDictionary<string, IEnumerable<string>> serviceDependence)
构建一个包含每个输入的所有直接依赖关系的字典。对于其中的每一个，添加所有唯一的间接依赖项（例如，遍历给定项目的每个依赖项，如果父项不存在，则添加它）。只要您至少对字典进行了一次更改，就重复此操作。如果有一个项目在它的依赖项中有自己，那么它就是一个循环依赖项:)
当然这样效率比较低，但是很简单易懂。如果您正在创建一个编译器，您可能只需构建所有依赖项的有向图，并在其中搜索路径 - 您可以找到许多现成的算法来在有向图中查找路径。
在图中查找循环的一种简单方法是使用递归深度优先图着色算法，其中节点标记为 "visiting" 或 "visited"。如果，当访问一个节点时，发现它已经处于 "visiting" 状态，那么你就有了一个循环。可以跳过标记为 "visited" 的节点。例如：
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>());
}
}
然后，您可以像这样使用它：
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);
更新
您的问题已更新为请求 "most efficient algorithm" 以查找循环依赖项。原始答案中的代码是递归的，因此 WhosebugException 的依赖链有可能达到数千层深。这是一个带有显式堆栈变量的非递归版本：
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>());
}
}
这在 N*log(N) + E 处应该相当有效，其中 N 是节点数，E 是边数。 Log(N) 来自构建 visited 散列 table 并且可以通过让每个节点记住它的 VisitState 来消除。这似乎是合理的表现；在下面的测试工具中，在 10000 个节点中找到平均长度为 4393 的 17897 个循环，总依赖项为 125603 的时间约为 10.2 秒：
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;
}
}
拓扑排序是做到这一点的方法。我在 Vb.net here
中有一个实现
当一个部署项目包含第二个部署项目的项目输出，而第二个项目包含第一个项目的输出时，通常会发生此错误。
我有一个检查循环依赖的方法。在输入中，我们有一个包含 <"A", < "B", "C" >> 和 <"B", < "A", "D" >> 的字典，这意味着 A 依赖于 B 和 C，我们有循环A->B.
但通常情况更复杂，有一系列的依赖关系。
如何修改此方法以找到依赖链？比如我想有一个包含链A->B->A的变量，而不是classA和class有冲突B.
private void FindDependency(IDictionary<string, IEnumerable<string>> serviceDependence)
构建一个包含每个输入的所有直接依赖关系的字典。对于其中的每一个，添加所有唯一的间接依赖项（例如，遍历给定项目的每个依赖项，如果父项不存在，则添加它）。只要您至少对字典进行了一次更改，就重复此操作。如果有一个项目在它的依赖项中有自己，那么它就是一个循环依赖项:)
当然这样效率比较低，但是很简单易懂。如果您正在创建一个编译器，您可能只需构建所有依赖项的有向图，并在其中搜索路径 - 您可以找到许多现成的算法来在有向图中查找路径。
在图中查找循环的一种简单方法是使用递归深度优先图着色算法，其中节点标记为 "visiting" 或 "visited"。如果，当访问一个节点时，发现它已经处于 "visiting" 状态，那么你就有了一个循环。可以跳过标记为 "visited" 的节点。例如：
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>());
}
}
然后，您可以像这样使用它：
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);
更新
您的问题已更新为请求 "most efficient algorithm" 以查找循环依赖项。原始答案中的代码是递归的，因此 WhosebugException 的依赖链有可能达到数千层深。这是一个带有显式堆栈变量的非递归版本：
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>());
}
}
这在 N*log(N) + E 处应该相当有效，其中 N 是节点数，E 是边数。 Log(N) 来自构建 visited 散列 table 并且可以通过让每个节点记住它的 VisitState 来消除。这似乎是合理的表现；在下面的测试工具中，在 10000 个节点中找到平均长度为 4393 的 17897 个循环，总依赖项为 125603 的时间约为 10.2 秒：
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;
}
}
拓扑排序是做到这一点的方法。我在 Vb.net here
中有一个实现