Java部分订购集合<E>

Question

我正在寻找一个数据结构的 Java 实现，该数据结构包含定义了 partial ordering 的元素集合，并允许以某种 topological order 迭代这些元素（任何可能的排序是很好；最好是随着集合内容的变化而稳定排序）。

理想情况下，它将实现一个

Collection<E>

、

Set<E>

或

SortedSet<E>

接口，并支持接口上的所有方法。在指定总排序方面，集合可以用

Comparator<E>

实例化，如果被比较的两个元素没有相互排序，比较器可以抛出异常（

ClassCastException

？）。作为奖励，如果插入的元素会产生排序异常（元素有序图中的循环），它将抛出异常。

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

这样的东西存在吗？在一些开源库中？

参考资料：

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

更新

在意识到我的要求对性能的影响（以及我无法完全解决的各种其他问题，使用偏序集）之后，我最终采用了一种不同的方法来解决我不需要偏序集的问题。依靠比较器来确定元素之间的顺序意味着对于元素插入，我必须针对每个现有元素咨询比较器，每次插入的成本为 O(n)。

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

Answer 1

有向无环图是否足以满足您的需求？我知道这通常不会捕获偏序集，但是您提到要排除图形循环。

如果是这样，您可以查看 JGraphT：http://jgrapht.org/

有一个用于拓扑排序的图迭代器。

请注意，有向图不是 java.util.Collections，但您可以获取顶点，这是一个 java.util.Set。如果你需要数据结构本身是一个集合，你可能可以用一个薄包装器包装一个 JGraphT 有向图，它is一个集合，将顶点视为元素。

这里的潜在缺点是您必须显式创建边缘，这可能会或可能不会被您的应用程序接受。

Answer 2

仅供参考，这是 JDK 本身中的一个，您可以（重新）使用它：PartiallyOrderedSet.java