oggetti come ordinare dipendeva da dipendere

Question

Ho una collezione:

List<VPair<Item, List<Item>> dependencyHierarchy; 

Il primo elemento nella coppia è un oggetto (oggetto) e la seconda è una raccolta dello stesso tipo di oggetti che la prima dipende sopra. Voglio ottenere un List<Item> in ordine di dipendenza, quindi non ci sono elementi che dipendono dal primo elemento e così via (nessuna dipendenza ciclica!).

ingresso:

 
Item4 depends on Item3 and Item5 
Item3 depends on Item1 
Item1 does not depend on any one 
Item2 depends on Item4 
Item5 does not depend on any one 

Risultato:

 
Item1 
Item5 
Item3 
Item4 
Item2 

Grazie.

SOLUZIONE:

topologico Assortimento (grazie a Loïc Février per idea)

e

example on C#, example on Java (grazie a xcud per grandi esempi)

Answer 1

esempio perfetto di utilizzare un ordinamento topologico:

http://en.wikipedia.org/wiki/Topological_sorting

Essa vi darà esattamente quello che ti serve.

Answer 2

vorrei rendere questo più facile su me stesso, memorizzando le dipendenze di un elemento all'interno della voce stessa:

public class Item 
{ 
    private List<Item> m_Dependencies = new List<Item>(); 

    protected AddDependency(Item _item) { m_Dependencies.Add(_item); } 

    public Item() 
    { 
    }; // eo ctor 

    public List<Item> Dependencies {get{return(m_Dependencies);};} 
} // eo class Item 

Poi, dato questo si può implementare un ordinamento personalizzato delegato per lista che ordina basa sul fatto che la data Articolo è contenuto all'interno dell'altro lista delle dipendenze:

int CompareItem(Item _1, Item _2) 
{ 
    if(_2.Dependencies.Contains(_1)) 
     return(-1); 
    else if(_1.Dependencies.Contains(_2)) 
     return(1); 
    else 
     return(0); 
} 

Answer 3

Questo è il mio re-implementazione di ordinamento topologico, l'idea si basa su http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html (il codice sorgente di Java portato consuma troppa memoria, controllando 50k oggetti costa 50k * * 50k 4 = 10 GB, che è inaccettabile. Inoltre, ha ancora Java codifica convention alcuni luoghi)

using System.Collections.Generic; 
using System.Diagnostics; 

namespace Modules 
{ 
    /// <summary> 
    /// Provides fast-algorithm and low-memory usage to sort objects based on their dependencies. 
    /// </summary> 
    /// <remarks> 
    /// Definition: http://en.wikipedia.org/wiki/Topological_sorting 
    /// Source code credited to: http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html  
    /// Original Java source code: http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm 
    /// </remarks> 
    /// <author>ThangTran</author> 
    /// <history> 
    /// 2012.03.21 - ThangTran: rewritten based on <see cref="TopologicalSorter"/>. 
    /// </history> 
    public class DependencySorter<T> 
    { 
     //************************************************** 
     // 
     // Private members 
     // 
     //************************************************** 

     #region Private members 

     /// <summary> 
     /// Gets the dependency matrix used by this instance. 
     /// </summary> 
     private readonly Dictionary<T, Dictionary<T, object>> _matrix = new Dictionary<T, Dictionary<T, object>>(); 

     #endregion 


     //************************************************** 
     // 
     // Public methods 
     // 
     //************************************************** 

     #region Public methods 

     /// <summary> 
     /// Adds a list of objects that will be sorted. 
     /// </summary> 
     public void AddObjects(params T[] objects) 
     { 
      // --- Begin parameters checking code ----------------------------- 
      Debug.Assert(objects != null); 
      Debug.Assert(objects.Length > 0); 
      // --- End parameters checking code ------------------------------- 

      // add to matrix 
      foreach (T obj in objects) 
      { 
       // add to dictionary 
       _matrix.Add(obj, new Dictionary<T, object>()); 
      } 
     } 

