Topologische Sortierung mit LINQ

Question

Ich habe eine Liste von Artikeln, die eine haben Teilordnungsbeziehung, ich.e, die Liste kann als a betrachtet werden Teilweise bestelltes Set.Ich möchte diese Liste genauso sortieren wie hier Frage.Wie dort richtig beantwortet, heißt dies topologische Sortierung.

Es gibt einen einigermaßen einfachen bekannten Algorithmus zur Lösung des Problems.Ich möchte eine LINQ-ähnliche Implementierung davon.

Ich habe bereits versucht, es zu verwenden OrderBy Erweiterungsmethode, aber ich bin mir ziemlich sicher, dass sie keine topologische Sortierung durchführen kann.Das Problem ist, dass die IComparer<TKey> Die Schnittstelle ist nicht in der Lage, eine Teilbestellung darzustellen.Dies geschieht, weil die Compare Die Methode kann grundsätzlich drei Arten von Werten zurückgeben: null, Negativ, Und positiv, Bedeutung sind gleich, ist weniger als, Und ist-größer-dann, jeweils.Eine funktionierende Lösung wäre nur möglich, wenn es einen Weg zur Rückkehr gäbe sind unabhängig.

Aus meiner voreingenommenen Sicht könnte die Antwort, nach der ich suche, von einem verfasst werden IPartialOrderComparer<T> Schnittstelle und eine Erweiterungsmethode wie diese:

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

Wie würde dies umgesetzt werden?Wie funktioniert die IPartialOrderComparer<T> Wie würde die Schnittstelle aussehen?Würden Sie einen anderen Ansatz empfehlen?Ich bin gespannt darauf, es zu sehen.Vielleicht gibt es eine schönere Möglichkeit, die Teilreihenfolge darzustellen, ich weiß es nicht.

Answer 1

Ich würde vorschlagen, die gleiche Icparer -Schnittstelle zu verwenden, aber die Erweiterungsmethode zu schreiben, um 0 als nicht verwandt zu interpretieren. In einer teilweisen Bestellung spielt die Elemente A und B gleich ihre Bestellung, wenn sie nicht miteinander verbunden sind - Sie müssen sie nur in Bezug auf Elemente bestellen, mit denen sie Beziehungen definiert haben.

Hier ist ein Beispiel, das eine teilweise Bestellung von gleichmäßigen und seltsamen ganzen Zahlen darstellt:

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

Ergebnis: 4, 8, 3, 5, 7, 10

Answer 2

Dies ist meine optimierte und renovierte Version von TehmickAntwort.

Eine Änderung, die ich vorgenommen habe, war der Austausch des Realen aufführen von Werten, die für eine logische Liste geliefert werden müssen. Dafür habe ich zwei Größenarrays gleicher Größe. Man hat alle Werte, und die anderen enthält Flags, die aussagen, ob jeder Wert erfolgt wurde. Auf diese Weise vermeide ich die Kosten für die Größe der Größe einer realen Größe List<Key>.

Eine weitere Änderung ist, dass ich zu Beginn der Iteration alle Schlüssel nur einmal lese. Aus Gründen kann ich mich jetzt nicht erinnern (vielleicht war es nur mein Instinkt), ich mag die Idee, das anzurufen, nicht keySelector mehrmals funktionieren.

Die letzten Berührungen waren Parametervalidierung und eine zusätzliche Überlastung, die einen impliziten Schlüsselvergleich verwendet. Ich hoffe, der Code ist lesbar genug. Hör zu.

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

Nun, ich bin mir nicht sicher, dass diese Art des Umgangs der beste Weg ist, aber ich könnte mich irren.

Die typische Möglichkeit, die topologische Sortierung zu verarbeiten, besteht darin, eine Grafik zu verwenden. Für jede Iteration entfernen Sie alle Knoten, die keine eingehende Verbindung haben, und entfernen gleichzeitig alle Verbindungen aus diesen Knoten. Die entfernten Knoten sind die Ausgabe der Iteration. Wiederholen Sie, bis Sie keine Knoten mehr entfernen können.

Um diese Verbindungen in erster Linie mit Ihrer Methode zu erhalten, benötigen Sie jedoch:

1. Eine Methode (Ihr Vergleich), die "das vor dem" sagen könnte, aber auch "keine Informationen für diese beiden"
2. Iterieren Sie alle Kombinationen und erstellen Sie Verbindungen für alle Kombinationen, für die der Vergleich eine Bestellung zurückgibt.

Mit anderen Worten, die Methode würde wahrscheinlich so definiert:

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

und dann zurück null Wenn es keine schlüssige Antwort für zwei Schlüssel gibt.

