相关疑难解决方法(0)

我正在寻找一个数据结构的Java实现,它包含一个元素集合,其中定义了一个部分排序,并允许一个元素以某种拓扑顺序迭代这些元素(任何可能的排序都很好;最好是一个稳定的订购作为集合的内容更改).

理想情况下,它将实现一个Collection<E>,Set<E>或SortedSet<E>接口,并支持接口上的所有方法.在指定总排序方面,可以使用a来实例化集合Comparator<E>,并且ClassCastException如果被比较的两个元素没有相对于彼此排序,则比较器可以抛出异常(？).作为奖励,如果插入的元素会产生排序异常(元素的有序图中的循环),它将抛出异常.

所以是的,我想要的是一个拓扑排序,但是我想要一个集合对象,它在每次插入/删除时保持排序顺序,类似于SortedSet如何按排序顺序维护集合.

这样的事情存在吗？在一些开源库中？

参考文献:

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

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

更新

在我意识到我的要求的性能影响(以及我无法解决的各种其他问题,使用poset)之后,我最终采用了不同的方法解决了我的问题,我不需要一个poset.依靠比较器来确定元素之间的顺序意味着对于元素插入,我必须针对每个现有元素查询比较器,每次插入花费O(n).

如果性能不是很重要(确实如此),并且如果元素的数量被限制在合理的范围内(事实并非如此),我想我会采用Willie建议的方法,尽管可能使用我自己的图形实现和拓扑排序实现以最小化依赖性.

我有一组序列化到文件的项目。有些项目可以依赖其他项目，但不允许循环引用。因此，它们需要以某种方式进行序列化，如果A依赖于B，B则首先在文件中进行序列化。

我写了我的Comparator，它使用一个reliesOn()函数来确定两个项目是否链接：

Collections.sort(itemsToSort, new Comparator<Item>() {
    @Override
    public int compare(Item first, Item second) {
        boolean firstReliesOnSecond = reliesOn(first, second);
        if (firstReliesOnSecond) {
            return 1;
        }
        boolean secondReliesOnFirst = reliesOn(second, first);
        if (secondReliesOnFirst) {
            return -1;
        }
        return 0;
    }
});

这适用于某些情况，但不是全部。在调试中，很明显排序依赖于 的传递性质Comparator，并且可以理解不会比较所有可能的项目配对。

例如，有五个项目A通过E，如果：

A -> B
B -> E
C
D
E

那么一种可能的排序是：

E, B, A, C, D

至少，E …