     /// <summary> 
     /// Sets dependencies of given object. 
     /// This means <paramref name="obj"/> depends on these <paramref name="dependsOnObjects"/> to run. 
     /// Please make sure objects given in the <paramref name="obj"/> and <paramref name="dependsOnObjects"/> are added first. 
     /// </summary> 
     public void SetDependencies(T obj, params T[] dependsOnObjects) 
     { 
      // --- Begin parameters checking code ----------------------------- 
      Debug.Assert(dependsOnObjects != null); 
      // --- End parameters checking code ------------------------------- 

      // set dependencies 
      Dictionary<T, object> dependencies = _matrix[obj]; 
      dependencies.Clear(); 

      // for each depended objects, add to dependencies 
      foreach (T dependsOnObject in dependsOnObjects) 
      { 
       dependencies.Add(dependsOnObject, null); 
      } 
     } 

     /// <summary> 
     /// Sorts objects based on this dependencies. 
     /// Note: because of the nature of algorithm and memory usage efficiency, this method can be used only one time. 
     /// </summary> 
     public T[] Sort() 
     { 
      // prepare result 
      List<T> result = new List<T>(_matrix.Count); 

      // while there are still object to get 
      while (_matrix.Count > 0) 
      { 
       // get an independent object 
       T independentObject; 
       if (!this.GetIndependentObject(out independentObject)) 
       { 
        // circular dependency found 
        throw new CircularReferenceException(); 
       } 

       // add to result 
       result.Add(independentObject); 

       // delete processed object 
       this.DeleteObject(independentObject); 
      } 

      // return result 
      return result.ToArray(); 
     } 

     #endregion 


     //************************************************** 
     // 
     // Private methods 
     // 
     //************************************************** 

     #region Private methods 

     /// <summary> 
     /// Returns independent object or returns NULL if no independent object is found. 
     /// </summary> 
     private bool GetIndependentObject(out T result) 
     { 
      // for each object 
      foreach (KeyValuePair<T, Dictionary<T, object>> pair in _matrix) 
      { 
       // if the object contains any dependency 
       if (pair.Value.Count > 0) 
       { 
        // has dependency, skip it 
        continue; 
       } 

       // found 
       result = pair.Key; 
       return true; 
      } 

      // not found 
      result = default(T); 
      return false; 
     } 

     /// <summary> 
     /// Deletes given object from the matrix. 
     /// </summary> 
     private void DeleteObject(T obj) 
     { 
      // delete object from matrix 
      _matrix.Remove(obj); 

      // for each object, remove the dependency reference 
      foreach (KeyValuePair<T, Dictionary<T, object>> pair in _matrix) 
      { 
       // if current object depends on deleting object 
       pair.Value.Remove(obj); 
      } 
     } 


     #endregion 
    } 

    /// <summary> 
    /// Represents a circular reference exception when sorting dependency objects. 
    /// </summary> 
    public class CircularReferenceException : Exception 
    { 
     /// <summary> 
     /// Initializes a new instance of the <see cref="CircularReferenceException"/> class. 
     /// </summary> 
     public CircularReferenceException() 
      : base("Circular reference found.") 
     {    
     } 
    } 
} 

Answer 4

aver lottato con questo per un po ', ecco il mio tentativo di uno stile di Linq metodo di estensione Tsort:

public static IEnumerable<T> TSort<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle = false) 
{ 
    var sorted = new List<T>(); 
    var visited = new HashSet<T>(); 

    foreach(var item in source) 
     Visit(item, visited, sorted, dependencies, throwOnCycle); 

    return sorted; 
} 

private static void Visit<T>(T item, HashSet<T> visited, List<T> sorted, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle) 
{ 
    if(!visited.Contains(item)) 
    { 
     visited.Add(item); 

     foreach(var dep in dependencies(item)) 
      Visit(dep, visited, sorted, dependencies, throwOnCycle); 

     sorted.Add(item); 
    } 
    else 
    { 
     if(throwOnCycle && !sorted.Contains(item)) 
      throw new Exception("Cyclic dependency found"); 
    } 
} 

Answer 5

un'idea diversa, per casi con un solo "genitore" a seconda:

Invece di deps, si memorizzano i genitori.
Quindi puoi capire molto facilmente se un problema è una dipendenza di qualche altro.
E quindi utilizzare Comparable<T>, che richiederebbe le dipendenze "minore" e la dipendenza "maggiore".
E quindi chiamare semplicemente Collections.sort(List<T>, ParentComparator<T>);

Per uno scenario multi-padre, sarebbe necessaria una ricerca ad albero che comporterebbe un'esecuzione lenta.Ma ciò potrebbe essere risolto da una cache in una forma di matrice di ordinamento A *.

Answer 6

