Как сортировать зависимые объекты по зависимостям

борясь с этим некоторое время, вот моя попытка метода расширения Linq style 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" );
    }
}

для этого есть nuget.

для тех из нас, кто предпочитает не изобретать заново колесо: используйте nuget для установки QuickGraph библиотека .NET, которая включает в себя несколько алгоритмов графа, включая топологическая сортировка.

чтобы использовать его, вам нужно создать экземпляр AdjacencyGraph<,> например AdjacencyGraph<String, SEdge<String>>. Затем, если вы включаете соответствующие расширения:

using QuickGraph.Algorithms;

вы можете по телефонам:

var sorted = myGraph.TopologicalSort();

чтобы получить список сортировка узлов.

мне понравился ответ DMM, но он предполагает, что входные узлы-это листья (которые могут быть или не быть тем, что ожидается).

я публикую альтернативное решение с использованием LINQ, которое не делает этого предположения. Кроме того, это решение использует 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;
    }
}

Это моя собственная повторная реализация топологической сортировки, идея основана на 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.")
        {            
        }
    }
}

Я бы сделал это проще для себя, сохранив зависимости элемента внутри самого элемента:

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

затем, учитывая это, вы можете реализовать пользовательский делегат сортировки для списка, который сортирует на основе того, содержится ли данный элемент в списке зависимостей другого:

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

другая идея, для случаев только с одним "родителем" в зависимости:

вместо deps, вы бы хранить родителей.
Таким образом, вы можете очень легко сказать, является ли проблема зависимостью от какой-то другой.
А потом использовать Comparable<T>, который будет требовать зависимости " меньше "и зависимость"больше".
А потом просто позвоните Collections.sort( List<T>, ParentComparator<T>);

для сценария с несколькими родителями потребуется поиск по дереву, что приведет к медленному выполнению. Но это можно решить с помощью кэш в виде матрицы сортировки*.

Я объединил идею DMM с алгоритмом поиска глубины в Википедии. Он работает идеально подходит для того, что мне нужно.

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

это рефакторинг кода из post https://stackoverflow.com/a/9991916/4805491.

// Version 1
public static class TopologicalSorter<T> where T : class {

    public struct Item {
        public readonly T Object;
        public readonly T Dependency;
        public Item(T @object, T dependency) {
            Object = @object;
            Dependency = dependency;
        }
    }


    public static T[] Sort(T[] objects, Func<T, T, bool> isDependency) {
        return Sort( objects.ToList(), isDependency ).ToArray();
    }

    public static T[] Sort(T[] objects, Item[] dependencies) {
        return Sort( objects.ToList(), dependencies.ToList() ).ToArray();
    }


    private static List<T> Sort(List<T> objects, Func<T, T, bool> isDependency) {
        return Sort( objects, GetDependencies( objects, isDependency ) );
    }

    private static List<T> Sort(List<T> objects, List<Item> dependencies) {
        var result = new List<T>( objects.Count );

        while (objects.Any()) {
            var obj = GetIndependentObject( objects, dependencies );
            RemoveObject( obj, objects, dependencies );
            result.Add( obj );
        }

        return result;
    }

    private static List<Item> GetDependencies(List<T> objects, Func<T, T, bool> isDependency) {
        var dependencies = new List<Item>();

        for (var i = 0; i < objects.Count; i++) {
            var obj1 = objects[i];
            for (var j = i + 1; j < objects.Count; j++) {
                var obj2 = objects[j];
                if (isDependency( obj1, obj2 )) dependencies.Add( new Item( obj1, obj2 ) ); // obj2 is dependency of obj1
                if (isDependency( obj2, obj1 )) dependencies.Add( new Item( obj2, obj1 ) ); // obj1 is dependency of obj2
            }
        }

        return dependencies;
    }


    private static T GetIndependentObject(List<T> objects, List<Item> dependencies) {
        foreach (var item in objects) {
            if (!GetDependencies( item, dependencies ).Any()) return item;
        }
        throw new Exception( "Circular reference found" );
    }

