Ordinamento topologico utilizzando LINQ

Question

Ho un elenco di elementi che hanno a relazione d'ordine parziale, io.e, l'elenco può essere considerato a insieme parzialmente ordinato.Voglio ordinare questo elenco nello stesso modo di questo domanda.Come risposto correttamente lì, questo è noto come ordinamento topologico.

Esiste un algoritmo noto ragionevolmente semplice per risolvere il problema.Voglio un'implementazione simile a LINQ.

Ho già provato a usare OrderBy metodo di estensione, ma sono abbastanza sicuro che non sia in grado di effettuare l'ordinamento topologico.Il problema è che il IComparer<TKey> l'interfaccia non è in grado di rappresentare un ordine parziale.Ciò accade perché il Compare Il metodo può restituire fondamentalmente 3 tipi di valori: zero, negativo, E positivo, Senso sono uguali, è meno di, E è-maggiore-allora, rispettivamente.Una soluzione funzionante sarebbe possibile solo se ci fosse un modo per ritornare non sono correlati.

Dal mio punto di vista parziale, la risposta che cerco potrebbe essere composta da an IPartialOrderComparer<T> interfaccia e un metodo di estensione come questo:

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

Come verrebbe implementato?Come funziona il IPartialOrderComparer<T> l'interfaccia sarebbe simile?Consiglieresti un approccio diverso?Sono ansioso di vederlo.Forse c'è un modo più carino per rappresentare l'ordine parziale, non lo so.

Answer 1

Suggerirei di utilizzare la stessa interfaccia IComparer, ma di scrivere il metodo di estensione in modo da interpretare 0 come non correlato.In un ordinamento parziale, se gli elementi aeb sono uguali il loro ordine non ha importanza, allo stesso modo se non sono correlati, devi solo ordinarli rispetto agli elementi con cui hanno relazioni definite.

Ecco un esempio che esegue un ordinamento parziale di numeri interi pari e dispari:

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

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

Answer 2

Questa è la mia versione ottimizzata e rinnovata di tehMickè la risposta.

Una modifica che ho apportato è stata la sostituzione del reale elenco di valori rimasti per produrre un elenco logico.Per questo, ho due array di dimensioni della stessa dimensione.Uno contiene tutti i valori e gli altri contengono flag che indicano se ciascun valore è stato restituito.In questo modo evito il costo di dover ridimensionare un file real List<Key>.

Un altro cambiamento è che leggo tutte le chiavi solo una volta all'inizio dell'iterazione.Per motivi che ora non ricordo (forse è stato solo il mio istinto) non mi piace l'idea di chiamare il keySelector funzionare più volte.

Gli ultimi tocchi sono stati la convalida dei parametri e un sovraccarico aggiuntivo che utilizza un comparatore di chiavi implicito.Spero che il codice sia abbastanza leggibile.Controlla.

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

Beh, non sono sicuro che questo modo di gestirlo sia il modo migliore, ma potrei sbagliarmi.

Il modo tipico per gestire l'ordinamento topologico è utilizzare un grafico e per ogni iterazione rimuovere tutti i nodi che non dispongono di una connessione in entrata e contemporaneamente rimuovere tutte le connessioni in uscita da tali nodi.I nodi rimossi sono l'output dell'iterazione.Ripeti fino a quando non sarà più possibile rimuovere altri nodi.

Tuttavia, per ottenere innanzitutto tali connessioni, con il tuo metodo, avresti bisogno di:

1. Un metodo (il tuo comparatore) che potrebbe dire "questo prima di quello" ma anche "nessuna informazione per questi due"
2. Itera tutte le combinazioni, creando connessioni per tutte le combinazioni per le quali l'operatore di confronto restituisce un ordinamento.

In altre parole, il metodo verrebbe probabilmente definito in questo modo:

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

e poi ritornare null quando non ha una risposta conclusiva per due chiavi.

Il problema a cui sto pensando è la parte "itera tutte le combinazioni".Forse c'è un modo migliore per gestire la situazione, ma non lo vedo.

Answer 4

Credo che Lasse V.La risposta di Karlsen è sulla strada giusta, ma non mi piace nascondere il metodo Confronta (o un'interfaccia separata che non si estenda da IComparable<T>).

Invece preferirei vedere qualcosa del genere:

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

In questo modo, hai ancora un'implementazione di IComparer<T> che può essere utilizzato in altri luoghi che lo richiedono IComparer<T>.

Tuttavia, richiede anche di indicare la relazione tra le istanze di T con il valore restituito nel modo seguente (simile a IComparable<T>):

• null: le istanze non sono confrontabili tra loro.
• 0 - le istanze sono paragonabili tra loro.

• 0 - x è una chiave comparabile, ma y non lo è.

• < 0 - y è una chiave comparabile, ma x non lo è.

Naturalmente, non otterrai un ordinamento parziale quando passi un'implementazione di this a qualcosa che si aspetta un IComparable<T> (e va notato che Lasse V.Anche la risposta di Karlsen non risolve questo problema) poiché ciò di cui hai bisogno non può essere rappresentato in un semplice metodo Confronta che accetta due istanze di T e restituisce un int.

Per completare la soluzione, devi fornire un metodo di estensione OrderBy personalizzato (così come ThenBy, OrderByDescending e ThenByDescending) che accetterà il nuovo parametro di istanza (come hai già indicato).L'implementazione sarebbe simile a questa:

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

Interfaccia per definire la relazione di ordine parziale:

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

Compare dovrebbe ritornare -1 Se x < y, 0 Se x = y, 1 Se y < x E null Se x E y non sono paragonabili.

Il nostro obiettivo è restituire un ordinamento degli elementi nell'ordine parziale che rispetti l'enumerazione.Cerchiamo cioè una sequenza e_1, e_2, e_3, ..., e_n degli elementi nell'ordine parziale tale che if i <= j E e_i è paragonabile a e_j Poi e_i <= e_j.Lo farò utilizzando una ricerca approfondita.

Classe che implementa l'ordinamento topologico utilizzando la ricerca in profondità:

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

Classe helper necessaria per contrassegnare i nodi come visitati durante la ricerca approfondita:

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

Non affermo che questa sia la migliore implementazione dell'algoritmo, ma credo che sia un'implementazione corretta.Inoltre, non ho restituito un file IOrderedEnumerable come hai richiesto, ma è facile da fare una volta che siamo a questo punto.

L'algoritmo funziona eseguendo prima una ricerca approfondita tra gli elementi aggiungendo un elemento e all'ordinamento lineare (rappresentato da _sorted nell'algoritmo) se abbiamo già aggiunto tutti i predecessori di e sono già stati aggiunti all'ordine.Quindi, per ogni elemento e, se non l'abbiamo già visitato, visita i suoi predecessori e poi aggiungi e.Quindi, questo è il nucleo dell’algoritmo:

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

Ad esempio, consideriamo l'ordinamento parziale definito su sottoinsiemi di {1, 2, 3} Dove X < Y Se X è un sottoinsieme di Y.Lo implemento come segue:

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

Poi con sets definito come l'elenco dei sottoinsiemi di {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());

Ciò si traduce nell'ordinamento:

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

che rispetta l'ordine parziale.

È stato molto divertente.Grazie.

Answer 6

grazie mille a tutti, partendo dalla risposta di Eric Mickelsen ho elaborato la mia versione poiché preferisco utilizzare valori null per indicare alcuna relazione come Lasse V.Karlsen ha detto.

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

quindi ho la seguente interfaccia per il comparatore

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

e questa classe di aiuto

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

ciò consente di abbellire un po' l'utilizzo in modo che i miei test possano assomigliare al seguente

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