Eu estou procurando uma implementação Java de uma estrutura de dados que contém uma coleção de elementos para os quais umordenação parcial é definido, e que permite iterar sobre esses elementos em algunsordem topológica (qualquer uma das ordenações possíveis é boa; de preferência, uma ordenação estável à medida que o conteúdo da coleção muda).

O ideal seria implementar umCollection<E>, Set<E>ouSortedSet<E> interface e suporte todos os métodos na interface. Em termos de especificação do total de pedidos, a coleção poderia ser instanciada com umComparator<E>, eo comparador poderia lançar uma exceção (ClassCastException?) se dois elementos comparados não forem solicitados em relação um ao outro. Como um bônus, ele lançaria uma exceção se um elemento sendo inserido produziria uma anomalia de ordenação (um ciclo no gráfico ordenado de elementos).

Então, sim, o que eu quero é um tipo topológico, mas eu gostaria de umobjeto de coleção que mantém essa ordem de classificação com cada inserção / remoção, da mesma forma que o SortedSet mantém uma coleção na ordem de classificação.

Será que algo assim existe? Em alguma biblioteca de código aberto?

Referências:

http://en.wikipedia.org/wiki/Partially_ordered_set

http://en.wikipedia.org/wiki/Topological_sorting

Atualizar

Eu acabei indo com uma abordagem diferente para o meu problema, onde eu não vou precisar de um poset, depois de perceber as implicações de desempenho dos meus requisitos (e vários outros problemas que eu não consegui resolver, usando o poset). Confiar no comparador para determinar a ordenação entre os elementos significa que, para a inserção de elementos, tenho de consultar o comparador em relação a todos os elementos existentes, custando O (n) por inserção.

Se o desempenho não fosse muito importante (é), e se o número de elementos fosse limitado a algo razoável (não é), eu acho que teria adotado a abordagem sugerida por Willie, embora talvez com minha própria implementação gráfica e topológica classificar a implementação para minimizar as dependências.