    private static IEnumerable<Item> GetDependencies(T obj, List<Item> dependencies) {
        return dependencies.Where( i => i.Object == obj );
    }

    private static void RemoveObject(T obj, List<T> objects, List<Item> dependencies) {
        objects.Remove( obj );
        dependencies.RemoveAll( i => i.Object == obj || i.Dependency == obj );
    }

}


// Version 2
public class TopologicalSorter {

    public static T[] Sort<T>(T[] source, Func<T, T, bool> isDependency) {
        var list = new LinkedList<T>( source );
        var result = new List<T>();

        while (list.Any()) {
            var obj = GetIndependentObject( list, isDependency );
            list.Remove( obj );
            result.Add( obj );
        }

        return result.ToArray();
    }

    private static T GetIndependentObject<T>(IEnumerable<T> list, Func<T, T, bool> isDependency) {
        return list.First( i => !GetDependencies( i, list, isDependency ).Any() );
    }

    private static IEnumerable<T> GetDependencies<T>(T obj, IEnumerable<T> list, Func<T, T, bool> isDependency) {
        return list.Where( i => isDependency( obj, i ) ); // i is dependency of obj
    }

}

мне не нравятся рекурсивные методы, поэтому DMM отсутствует. Крумелур выглядит хорошо, но, кажется, использует много памяти? Сделал альтернативный метод на основе стека, который, кажется, работает. Использует ту же логику DFS, что и DMM, и я использовал эти решения в качестве сравнения при тестировании.

    public static IEnumerable<T> TopogicalSequenceDFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> deps)
    {
        HashSet<T> yielded = new HashSet<T>();
        HashSet<T> visited = new HashSet<T>();
        Stack<Tuple<T, IEnumerator<T>>> stack = new Stack<Tuple<T, IEnumerator<T>>>();

        foreach (T t in source)
        {
            stack.Clear();
            if (visited.Add(t))
                stack.Push(new Tuple<T, IEnumerator<T>>(t, deps(t).GetEnumerator()));

            while (stack.Count > 0)
            {
                var p = stack.Peek();
                bool depPushed = false;
                while (p.Item2.MoveNext())
                {
                    var curr = p.Item2.Current;
                    if (visited.Add(curr))
                    {
                        stack.Push(new Tuple<T, IEnumerator<T>>(curr, deps(curr).GetEnumerator()));
                        depPushed = true;
                        break;
                    }
                    else if (!yielded.Contains(curr))
                        throw new Exception("cycle");
                }

                if (!depPushed)
                {
                    p = stack.Pop();
                    if (!yielded.Add(p.Item1))
                        throw new Exception("bug");
                    yield return p.Item1;
                }
            }
        }
    }

здесь также более простой вариант BFS на основе стека. Это приведет к другому результату, чем выше, но все еще действителен. Я не уверен, есть ли какие-либо преимущества в использовании варианта DFS выше, но это было весело создавать оно.

    public static IEnumerable<T> TopologicalSequenceBFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies)
    {
        var yielded = new HashSet<T>();
        var visited = new HashSet<T>();
        var stack = new Stack<Tuple<T, bool>>(source.Select(s => new Tuple<T, bool>(s, false))); // bool signals Add to sorted

        while (stack.Count > 0)
        {
            var item = stack.Pop();
            if (!item.Item2)
            {
                if (visited.Add(item.Item1))
                {
                    stack.Push(new Tuple<T, bool>(item.Item1, true)); // To be added after processing the dependencies
                    foreach (var dep in dependencies(item.Item1))
                        stack.Push(new Tuple<T, bool>(dep, false));
                }
                else if (!yielded.Contains(item.Item1))
                    throw new Exception("cyclic");
            }
            else
            {
                if (!yielded.Add(item.Item1))
                    throw new Exception("bug");
                yield return item.Item1;
            }
        }
    }

для .NET 4.7+ я предлагаю заменить Кортеж ValueTuple для более низкого использования памяти. В старых версиях .NET Кортеж может быть заменен на KeyValuePair.