Топологическая сортировка с использованием LINQ

StackOverflow https://stackoverflow.com/questions/1982592

Вопрос

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

Существует достаточно простой известный алгоритм решения этой проблемы.Мне нужна LINQ-подобная реализация.

я уже пробовал использовать OrderBy метод расширения, но я совершенно уверен, что он не способен выполнить топологическую сортировку.Проблема в том, что IComparer<TKey> интерфейс не может представлять частичный порядок.Это происходит потому, что Compare метод может возвращать в основном 3 вида значений: нуль, отрицательный, и позитивный, значение равны, меньше чем, и больше-то, соответственно.Рабочее решение было бы возможно только в том случае, если бы существовал способ вернуть не связаны.

С моей предвзятой точки зрения, ответ, который я ищу, может быть составлен кем-то IPartialOrderComparer<T> интерфейс и метод расширения, подобный этому:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IPartialOrderComparer<TKey> comparer
);

Как это будет реализовано?Как IPartialOrderComparer<T> интерфейс будет выглядеть?Вы бы порекомендовали другой подход?Мне не терпится это увидеть.Возможно, есть более приятный способ представить частичный порядок, я не знаю.

Это было полезно?

Решение

Я бы предложил использовать тот же интерфейс IcomParer, но написать метод расширения, чтобы интерпретировать 0 как не связанный. В частичном упорядочении, если элементы A и B равны, их порядок не имеет значения, как в случае, если они не связаны - вам нужно только заказать их в отношении элементов, с которыми они определили отношения.

Вот пример, который делает частичное упорядочение ровных и странных целых чисел:

namespace PartialOrdering
{
    public static class Enumerable
    {
        public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            List<TSource> list = new List<TSource>(source);
            while (list.Count > 0)
            {
                TSource minimum = default(TSource);
                TKey minimumKey = default(TKey);
                foreach (TSource s in list)
                {
                    TKey k = keySelector(s);
                    minimum = s;
                    minimumKey = k;
                    break;
                }
                foreach (TSource s in list)
                {
                    TKey k = keySelector(s);
                    if (comparer.Compare(k, minimumKey) < 0)
                    {
                        minimum = s;
                        minimumKey = k;
                    }
                }
                yield return minimum;
                list.Remove(minimum);
            }
            yield break;
        }

    }
    public class EvenOddPartialOrdering : IComparer<int>
    {
        public int Compare(int a, int b)
        {
            if (a % 2 != b % 2)
                return 0;
            else if (a < b)
                return -1;
            else if (a > b)
                return 1;
            else return 0; //equal
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            IEnumerable<Int32> integers = new List<int> { 8, 4, 5, 7, 10, 3 };
            integers = integers.PartialOrderBy<Int32, Int32>(new Func<Int32, Int32>(delegate(int i) { return i; }), new EvenOddPartialOrdering());
        }
    }
}

Результат: 4, 8, 3, 5, 7, 10

Другие советы

Это моя оптимизированная и отремонтированная версия ТехмикОтвет.

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

Еще одно изменение в том, что я читаю все ключи только один раз в начале итерации. По причинам, которые я не могу вспомнить сейчас (может 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--;
    }
}

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

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

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

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

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

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

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

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

я полагаю, что Ответ Лассе В. Карлсена на правильном пути, но мне не нравится скрывать метод сравнения (или отдельный интерфейс в этом отношении, который не распространяется от 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 - y - сопоставимый ключ, но X нет.

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

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

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}

который соблюдает частичный порядок.

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

Большое спасибо всем, начиная с ответа Эрика Микелсена, я придумал свою версию, поскольку я предпочитаю использовать нулевые значения, чтобы указать никаких отношений, как сказал Лассе В. Карлсен.

public static IEnumerable<TSource> PartialOrderBy<TSource>(
        this IEnumerable<TSource> source,            
        IPartialEqualityComparer<TSource> comparer)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (comparer == null) throw new ArgumentNullException("comparer");


        var set = new HashSet<TSource>(source);
        while (!set.IsEmpty())
        {
            TSource minimum = set.First();                

            foreach (TSource s in set)
            {                    
                var comparison = comparer.Compare(s, minimum);
                if (!comparison.HasValue) continue;
                if (comparison.Value <= 0)
                {
                    minimum = s;                        
                }
            }
            yield return minimum;
            set.Remove(minimum);
        }
    }

public static IEnumerable<TSource> PartialOrderBy<TSource>(
       this IEnumerable<TSource> source,
       Func<TSource, TSource, int?> comparer)
    {
        return PartialOrderBy(source, new PartialEqualityComparer<TSource>(comparer));
    }

Тогда у меня есть следующий интерфейс для сравнения

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

И этот помощник класса

internal class PartialEqualityComparer<TSource> : IPartialEqualityComparer<TSource>
{
    private Func<TSource, TSource, int?> comparer;

    public PartialEqualityComparer(Func<TSource, TSource, int?> comparer)
    {
        this.comparer = comparer;
    }

    public int? Compare(TSource x, TSource y)
    {
        return comparer(x,y);
    }
}

Это позволяет немного украсить использование, чтобы мои тесты выглядели как следующие

 var data = new int[] { 8,7,6,5,4,3,2,1,0 };
 var partiallyOrdered = data.PartialOrderBy((x, y) =>
     {
        if (x % 2 == 0 && y % 2 != 0) return null;
        return x.CompareTo(y);
     });
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top