使用 LINQ 进行拓扑排序

Question

我有一个项目列表，其中包含 偏序关系, ， 我。e，该列表可以被认为是 部分有序集. 。我想以与此相同的方式对该列表进行排序 问题. 。正如那里正确回答的那样，这被称为 拓扑排序.

有一个相当简单的已知算法可以解决这个问题。我想要一个类似 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> 界面会是什么样子？您会推荐一种不同的方法吗？我很想看到它。也许有更好的方法来表示部分顺序，我不知道。

Answer 1

我建议使用相同的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

Answer 2

这是我的优化和翻新版本 tehMick ”的回答。

我一个变化被替换真实值的列表左，得到用于逻辑清单。对于这一点，我也有同样大小的两个大小的数组。一个人所有的值，其余包含如果每个值已经取得了标志告诉。这样，我避免必须调整真实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--;
    }
}

Answer 3

好吧，我不确定这种处理方式是最好的方式，但我可能是错的。

处理拓扑排序的典型方法是使用图，并且对于每次迭代，删除所有没有入站连接的节点，并同时删除从这些节点出站的所有连接。删除的节点是迭代的输出。重复此操作，直到无法删除更多节点。

但是，为了首先使用您的方法获得这些连接，您需要：

1. 一种方法（你的比较器）可以说“这个在那之前”，但也可以说“没有这两个的信息”
2. 迭代所有组合，为比较器返回排序的所有组合创建连接。

换句话说，该方法可能会这样定义：

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

然后返回 null 当它没有两个密钥的结论性答案时。

我正在考虑的问题是“迭代所有组合”部分。也许有更好的方法来处理这个问题，但我没有看到。

Answer 4

我相信 拉塞 V.卡尔森的回答 是在正确的轨道上，但我不喜欢隐藏 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 - y 是可比较的键，但 x 不是。

当然，当将其实现传递给任何需要 IComparable<T> （应该指出的是，Lasse V.Karlsen 的答案也没有解决这个问题），因为您需要的内容无法用简单的 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;            
    }
}

Answer 5

接口定义部分顺序关系：

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

需要为已访问而做深度优先搜索标记节点Helper类：

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}

，尊重偏序。

这是一个很大的乐趣。感谢。

Answer 6

非常感谢大家，埃里克Mickelsen的回答[我已开始与我的版本上来，因为我更喜欢使用空值来表示作为拉塞五卡尔森说没有关系。

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