Das Problem, an das ich denke, ist der Teil "Iterate Alle Kombinationen". Vielleicht gibt es eine bessere Möglichkeit, damit umzugehen, aber ich sehe es nicht.

Answer 4

Ich glaube das Lasse V.Karlsens Antwort ist auf dem richtigen Weg, aber ich mag es nicht, die Compare-Methode auszublenden (oder eine separate Schnittstelle, die sich nicht erstreckt). IComparable<T>).

Stattdessen würde ich lieber so etwas sehen:

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

Auf diese Weise haben Sie immer noch eine Implementierung von IComparer<T> die an anderen Orten verwendet werden können, die es erfordern IComparer<T>.

Es erfordert jedoch auch, dass Sie die Beziehung der Instanzen von T zueinander mit dem Rückgabewert auf folgende Weise angeben (ähnlich wie IComparable<T>):

• null – Instanzen sind nicht miteinander vergleichbar.
• 0 – die Instanzen sind miteinander vergleichbar.

• 0 - x ist ein vergleichbarer Schlüssel, y jedoch nicht.

• < 0 – y ist ein vergleichbarer Schlüssel, x jedoch nicht.

Natürlich erhalten Sie keine Teilbestellung, wenn Sie eine Implementierung davon an irgendetwas übergeben, das eine erwartet IComparable<T> (und es sollte beachtet werden, dass Lasse V.Karlsens Antwort löst dieses Problem auch nicht, da das, was Sie benötigen, nicht in einer einfachen Compare-Methode dargestellt werden kann, die zwei Instanzen von T verwendet und einen int zurückgibt.

Um die Lösung fertigzustellen, müssen Sie eine benutzerdefinierte OrderBy-Erweiterungsmethode (sowie ThenBy, OrderByDescending und ThenByDescending) bereitstellen, die den neuen Instanzparameter akzeptiert (wie Sie bereits angegeben haben).Die Implementierung würde etwa so aussehen:

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

Schnittstelle zur Definition der Teilreihenfolge:

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

Compare sollte zurückkehren -1 wenn x < y, 0 wenn x = y, 1 wenn y < x und null wenn x und y sind nicht vergleichbar.

Unser Ziel ist es, eine Bestellung der Elemente in der Teilreihenfolge zurückzugeben, die die Aufzählung respektiert. Das heißt, wir suchen eine Sequenz e_1, e_2, e_3, ..., e_n der Elemente in der Teilreihenfolge so, dass wenn i <= j und e_i ist vergleichbar mit e_j dann e_i <= e_j. Ich werde dies mit einer Tiefensuche tun.

Klasse, die die topologische Sortierung mithilfe der Tiefen-First-Suche implementiert:

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

Helferklasse, die zum Markieren von Knoten erforderlich ist, wie sie während der Tiefe-First-Suche besucht wurden:

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

Ich behaupte nicht, dass dies die beste Implementierung des Algorithmus ist, aber ich glaube, dass es sich um eine korrekte Implementierung handelt. Außerdem habe ich keine zurückgegeben IOrderedEnumerable Wie Sie beantragt haben, aber das ist einfach zu tun, sobald wir an diesem Punkt sind.

Der Algorithmus funktioniert mit einer Tiefensuche durch die Elemente, die ein Element hinzufügen e zur linearen Bestellung (dargestellt durch _sorted im Algorithmus), wenn wir bereits alle Vorgänger hinzugefügt haben e wurden bereits zur Bestellung hinzugefügt. Daher für jedes Element e, Wenn wir es noch nicht besucht haben, besuchen Sie seine Vorgänger und fügen Sie dann hinzu e. Dies ist also der Kern des Algorithmus:

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

Betrachten Sie beispielsweise die auf Teilmengen definierte Teilbestellung von Untergruppen von {1, 2, 3} wo X < Y wenn X ist eine Teilmenge von Y. Ich implementiere dies wie folgt:

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

Dann mit sets definiert als die Liste der Untergruppen von {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());

Dies führt zur Bestellung:

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

Was respektiert die Teilreihenfolge.

Das hat viel Spaß gemacht. Vielen Dank.

Answer 6

Vielen Dank an alle, angefangen bei Eric Mickelsens Antwort habe ich meine Version ausgedacht, da ich lieber Nullwerte verwende, um keine Beziehung anzuzeigen, wie Lasse V. Karlsen sagte.

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

Dann habe ich die folgende Schnittstelle für den Vergleich

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

und diese Helferklasse

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

Dies ermöglicht es, die Verwendung ein wenig zu verschönern, damit meine Tests wie folgt aussehen können

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