objetos Cómo ordenar dependido de la dependencia

Question

que tienen una colección:

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

El primer elemento de par es un objeto (elemento) y la segunda es una colección del mismo tipo de objetos que el primero depende en. Quiero obtener un List<Item> en orden de dependencia, por lo que no hay elementos que dependan del primer elemento y así sucesivamente (¡no hay dependencia de ciclo!).

de entrada:

 
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 

Resultado:

 
Item1 
Item5 
Item3 
Item4 
Item2 

Gracias.

Solución:

topológica Clasificación (gracias a Loïc Février para IDEA)

y

example on C#, example on Java (gracias a xcud para grandes ejemplos)

Answer 1

ejemplo perfecto de utilice un tipo topológico:

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

Se le dará exactamente lo que necesita.

Answer 2

Me gustaría hacer esto más fácil en mí mismo mediante el almacenamiento de las dependencias de un elemento dentro del artículo en sí:

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 

Entonces, dado que esto le puede aplicar una costumbre Ordenar delegar para la lista que clasifica en función de si el dado el artículo está contenido dentro de la lista de la otra de las dependencias:

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

Ésta es mi propia re-implementación de clasificación topológica, la idea se basa en http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html (el código fuente de Java portado consume demasiada memoria, comprobando 50k objetos cuesta 50k * 50k * 4 = 10 GB que es inaceptable. Además, todavía tiene Java convenciones de codificación algunos lugares)

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

Después de haber luchado con esto durante un tiempo, aquí está mi intento de un estilo de LINQ método de extensión 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

Una idea diferente, por casos con un solo "padre" en función de:

En lugar de déps, almacenarías a los padres.
Para que pueda ver muy fácilmente si un problema es una dependencia de algún otro.
Y luego use Comparable<T>, que reclamaría las dependencias "menor" y la dependencia "mayor".
Y a continuación, sólo tiene que llamar Collections.sort(List<T>, ParentComparator<T>);

Para el escenario de múltiples padres, sería necesario un árbol de búsqueda que daría lugar a la ejecución lenta.Pero eso podría resolverse con un caché en forma de matriz A *.

Answer 6

que fusionó la idea de DMM con el algoritmo de profundidad de primera búsqueda en Wikipedia. Funciona perfecto para lo que necesitaba.

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

Hay una Nuget para que.

Para aquellos de nosotros que prefieren no reinventar la rueda: utilizar Nuget para instalar la biblioteca QuickGraph NET, que incluye múltiples algoritmos de grafos incluyendo clasificación topológica.

Para usarlo, debe crear una instancia de AdjacencyGraph<,>, como AdjacencyGraph<String, SEdge<String>>. Entonces, si se incluyen las extensiones adecuadas:

using QuickGraph.Algorithms; 

Puede llamar:

var sorted = myGraph.TopologicalSort(); 

Para obtener una lista de nodos ordenados.

Answer 8

me gustó la respuesta de DMM, pero se supone que los nodos de entrada son las hojas (que puede o no ser lo que se espera).

He colgado una solución alternativa con el uso de LINQ que no haga esta suposición. Además, esta solución usa yield return para poder devolver rápidamente las hojas (usando, por ejemplo, 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; 
    } 
}