如何通过依赖sorting依赖的对象

我有一个集合：

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

对中的第一个项目是某个对象（item），第二个项目是第一个依赖的相同types对象的集合。 我想按照依赖的顺序得到一个List<Item> ，所以没有依赖于第一个元素等等的东西（没有循环依赖！）。

input：

 Item4取决于Item3和Item5
 Item3取决于Item1
 Item1不依赖于任何一个
 Item2取决于Item4 
 Item5不依赖于任何一个 

结果：

项目1
项目5
项目3
项目4
项目2

谢谢。

解：

拓扑sorting （感谢LoïcFévrier的想法）

和

在C＃上的 例子，在Java 上的 例子 （感谢xcud的伟大的例子）

Answer 1

使用拓扑sorting的完美示例：

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

它会给你正是你所需要的。

Answer 2

经过一段时间的努力，这里是我尝试Linq式的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 3

有一个nuget的 。

对于我们这些不想重新发明轮子的人来说：使用nuget安装QuickGraph .NET库，其中包括多种graphicsalgorithm，包括拓扑sorting 。

要使用它，您需要创buildAdjacencyGraph<,>一个实例AdjacencyGraph<,>例如AdjacencyGraph<String, SEdge<String>> 。 那么，如果你包含适当的扩展名：

 using QuickGraph.Algorithms; 

你可以打电话给：

 var sorted = myGraph.TopologicalSort(); 

获取sorting节点的列表。

Answer 4

我喜欢DMM的答案，但它假定input节点是叶子（可能会或可能不是预期的）。

我发布一个使用LINQ的替代解决scheme，不做这个假设。 另外，这个解决scheme使用yield return来快速返回叶子（例如使用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; } } 

Answer 5

这是我自己重新实现的拓扑sorting，这个想法是基于http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html （移植的Java源代码消耗太多的内存，检查50k对象的成本是50k * 50k * 4 = 10GB这是不可接受的，另外还有一些Java编码规范）

 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 6

通过在项目本身中存储项目的依赖关系，我可以让自己更容易：

 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 

然后，给定这个你可以实现一个List的自定义Sort委托，根据给定的Item是否包含在另一个依赖关系列表中进行sorting：

 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 7

一个不同的想法，只有一个“父母”取决于：

而不是代价，你会存储父母。
所以你可以很容易地告诉一个问题是否是其他的依赖关系。
然后使用Comparable<T> ，它会声明依赖关系“较小”，依赖关系“更大”。
然后只需调用Collections.sort( List<T>, ParentComparator<T>);

对于多父scheme，需要进行树search，这会导致执行速度慢。 但是这可以通过A *sortingmatrixforms的caching来解决。

Answer 8

我将DMM的想法与维基百科上的深度优先searchalgorithm合并在一起。 它适用于我所需要的。

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