.net - Clasificación topológica utilizando LINQ

sorting topological-sort

Question

Tengo una lista de artículos que tienen una relación de orden parcial , i. e, la lista puede considerarse un conjunto parcialmente ordenado . Quiero ordenar esta lista de la misma manera que en esta question . Como se responde correctamente, esto se conoce como ordenación topológica .

Hay un algoritmo conocido razonablemente simple para resolver el problema. Quiero una implementación similar a LINQ.

Ya intenté usar el método de extensión OrderBy , pero estoy bastante seguro de que no es capaz de hacer una clasificación topológica. El problema es que la IComparer<TKey> no puede representar una orden parcial. Esto sucede porque el método de Compare puede devolver básicamente 3 tipos de valores: cero , negativo y positivo , es decir, son iguales , es menor que , y es mayor luego , respectivamente. Una solución de trabajo solo sería posible si hubiera una forma de devolver sin relación .

Desde mi punto de vista sesgado, la respuesta que estoy buscando podría estar compuesta por una IPartialOrderComparer<T> y un método de extensión como este:

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

¿Cómo se implementaría esto? ¿Cómo se IPartialOrderComparer<T> la IPartialOrderComparer<T> ? ¿Recomendarías un enfoque diferente? Estoy ansioso por verlo. Tal vez haya una manera más agradable de representar el pedido parcial, no lo sé.

Answer 1

Bueno, no estoy seguro de que esta forma de manejarlo sea la mejor, pero podría estar equivocado.

La forma típica de manejar la clasificación topológica es mediante el uso de un gráfico, y para cada iteración, elimine todos los nodos que no tengan una conexión de entrada y elimine simultáneamente todas las conexiones salientes de esos nodos. Los nodos eliminados son la salida de la iteración. Repita hasta que no pueda eliminar más nodos.

Sin embargo, para obtener esas conexiones en primer lugar, con su método, necesitaría:

1. Un método (su comparador) que podría decir "esto antes que eso" pero también "no hay información para estos dos"
2. Iterar todas las combinaciones, creando conexiones para todas las combinaciones para las que el comparador devuelve un pedido.

En otras palabras, el método probablemente se definiría así:

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

y luego devuelve null cuando no tiene una respuesta concluyente para dos claves.

El problema en el que estoy pensando es en la parte "iterar todas las combinaciones". Quizás haya una mejor manera de manejar esto, pero no lo estoy viendo.

Answer 2

Creo que la respuesta de Lasse V. Karlsen está en el camino correcto, pero no me gusta ocultarme el método de comparación (o una interfaz separada para la materia que no se extiende desde IComparable<T> ).

En su lugar, prefiero ver algo como esto:

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

De esta manera, todavía tiene una implementación de IComparer<T> que se puede utilizar en otros lugares que requieren IComparer<T> .

Sin embargo, también requiere que indique la relación de las instancias de T entre sí y el valor de retorno de la siguiente manera (similar a IComparable<T> ):

• nulo - las instancias no son comparables entre sí.
• 0 - las instancias son comparables entre sí.

• 0 - x es una clave comparable, y y no lo es.

• <0 - y es una clave comparable, pero x no lo es.

Por supuesto, no obtendrá un pedido parcial cuando pase una implementación de esto a cualquier cosa que espere un IComparable<T> (y debe tenerse en cuenta que la respuesta de Lasse V. Karlsen tampoco resuelve esto), ya que lo que necesita puede t se representa en un método de comparación simple que toma dos instancias de T y devuelve un int.

Para finalizar la solución, debe proporcionar un método de extensión personalizado OrderBy (así como ThenBy, OrderByDescending y ThenByDescending) que acepte el nuevo parámetro de instancia (como ya ha indicado). La implementación se vería algo así:

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 3

Esta es mi versión optimizada y restaurada de la respuesta de tehMick .

Un cambio que hice fue reemplazar la lista real de valores que quedaron para obtener una lista lógica. Para esto, tengo dos matrices de tamaño del mismo tamaño. Uno tiene todos los valores y los otros contienen indicadores que indican si se ha producido cada valor. De esta manera, evito el costo de tener que cambiar el tamaño de una List<Key> real.

Otro cambio es que estoy leyendo todas las claves solo una vez al comienzo de la iteración. Por razones que no puedo recordar ahora (quizás fue solo mi instinto) no me gusta la idea de llamar a la función keySelector varias veces.

Los últimos toques fueron la validación de parámetros y una sobrecarga adicional que utiliza un comparador de claves implícito. Espero que el código sea lo suficientemente legible. Echale un vistazo.

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 4

Interfaz para definir la relación de orden parcial:

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

Compare debe devolver -1 si x < y , 0 si x = y , 1 si y < x y null si x e y no son comparables.

Nuestro objetivo es devolver un orden de los elementos en el orden parcial que respeta la enumeración. Es decir, buscamos una secuencia e_1, e_2, e_3, ..., e_n de los elementos en el orden parcial, de modo que si i <= j y e_i es comparable a e_j entonces e_i <= e_j . Lo haré usando una búsqueda en profundidad.

Clase que implementa ordenamiento topológico usando búsqueda en profundidad:

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

Se necesita una clase auxiliar para marcar los nodos como visitados mientras se hace una búsqueda en profundidad:

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

No digo que esta sea la mejor implementación del algoritmo, pero creo que es una implementación correcta. Además, no IOrderedEnumerable un IOrderedEnumerable como solicitó, pero es fácil de hacer una vez que estamos en este punto.

El algoritmo funciona haciendo una búsqueda en profundidad a través de los elementos, agregando un elemento e al ordenamiento lineal (representado por _sorted en el algoritmo) si ya hemos agregado todos los predecesores de e que ya se han agregado al pedido. Por lo tanto, para cada elemento e , si aún no lo hemos visitado, visite sus predecesores y luego agregue e . Por lo tanto, este es el núcleo del 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);
    }
}

Como ejemplo, considere el ordenamiento parcial definido en los subconjuntos de {1, 2, 3} donde X < Y si X es un subconjunto de Y Implemento esto de la siguiente manera:

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

Luego, con los sets definidos como la lista de subconjuntos de {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());

Esto se traduce en el pedido:

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

Que respeta el orden parcial.

Eso fue muy divertido. Gracias.

Answer 5

Sugeriría usar la misma interfaz de IComparer, pero escribir el método de extensión para interpretar 0 como no relacionado. En una ordenación parcial, si los elementos a y b son iguales a su orden, no importa, de la misma manera si no están relacionados, solo tiene que ordenarlos con respecto a los elementos con los que tienen relaciones definidas.

Aquí hay un ejemplo que hace un orden parcial de enteros pares e impares:

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

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

Answer 6

muchas gracias a todos, a partir de la respuesta de Eric Mickelsen, se me ocurrió mi versión, ya que prefiero usar valores nulos para indicar que no hay relación, como dijo Lasse V. Karlsen.

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

Entonces tengo la siguiente interfaz para el comparador

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

y esta clase de ayuda

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

que permite embellecer un poco el uso para que mis pruebas puedan tener el siguiente aspecto

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