Clasificación topológica usando LINQ

Question

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

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

Ya intenté usar OrderBy método de extensión, pero estoy bastante seguro de que no puede realizar una clasificación topológica.El problema es que el IComparer<TKey> La interfaz no puede representar un pedido parcial.Esto sucede porque el Compare El método puede devolver básicamente 3 tipos de valores: cero, negativo, y positivo, significado son iguales, es menos que, y es-mayor-entonces, respectivamente.Una solución funcional sólo sería posible si hubiera una manera de regresar no están relacionados.

Desde mi punto de vista parcial, la respuesta que busco podría estar compuesta por un IPartialOrderComparer<T> interfaz 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 hace el IPartialOrderComparer<T> ¿Cómo se vería la interfaz?¿Recomendarías un enfoque diferente?Estoy ansioso por verlo.Quizás haya una manera mejor de representar el orden parcial, no lo sé.

Answer 1

Se recomienda usar la misma interfaz IComparer, pero escribir el método de extensión con el fin de interpretar 0 como no relacionado. En una ordenación parcial, si los elementos a y b son iguales su orden no importa, como en cuanto a si ellos no están relacionados - sólo tiene que ordenar con respecto a los elementos con los que se han definido las relaciones

.

Aquí hay un ejemplo que hace una ordenación parcial de los 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 2

Esta es mi versión optimizada y renovada de tehMickla respuesta.

Un cambio que hice fue reemplazar el real lista de valores que quedan por producir para una lista lógica.Para esto, tengo dos matrices del mismo tamaño.Uno tiene todos los valores y el otro contiene indicadores que indican si se ha obtenido cada valor.De esta manera evito el coste de tener que cambiar el tamaño de una imagen real. List<Key>.

Otro cambio es que leo todas las claves solo una vez al comienzo de la iteración.Por razones que no recuerdo ahora (tal vez fue sólo mi instinto) no me gusta la idea de llamar al keySelector funcionar 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.Échale 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 3

Bueno, no estoy seguro de que esta forma de manejo es la mejor manera, pero podría estar equivocado.

La forma típica de manejar clasificación topológica es mediante el uso de un gráfico, y para cada iteración eliminar todos los nodos que no tienen una conexión de entrada, y al mismo tiempo eliminan todas las conexiones salientes a partir de esos nodos. Los nodos eliminados son la salida de la iteración. Repetir hasta que no se puede quitar cualquier más nodos.

Sin embargo, con el fin de conseguir esas conexiones en el primer lugar, con su método, lo que se necesita:

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

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

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

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

El problema que estoy pensando es la parte "iterar todas las combinaciones". Tal vez hay una mejor manera de manejar esto, pero yo no lo veo.

Answer 4

Creo que la respuesta de Lasse V. Karlsen está en el camino correcto , pero no como escondite del método de comparación (o una interfaz independiente para el caso que no se extiende a partir 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, usted todavía tiene una implementación de IComparer<T> que puede ser utilizado en otros lugares que requieren IComparer<T>.

Sin embargo, también se requiere que indica la relación de los casos de T entre sí con el valor de retorno de la manera siguiente (similar a IComparable<T>):

• null - casos no son comparables entre sí
.
• 0 - los casos son comparables entre sí
.

•   

  0 -. X es una clave comparable, pero Y no es

• <0 -. Y es una clave comparable, pero X no es

Por supuesto, usted no conseguirá ordenación parcial cuando pasa una implementación de este a cualquier cosa que se espera un IComparable<T> (y cabe señalar que la respuesta de Lasse V. Karlsen no resuelve este tampoco) como lo que se necesita se puede' t puede representar en un simple método de comparación que tiene dos instancias de T y devuelve un int.

Para terminar la solución, tiene que proporcionar una costumbre OrdenarPor (así como ThenBy, OrderByDescending y ThenByDescending también) método de extensión que aceptará el nuevo parámetro de ejemplar (como ya se ha indicado). La implementación sería algo como esto:

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

interfaz para definir la relación de orden parcial:

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

Compare debería devolver -1 si x < y, 0 si x = y, 1 si y < x y null si x y y no son comparables.

Nuestro objetivo es devolver un ordenamiento de los elementos en el orden parcial que respete la enumeración. Es decir, buscamos una e_1, e_2, e_3, ..., e_n secuencia de los elementos en el orden parcial de tal manera que si i <= j y e_i es comparable a e_j entonces e_i <= e_j. Voy a hacer esto utilizando una búsqueda en profundidad.

clase que implementa topológica especie mediante la búsqueda primero 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();
    }
}

Clase auxiliar necesaria para el marcado de los nodos como visitado mientras se hace la 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 pretendo que esta es la mejor aplicación del algoritmo, pero yo creo que es una implementación correcta. Además, no me vuelvo un IOrderedEnumerable como usted pidió pero que es fácil de hacer una vez que estamos en este punto.

Los funciona el algoritmo de hacer una búsqueda en profundidad a través de los elementos de la adición de un e elemento a la ordenación lineal (representados por _sorted en el algoritmo) si ya hemos añadido todos los predecesores de e ya se han añadido a la ordenación. Por lo tanto, para cada elemento de e, si todavía no hemos visitado, visitar sus predecesores y luego añadir 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);
    }
}

A modo de ejemplo, considere la parcial-pedido definido en subconjuntos de {1, 2, 3} donde X < Y si X es un subconjunto de Y. Implemento 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;
    }
}

A continuación, con sets define 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 da lugar al pedido:

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

que respeta el orden parcial.

Eso fue muy divertido. Gracias.

Answer 6

Muchas gracias a todo el mundo, a partir hemos respuesta que Mickelsen de Eric se acercó con mi versión como prefiero utilizar valores nulos para indicar ninguna 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 el uso de un poco para mis ensayos podrá tiene el siguiente

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