In C#, come trovare la catena di dipendenza circolare?

Question

Questo errore si verifica in genere quando un progetto di distribuzione contiene gli output di progetto di un secondo progetto di distribuzione e il secondo progetto contiene gli output del primo progetto.

Ho un metodo che controlla la dipendenza circolare. In input, abbiamo un dizionario che contiene, ad esempio, <"A", < "B", "C" >> e <"B", < "A", "D" >>, ciò significa che A dipende da B e C e abbiamo una dipendenza circolare con A->B.

Ma di solito abbiamo una situazione più complessa, con una catena di dipendenza. Come modificare questo metodo per trovare una catena di dipendenze? Ad esempio, voglio avere una variabile che contenga la catena A->B->A, piuttosto che la classe A ha un conflitto con la classe B.

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

Answer 1

Un modo semplice per trovare i cicli in un grafico consiste nell'utilizzare un algoritmo di colorimetria ricorsiva con profondità in primo luogo in cui i nodi sono contrassegnati come "visitanti" o "visitati". Se, quando visiti un nodo, trovi che è già nello stato "in visita", hai un ciclo. I nodi contrassegnati come "visitati" possono essere saltati. Per esempio:

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

Quindi, è possibile utilizzare le cose come:

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

Aggiornamento

La tua domanda è stata aggiornata per richiedere il "algoritmo più efficiente" per la ricerca di dipendenze cicliche. Il codice nella risposta originale è ricorsivo, quindi c'è una possibilità di uno StackOverflowException per catene di dipendenze con migliaia di livelli profondi. Ecco una versione non ricorsiva con una variabile di stack esplicito:

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

Questo dovrebbe essere ragionevolmente efficiente a N*log(N) + E dove N è il numero di nodi e E è il numero di spigoli. Il Log(N) proviene dalla costruzione della tabella hash visited e potrebbe essere eliminato rendendo ogni nodo che ricorda il suo . Questo sembra abbastanza performante; nella seguente di collaudo, il tempo per trovare 17897 cicli di lunghezza media 4393 a 10000 nodi con 125603 dipendenze totale è di circa 10,2 secondi:

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

Creare un dizionario con tutte le dipendenze dirette di ciascuno degli input. Per ognuno di questi, aggiungi tutte le dipendenze indirette univoche (ad esempio vai su ciascuna delle dipendenze dell'elemento specificato e se non esiste per il genitore, aggiungilo). Ripeti finché apporti almeno una modifica al dizionario. Se c'è un elemento che ha esso stesso nelle sue dipendenze, è una dipendenza ciclica :)

Questo è relativamente inefficiente, ovviamente, ma è abbastanza semplice e facile da capire. Se stavate creando un compilatore, probabilmente dovreste semplicemente creare un grafico diretto di tutte le dipendenze e cercare i percorsi in questo: potete trovare molti algoritmi pronti per trovare un percorso in un grafico diretto.

Answer 3

ordinamento topologico è il modo per farlo. Ho un'implementazione in Vb.net here