Classificação topológica usando LINQ

Question

Eu tenho uma lista de itens que têm um relação de ordem parcial, eu.e, a lista pode ser considerada uma conjunto parcialmente ordenado.Quero classificar esta lista da mesma maneira que neste pergunta.Como respondido corretamente lá, isso é conhecido como classificação topológica.

Existe um algoritmo conhecido razoavelmente simples para resolver o problema.Eu quero uma implementação semelhante ao LINQ.

eu já tentei usar OrderBy método de extensão, mas tenho certeza de que não é capaz de fazer classificação topológica.O problema é que o IComparer<TKey> interface não é capaz de representar uma ordem parcial.Isto acontece porque o Compare O método pode retornar basicamente 3 tipos de valores: zero, negativo, e positivo, significado são iguais, é menos do que, e é-maior-então, respectivamente.Uma solução funcional só seria possível se houvesse uma maneira de retornar não estão relacionados.

Do meu ponto de vista tendencioso, a resposta que procuro pode ser composta por um IPartialOrderComparer<T> interface e um método de extensão como este:

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

Como isso seria implementado?Como é que IPartialOrderComparer<T> interface seria?Você recomendaria uma abordagem diferente?Estou ansioso para ver isso.Talvez exista uma maneira melhor de representar a ordem parcial, não sei.

Answer 1

Eu sugeriria o uso da mesma interface ICOMPARER, mas escrevendo o método de extensão para interpretar 0 como não relacionado. Em uma ordem parcial, se os elementos A e B forem iguais, sua ordem não importa, como não estiver relacionada - você só precisará ordená -los com relação aos elementos com os quais eles definiram relacionamentos.

Aqui está um exemplo que faz uma ordem parcial de números inteiros pares e estranhos:

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 é a minha versão otimizada e reformada de TehmickResposta.

Uma mudança que fiz foi substituir o real Lista de valores deixados para produzir para uma lista lógica. Para isso, tenho duas matrizes de tamanho do mesmo tamanho. Um tem todos os valores, e os outros contém sinalizadores informando se cada valor foi produzido. Dessa forma, evito o custo de ter que redimensionar um real List<Key>.

Uma outra mudança é que estou lendo todas as teclas apenas uma vez no início da iteração. Por razões que não me lembro agora (talvez fosse apenas o meu instinto), não gosto da ideia de chamar o keySelector função várias vezes.

Os últimos toques foram a validação de parâmetros e uma sobrecarga extra que usa uma comparação de chave implícita. Espero que o código seja legível o suficiente. Confira.

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

Bem, não tenho certeza de que essa maneira de lidar com isso seja a melhor maneira, mas eu poderia estar errado.

A maneira típica de lidar com a classificação topológica é usando um gráfico e, para cada iteração, remova todos os nós que não possuem uma conexão de entrada e, simultaneamente, remova todas as conexões que saem desses nós. Os nós removidos são a saída da iteração. Repita até que você não possa remover mais nós.

No entanto, para obter essas conexões em primeiro lugar, com seu método, você precisaria:

1. Um método (seu comparador) que poderia dizer "isso antes", mas também "sem informações para esses dois"
2. Itera todas as combinações, criando conexões para todas as combinações que o comparador retorna uma ordem.

Em outras palavras, o método provavelmente definiria assim:

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

e depois retorne null Quando não tem uma resposta conclusiva para duas chaves.

O problema em que estou pensando é a parte "iterar todas as combinações". Talvez haja uma maneira melhor de lidar com isso, mas não estou vendo.

Answer 4

Acredito que Lasse V.A resposta de Karlsen está no caminho certo, mas não gosto de esconder o método Compare (ou uma interface separada que não se estende de IComparable<T>).

Em vez disso, prefiro ver algo assim:

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

Dessa forma, você ainda tem uma implementação de IComparer<T> que pode ser usado em outros locais que exijam IComparer<T>.

No entanto, também exige que você indique o relacionamento das instâncias de T entre si com o valor de retorno da seguinte maneira (semelhante a IComparable<T>):

• null - as instâncias não são comparáveis ​​entre si.
• 0 - as instâncias são comparáveis ​​entre si.

• 0 - x é uma chave comparável, mas y não.

• < 0 - y é uma chave comparável, mas x não é.

Claro, você não obterá uma ordem parcial ao passar uma implementação disso para qualquer coisa que espere um IComparable<T> (e deve-se notar que Lasse V.A resposta de Karlsen também não resolve isso), pois o que você precisa não pode ser representado em um método Compare simples que pega duas instâncias de T e retorna um int.

Para finalizar a solução, você deve fornecer um método de extensão OrderBy customizado (bem como ThenBy, OrderByDescendente e ThenByDescendente) que aceitará o novo parâmetro de instância (como você já indicou).A implementação seria mais ou menos assim:

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 para definir o relacionamento de ordem parcial:

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

Compare deve voltar -1 E se x < y, 0 E se x = y, 1 E se y < x e null E se x e y não são comparáveis.

Nosso objetivo é retornar uma ordem dos elementos na ordem parcial que respeita a enumeração. Isto é, buscamos uma sequência e_1, e_2, e_3, ..., e_n dos elementos na ordem parcial de modo que se i <= j e e_i é comparável a e_j então e_i <= e_j. Farei isso usando uma pesquisa de profundidade.

Classe que implementa a classificação topológica usando a primeira pesquisa de profundidade:

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

A classe auxiliar necessária para marcar nós como visitada ao fazer uma pesquisa em profundidade:

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

Não afirmo que essa é a melhor implementação do algoritmo, mas acredito que é uma implementação correta. Além disso, eu não devolvei um IOrderedEnumerable Como você solicitou, mas isso é fácil de fazer quando estamos neste momento.

O algoritmo funciona fazendo uma pesquisa em profundidade através dos elementos adicionando um elemento e para a ordem linear (representada por _sorted no algoritmo) se já adicionamos todos os antecessores de e já foram adicionados à ordem. Portanto, para cada elemento e, se ainda não o visitamos, visite seus antecessores e depois adicione e. Assim, este é o núcleo do 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 exemplo, considere a ordem parcial definida em subconjuntos de {1, 2, 3} Onde X < Y E se X é um subconjunto de Y. Eu implemento isso da seguinte maneira:

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

Então com sets definido como a 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());

Isso resulta na ordem:

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

o que respeita a ordem parcial.

Isso foi muito divertido. Obrigado.

Answer 6

Muito obrigado a todos, a partir da resposta de Eric Mickelsen, criei minha versão, pois prefiro usar valores nulos para indicar nenhuma relação como disse 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));
    }

Então eu tenho a seguinte interface para o comparador

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

e esta classe ajudante

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

Isso permite embelezar um pouco o uso para que meus testes possam se parecer com o seguinte

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