当一个部署项目包含第二个部署项目的项目输出时,通常会发生此错误,而第二个项目包含第一个项目的输出.
我有一个检查循环依赖的方法.在输入中,我们有一个字典,其中包含例如<“A”,< “B”,“C”>>和<“B”,< “A”,“D”>,这意味着A取决于B和C,并且我们具有与A-> B的循环依赖性. 但通常我们有一个更加复杂的情况,有一连串的依赖.
如何修改这个方法找到一个依赖链？例如,我想要一个包含链A-> B-> A的变量,而不是类A与类B有冲突.
private void FindDependency(IDictionary<string,IEnumerable<string>> serviceDependence)
解决方法
在图中找到循环的简单方法是使用递归深度优先图形着色算法,其中节点被标记为“访问”或“访问”.如果在访问节点时发现它已经处于“访问”状态,那么你有一个循环.标记为“已访问”的节点可以跳过.例如：
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,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>(),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);
更新
您的问题已更新,以请求查找循环依赖关系的“最有效的算法”.原始答案中的代码是递归的,所以有一个StackOverflowException的依赖关系链几千层级的机会.这是一个具有显式堆栈变量的非递归版本：
public static class DependencyExtensions
{
enum VisitState
{
NotVisited,out value))
return value;
return defaultValue;
}
private static void TryPush<T>(T node,Stack<KeyValuePair<T,IEnumerator<T>>> stack,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,VisitState> visited)
{
var stack = new Stack<KeyValuePair<T,IEnumerator<T>>>();
var cycles = new List<List<T>>();
TryPush(root,stack,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,cycles);
}
}
return cycles;
}
public static List<List<T>> FindCycles<T>(this IEnumerable<T> nodes,VisitState>();
foreach (var node in nodes)
cycles.AddRange(FindCycles(node,visited));
return cycles;
}
public static List<List<T>> FindCycles<T,null) ?? Enumerable.Empty<T>());
}
}
这在N * log(N)E处应该是相当有效的,其中N是节点数,E是边数. Log(N)来自构建访问哈希表,可以通过使每个节点记住它的VisitState来消除.这似乎是合理的;在以下测试工具中,找到17897个周期的平均长度4393个10000个节点,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;
}
}