Ho unito l'idea di DMM con l'algoritmo di ricerca approfondita su Wikipedia. Funziona perfettamente per quello di cui avevo bisogno.

public static class TopologicalSorter 
{ 
public static List<string> LastCyclicOrder = new List<string>(); //used to see what caused the cycle 

sealed class ItemTag 
{ 
    public enum SortTag 
    { 
    NotMarked, 
    TempMarked, 
    Marked 
    } 

    public string Item { get; set; } 
    public SortTag Tag { get; set; } 

    public ItemTag(string item) 
    { 
    Item = item; 
    Tag = SortTag.NotMarked; 
    } 
} 

public static IEnumerable<string> TSort(this IEnumerable<string> source, Func<string, IEnumerable<string>> dependencies) 
{ 
    TopologicalSorter.LastCyclicOrder.Clear(); 

    List<ItemTag> allNodes = new List<ItemTag>(); 
    HashSet<string> sorted = new HashSet<string>(StringComparer.OrdinalIgnoreCase); 

    foreach (string item in source) 
    { 
    if (!allNodes.Where(n => string.Equals(n.Item, item, StringComparison.OrdinalIgnoreCase)).Any()) 
    { 
     allNodes.Add(new ItemTag(item)); //don't insert duplicates 
    } 
    foreach (string dep in dependencies(item)) 
    { 
     if (allNodes.Where(n => string.Equals(n.Item, dep, StringComparison.OrdinalIgnoreCase)).Any()) continue; //don't insert duplicates 
     allNodes.Add(new ItemTag(dep)); 
    } 
    } 

    foreach (ItemTag tag in allNodes) 
    { 
    Visit(tag, allNodes, dependencies, sorted); 
    } 

    return sorted; 
} 

static void Visit(ItemTag tag, List<ItemTag> allNodes, Func<string, IEnumerable<string>> dependencies, HashSet<string> sorted) 
{ 
    if (tag.Tag == ItemTag.SortTag.TempMarked) 
    { 
    throw new GraphIsCyclicException(); 
    } 
    else if (tag.Tag == ItemTag.SortTag.NotMarked) 
    { 
    tag.Tag = ItemTag.SortTag.TempMarked; 
    LastCyclicOrder.Add(tag.Item); 

    foreach (ItemTag dep in dependencies(tag.Item).Select(s => allNodes.Where(t => string.Equals(s, t.Item, StringComparison.OrdinalIgnoreCase)).First())) //get item tag which falls with used string 
     Visit(dep, allNodes, dependencies, sorted); 

    LastCyclicOrder.Remove(tag.Item); 
    tag.Tag = ItemTag.SortTag.Marked; 
    sorted.Add(tag.Item); 
    } 
} 
} 

Answer 7

C'è un NuGet per questo.

Per quelli di noi che preferiscono non reinventare la ruota: utilizzare NuGet per installare la libreria QuickGraph .NET, che include molteplici algoritmi per grafi tra cui ordinamento topologico.

Per utilizzarlo, è necessario creare un'istanza di AdjacencyGraph<,> come AdjacencyGraph<String, SEdge<String>>. Quindi, se si includono le estensioni appropriate:

using QuickGraph.Algorithms; 

È possibile chiamare:

var sorted = myGraph.TopologicalSort(); 

per ottenere un elenco di nodi ordinati.

Answer 8

Mi è piaciuta la risposta del DMM, ma si presume che i nodi di input siano foglie (che possono o meno essere quelle previste).

Sto postando una soluzione alternativa utilizzando LINQ che non fa questa ipotesi. Inoltre, questa soluzione utilizza yield return per poter restituire rapidamente le foglie (utilizzando ad esempio TakeWhile).

public static IEnumerable<T> TopologicalSort<T>(this IEnumerable<T> nodes, 
               Func<T, IEnumerable<T>> connected) 
{ 
    var elems = nodes.ToDictionary(node => node, 
            node => new HashSet<T>(connected(node))); 
    while (elems.Count > 0) 
    { 
     var elem = elems.FirstOrDefault(x => x.Value.Count == 0); 
     if (elem.Key == null) 
     { 
      throw new ArgumentException("Cyclic connections are not allowed"); 
     } 
     elems.Remove(elem.Key); 
     foreach (var selem in elems) 
     { 
      selem.Value.Remove(elem.Key); 
     } 
     yield return elem.Key; 
    } 
}