In C#, wie findet man eine Kette von Kreisabhängigkeiten?

Question

Dieser Fehler tritt normalerweise auf, wenn ein Bereitstellungsprojekt die Projektausgaben eines zweiten Bereitstellungsprojekts enthält und das zweite Projekt die Ausgaben des ersten Projekts enthält.

Ich habe eine Methode, die kreisförmige Abhängigkeit überprüfen. In der Eingabe haben wir ein Wörterbuch, das zum Beispiel <"A", < "B", "C" >> und <"B", < "A", "D" >> enthält, das bedeutet, dass A von B und abhängt und wir haben zirkuläre Abhängigkeit mit A->B.

Aber normalerweise haben wir eine komplexere Situation mit einer Abhängigkeitskette. Wie ändert man diese Methode, um eine Abhängigkeitskette zu finden? Zum Beispiel möchte ich eine Variable haben, die die Kette A->B->A enthält, statt der Klasse A einen Konflikt mit der Klasse B.

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

Answer 1

Ein einfacher Weg, um Zyklen in einem Graphen zu finden, ist die Verwendung eines rekursiven Tiefen-zuerst-Graph-Farbalgorithmus, in dem Knoten als "Besuch" oder "Besuch" markiert sind. Wenn Sie beim Besuch eines Knotens feststellen, dass er sich bereits im Status "Besuch" befindet, haben Sie einen Zyklus. Knoten, die als "besucht" gekennzeichnet sind, können übersprungen werden. Zum Beispiel:

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

Dann könnten Sie es mögen verwenden:

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

aktualisieren

Ihre Frage wurde aktualisiert, für die Suche nach zyklischen Abhängigkeiten der „effizientesten Algorithmus“ zu beantragen. Der Code in der ursprünglichen Antwort ist rekursiv, also gibt es eine Wahrscheinlichkeit von StackOverflowException für Abhängigkeitsketten Tausende von Ebenen tief. Hier ist eine nicht-rekursive Version mit einer expliziten Stapelvariable:

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

Dies sollte einigermaßen effizient sein bei N*log(N) + E wo N die Anzahl der Knoten und E ist die Anzahl der Kanten. Die Log(N) stammt aus dem Aufbau der Hash-Tabelle visited und könnte eliminiert werden, indem jeder Knoten sich an seine erinnern. Dies scheint einigermaßen performant zu sein; im folgenden Test harness, zu der Zeit 17.897 Zyklen mit einer durchschnittlichen Länge 4393 in 10000 Knoten mit 125.603 Gesamt Abhängigkeiten zu finden, sind um 10,2 Sekunden:

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

Answer 2

Erstellen Sie ein Wörterbuch mit allen direkten Abhängigkeiten von jedem der Eingänge. Fügen Sie für jedes dieser Elemente alle eindeutigen indirekten Abhängigkeiten hinzu (z. B. gehen Sie über alle Abhängigkeiten des gegebenen Elements, und wenn es nicht für das übergeordnete Element existiert, fügen Sie es hinzu). Wiederholen Sie dies, solange Sie mindestens eine Änderung am Wörterbuch vornehmen. Wenn es ein Element gibt, das sich in seinen Abhängigkeiten befindet, ist es eine zyklische Abhängigkeit :)

Dies ist natürlich relativ ineffizient, aber es ist ziemlich einfach und leicht zu verstehen. Wenn Sie einen Compiler erstellen würden, würden Sie wahrscheinlich nur ein gerichteter Graph aller Abhängigkeiten erstellen und nach Pfaden suchen - Sie können viele fertige Algorithmen finden, um einen Pfad in einem gerichteten Graphen zu finden.

Answer 3

Topologische Art ist die Art und Weise, das zu tun. Ich habe eine Implementierung in Vb.net here