Топологическая Сортировка с помощью LINQ

Ну, я не уверен, что такой способ обработки - лучший, но я могу ошибаться.

Типичным способом обработки топологической сортировки является использование графа, и для каждой итерации удаляются все узлы, которые не имеют входящего соединения, и одновременно удаляются все соединения, исходящие из этих узлов. Удаленные узлы являются выходом итерации. Повторяйте до тех пор, пока вы не сможете удалить больше узлов.

Однако, чтобы получить эти связи в первую очередь, с вашим методом, вам понадобится:

1. Метод (ваш компаратор), который может сказать «это до этого», но также » нет информации для этих двух "
2. Итерация всех комбинаций, создание соединений для всех комбинаций, для которых компаратор возвращает порядок.

Другими словами, метод, вероятно, будет определен следующим образом:

public Int32? Compare(TKey a, TKey b) { ... }

и затем вернет null, когда у него нет окончательного ответа для двух ключей.

Проблема, о которой я думаю, заключается в части «повторять все комбинации». Возможно, есть лучший способ справиться с этим, но я этого не вижу.

Я считаю, что ответ Лассе В. Карлсена находится на правильном пути, но мне не нравится скрывать метод Compare (или отдельный интерфейс для этого вопроса, который не выходит за пределы IComparable<T> ]).

Вместо этого я предпочел бы увидеть что-то вроде этого:

public interface IPartialOrderComparer<T> : IComparer<T>
{
    int? InstancesAreComparable(T x, T y);
}

Таким образом, у вас все еще есть реализация IComparer<T>, которую можно использовать в других местах, где требуется IComparer<T>.

Однако также требуется, чтобы вы указали отношение экземпляров T друг к другу с возвращаемым значением следующим образом (аналогично IComparable<T>):

• null - экземпляры несопоставимы друг с другом.
• 0 - экземпляры сравнимы между собой.

• 0 - x - сопоставимый ключ, а y - нет.

• < 0 - у сопоставимый ключ, а х - нет.

Конечно, вы не получите частичного упорядочения при передаче реализации этого чему-либо, что ожидает IComparable<T> (и следует отметить, что ответ Лассе В. Карлсена также не решает это), так как то, что вам нужно, не может быть представлено в простом методе Compare, который принимает два экземпляра T и возвращает int.

