đối tượng Làm thế nào để sắp xếp phụ thuộc bởi sự phụ thuộc

Question

Tôi có một bộ sưu tập:

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

Mục đầu tiên trong cặp là một số đối tượng (item) và thứ hai là một bộ sưu tập cùng loại đối tượng mà người đầu tiên phụ thuộc trên. Tôi muốn nhận được một List<Item> theo thứ tự phụ thuộc, do đó, không có mục nào phụ thuộc vào yếu tố đầu tiên và vân vân (không phụ thuộc vào chu kỳ!).

Input:

 
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 

Kết quả:

 
Item1 
Item5 
Item3 
Item4 
Item2 

Cảm ơn bạn.

SOLUTION:

tôpô Sorting (nhờ Loïc Février cho ý tưởng)

và

example on C#, example on Java (nhờ xcud cho ví dụ tuyệt vời)

Answer 1

Perfect ví dụ để sử dụng một loại topo:

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

Nó sẽ cung cấp cho bạn chính xác những gì bạn cần.

Answer 2

tôi sẽ làm cho điều này dễ dàng hơn về bản thân mình bằng cách lưu trữ các phụ thuộc của một mục trong mục riêng của mình:

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 

Sau đó, đưa ra này bạn có thể thực hiện một tùy chỉnh Sắp xếp giao cho Danh sách rằng loại dựa vào việc trao mục được chứa trong danh sách của người khác phụ thuộc:

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

này là của riêng tái thực hiện của tôi về phân loại tôpô, ý tưởng dựa trên http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html (các mã nguồn Java được chuyển tiêu thụ quá nhiều bộ nhớ, kiểm tra 50k đối tượng chi phí 50k * 50k * 4 = 10 GB không thể chấp nhận được. Bên cạnh đó, nó vẫn có Java mã hóa ước một số nơi)

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

Sau khi vật lộn với điều này trong một thời gian, đây là nỗ lực của tôi tại một LINQ phong cách phương pháp khuyến nông 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

Một ý tưởng khác nhau, ví các trường hợp chỉ có một "phụ huynh" tùy thuộc:

Thay vì chi trả, bạn nên lưu trữ cha mẹ.
Vì vậy, bạn có thể nói rất dễ dàng cho dù vấn đề là sự phụ thuộc của một số khác.
Và sau đó sử dụng Comparable<T>, yêu cầu phụ thuộc "nhỏ hơn" và phụ thuộc "lớn hơn".
Và sau đó chỉ cần gọi Collections.sort(List<T>, ParentComparator<T>);

Đối với kịch bản nhiều phụ huynh, cần tìm kiếm cây sẽ dẫn đến việc thực thi chậm.Nhưng điều đó có thể được giải quyết bằng bộ nhớ đệm dưới dạng ma trận loại A *.

Answer 6

Tôi đã hợp nhất ý tưởng DMM với thuật toán tìm kiếm theo chiều sâu trên Wikipedia. Nó hoạt động hoàn hảo cho những gì tôi cần.

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ó nuget cho rằng.

Đối với những người không muốn phát minh lại bánh xe: hãy sử dụng nuget để cài đặt thư viện .NET QuickGraph, bao gồm nhiều thuật toán đồ thị bao gồm loại topo.

Để sử dụng, bạn cần phải tạo một phiên bản AdjacencyGraph<,> chẳng hạn như AdjacencyGraph<String, SEdge<String>>. Sau đó, nếu bạn bao gồm các phần mở rộng thích hợp:

using QuickGraph.Algorithms; 

Bạn có thể gọi:

var sorted = myGraph.TopologicalSort(); 

Để có được một danh sách các nút được sắp xếp.

Answer 8

Tôi thích câu trả lời của DMM, nhưng giả định rằng các nút đầu vào là lá (có thể hoặc không thể là những gì được mong đợi).

Tôi đăng một giải pháp thay thế bằng LINQ không đưa ra giả định này. Ngoài ra, giải pháp này sử dụng yield return để có thể nhanh chóng trả lại các lá (sử dụng ví dụ: 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; 
    } 
}