Чтобы закончить решение, вы должны предоставить пользовательский метод расширения OrderBy (а также ThenBy, OrderByDescending и ThenByDescending), который будет принимать новый параметр экземпляра (как вы уже указали). Реализация будет выглядеть примерно так:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(      
    this IEnumerable<TSource> source,      
    Func<TSource, TKey> keySelector,      
    IPartialOrderComparer<TKey> comparer)
{
    return Enumerable.OrderBy(source, keySelector,
        new PartialOrderComparer(comparer);
}

internal class PartialOrderComparer<T> : IComparer<T>
{
    internal PartialOrderComparer(IPartialOrderComparer<T> 
        partialOrderComparer)
    {
        this.partialOrderComparer = partialOrderComparer;
    }

    private readonly IPartialOrderComparer<T> partialOrderComparer;

    public int Compare(T x, T y)
    {
        // See if the items are comparable.
        int? comparable = partialOrderComparable.
            InstancesAreComparable(x, y);

        // If they are not comparable (null), then return
        // 0, they are equal and it doesn't matter
        // what order they are returned in.
        // Remember that this only to determine the
        // values in relation to each other, so it's
        // ok to say they are equal.
        if (comparable == null) return 0;

        // If the value is 0, they are comparable, return
        // the result of that.
        if (comparable.Value == 0) return partialOrderComparer.Compare(x, y);

        // One or the other is uncomparable.
        // Return the negative of the value.
        // If comparable is negative, then y is comparable
        // and x is not.  Therefore, x should be greater than y (think
        // of it in terms of coming later in the list after
        // the ordered elements).
        return -comparable.Value;            
    }
}

Интерфейс для определения отношения частичного порядка:

interface IPartialComparer<T> {
    int? Compare(T x, T y);
}

Compare должен возвращать -1, если x < y, 0, если x = y, 1, если y < x и null если x и y не сопоставимы.

Наша цель - вернуть порядок элементов в частичном порядке, который учитывает перечисление. То есть мы ищем последовательность e_1, e_2, e_3, ..., e_n элементов в частичном порядке, так что если i <= j и e_i сопоставимы с e_j, то e_i <= e_j. Я сделаю это, используя поиск в глубину.

Класс, реализующий топологическую сортировку с использованием поиска по глубине:

class TopologicalSorter {
    class DepthFirstSearch<TElement, TKey> {
        readonly IEnumerable<TElement> _elements;
        readonly Func<TElement, TKey> _selector;
        readonly IPartialComparer<TKey> _comparer;
        HashSet<TElement> _visited;
        Dictionary<TElement, TKey> _keys;
        List<TElement> _sorted;

        public DepthFirstSearch(
            IEnumerable<TElement> elements,
            Func<TElement, TKey> selector,
            IPartialComparer<TKey> comparer
        ) {
            _elements = elements;
            _selector = selector;
            _comparer = comparer;
            var referenceComparer = new ReferenceEqualityComparer<TElement>();
            _visited = new HashSet<TElement>(referenceComparer);
            _keys = elements.ToDictionary(
                e => e,
                e => _selector(e), 
                referenceComparer
            );
            _sorted = new List<TElement>();
        }

        public IEnumerable<TElement> VisitAll() {
            foreach (var element in _elements) {
                Visit(element);
            }
            return _sorted;
        }

        void Visit(TElement element) {
            if (!_visited.Contains(element)) {
                _visited.Add(element);
                var predecessors = _elements.Where(
                    e => _comparer.Compare(_keys[e], _keys[element]) < 0
                );
                foreach (var e in predecessors) {
                    Visit(e);
                }
                _sorted.Add(element);
            }
        }
    }

    public IEnumerable<TElement> ToplogicalSort<TElement, TKey>(
        IEnumerable<TElement> elements,
        Func<TElement, TKey> selector, IPartialComparer<TKey> comparer
    ) {
        var search = new DepthFirstSearch<TElement, TKey>(
            elements,
            selector,
            comparer
        );
        return search.VisitAll();
    }
}

Вспомогательный класс, необходимый для маркировки узлов как посещенных при выполнении поиска по глубине:

class ReferenceEqualityComparer<T> : IEqualityComparer<T> {
    public bool Equals(T x, T y) {
        return Object.ReferenceEquals(x, y);
    }

    public int GetHashCode(T obj) {
        return obj.GetHashCode();
    }
}

Я не утверждают, что это лучшая реализация алгоритма, но я считаю, что это правильная реализация. Кроме того, я не вернул IOrderedEnumerable, как вы просили, но это легко сделать, когда мы окажемся в этой точке.

Алгоритм работает, выполняя поиск в глубину по элементам, добавляя элемент e к линейному упорядочению (представленному в алгоритме как _sorted), если мы уже добавили, что все предшественники e уже были добавлены в порядок. Следовательно, для каждого элемента e, если мы еще не посетили его, посетите его предшественников, а затем добавьте e. Таким образом, это является ядром алгоритма:

public void Visit(TElement element) {
    // if we haven't already visited the element
    if (!_visited.Contains(element)) {
        // mark it as visited
        _visited.Add(element);
        var predecessors = _elements.Where(
            e => _comparer.Compare(_keys[e], _keys[element]) < 0
        );
        // visit its predecessors
        foreach (var e in predecessors) {
            Visit(e);
        }
        // add it to the ordering
        // at this point we are certain that
        // its predecessors are already in the ordering
        _sorted.Add(element);
    }
}

В качестве примера рассмотрим частичное упорядочение, определенное для подмножеств {1, 2, 3}, где X < Y, если X является подмножеством Y , Я реализую это следующим образом:

public class SetComparer : IPartialComparer<HashSet<int>> {
    public int? Compare(HashSet<int> x, HashSet<int> y) {
        bool xSubsety = x.All(i => y.Contains(i));
        bool ySubsetx = y.All(i => x.Contains(i));
        if (xSubsety) {
            if (ySubsetx) {
                return 0;
            }
            return -1;
        }
        if (ySubsetx) {
            return 1;
        }
        return null;
    }
}

Затем, когда sets определен как список подмножеств {1, 2, 3}

List<HashSet<int>> sets = new List<HashSet<int>>() {
    new HashSet<int>(new List<int>() {}),
    new HashSet<int>(new List<int>() { 1, 2, 3 }),
    new HashSet<int>(new List<int>() { 2 }),
    new HashSet<int>(new List<int>() { 2, 3}),
    new HashSet<int>(new List<int>() { 3 }),
    new HashSet<int>(new List<int>() { 1, 3 }),
    new HashSet<int>(new List<int>() { 1, 2 }),
    new HashSet<int>(new List<int>() { 1 })
};
TopologicalSorter s = new TopologicalSorter();
var sorted = s.ToplogicalSort(sets, set => set, new SetComparer());

Это приводит к упорядочению:

{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}

, который учитывает частичный порядок.

Это было очень весело. Спасибо.

Это моя оптимизированная и обновленная версия ответа tehMick .

Одним из изменений, которое я сделал, была замена реального списка значений, оставленных для получения логического списка. Для этого у меня есть два массива одинакового размера. В одном есть все значения, а в другом - флаги, показывающие, было ли выдано каждое значение. Таким образом, я избегаю затрат на изменение размера реального List.

Еще одно изменение заключается в том, что я считываю все ключи только один раз в начале итерации. По причинам, которые я сейчас не могу вспомнить (может быть, это был просто мой инстинкт), мне не нравится идея несколько раз вызывать функцию keySelector keySelector.

Последним штрихом была проверка параметров и дополнительная перегрузка, использующая неявный сравнитель ключей. Надеюсь, код достаточно читабелен. Проверьте его.

public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector)
{
    return PartialOrderBy(source, keySelector, null);
}

public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)
{
    if (source == null) throw new ArgumentNullException("source");
    if (keySelector == null) throw new ArgumentNullException("keySelector");
    if (comparer == null) comparer = (IComparer<TKey>)Comparer<TKey>.Default;

    return PartialOrderByIterator(source, keySelector, comparer);
}

private static IEnumerable<TSource> PartialOrderByIterator<TSource, TKey>(
    IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)
{
    var values = source.ToArray();
    var keys = values.Select(keySelector).ToArray();
    int count = values.Length;
    var notYieldedIndexes = System.Linq.Enumerable.Range(0, count).ToArray();
    int valuesToGo = count;

    while (valuesToGo > 0)
    {
        //Start with first value not yielded yet
        int minIndex = notYieldedIndexes.First( i => i >= 0);

        //Find minimum value amongst the values not yielded yet
        for (int i=0; i<count; i++)
        if (notYieldedIndexes[i] >= 0)
        if (comparer.Compare(keys[i], keys[minIndex]) < 0) {
            minIndex = i;
        }

        //Yield minimum value and mark it as yielded
        yield return values[minIndex];
        notYieldedIndexes[minIndex] = -1;
        valuesToGo--;
    }
}