问题描述
我正在寻找一种数据结构的 Java 实现，它包含定义了 部分排序 的元素集合，并允许在某些 拓扑中迭代这些元素order(任何可能的排序都可以；最好是随着集合内容的变化而稳定排序).
I am looking for a Java implementation of a data structure which holds a collection of elements for which a partial ordering is defined, and which allows one to iterate over those elements in some topological order (any of the possible orderings is fine; preferably a stable ordering as the contents of the collection changes).
理想情况下，它将实现 Collection、Set 或 SortedSet 接口并支持所有接口上的方法.在指定总排序方面，可以使用 Comparator 实例化集合，如果比较两个元素，比较器可能会抛出异常 (ClassCastException?)没有相对于彼此排序.作为奖励，如果插入的元素会产生排序异常(元素有序图中的循环)，则会引发异常.
Ideally it would implement a Collection<E>, Set<E>, or SortedSet<E> interface and support all of the methods on the interface. In terms of specifying the total ordering, the collection could be instantiated with a Comparator<E>, and the comparator could throw an exception (ClassCastException?) if two elements being compared are not ordered with respect to each other. As a bonus, it would throw an exception if an element being inserted would produce an ordering anomaly (a cycle in the ordered graph of elements).
所以是的，我想要的是拓扑排序，但我想要一个 collection 对象，该对象在每次插入/删除时都保持该排序顺序，类似于 SortedSet 如何按排序顺序维护集合.
So yeah, what I want is a topological sort, but I would like a collection object that maintains that sort order with every insertion/removal, similarly to how SortedSet maintains a collection in sorted order.
这样的东西存在吗?在一些开源库中?
Does something like this exist? In some open source library?
参考资料:
http://en.wikipedia.org/wiki/Partially_ordered_set
http://en.wikipedia.org/wiki/Topological_sorting
更新
在意识到我的要求对性能的影响(以及我无法完全解决的各种其他问题，使用 poset)之后，我最终采用了一种不同的方法来解决我不需要 poset 的问题.依靠比较器来确定元素之间的顺序意味着对于元素插入，我必须针对每个现有元素咨询比较器，每次插入的成本为 O(n).
I ended up going with a different approach for my problem where I won't need a poset, after realizing the performance implications of my requirements (and various other issues that I couldn't quite resolve, using the poset). Relying on the comparator to determine the ordering among elements means that for element insertion, I have to consult the comparator against every existing element, costing O(n) per insertion.
如果性能不是很重要(确实如此)，并且如果元素的数量限制在合理的范围内(不是)，我想我会采用 Willie 建议的方法，尽管可能使用我自己的图表实现和拓扑排序实现以最小化依赖关系.
If performance were not very important (it is), and if the number of elements was bounded to something reasonable (it isn't), I think I would have taken the approach suggested by Willie, although perhaps with my own graph implementation and topological sort implementation to minimize dependencies.
推荐答案
有向无环图是否足以满足您的需求?我知道这通常不会捕获 poset，但您提到要排除图形循环.
Would a directed acyclic graph be sufficiently general for your needs? I know that this doesn't capture posets generally, but you mentioned wanting to exclude graph cycles.
如果是这样，您可以查看 JGraphT:http://jgrapht.org/
If so you might look at JGraphT: http://jgrapht.org/
有一个用于拓扑排序的图迭代器.
There's a graph iterator for topological sorts.
请注意，有向图不是 java.util.Collections，但您可以获取顶点，即 java.util.Set.如果你需要数据结构本身是一个集合，你可以用一个是一个集合的瘦包装器来包装一个 JGraphT 有向图，将顶点视为元素.
Note that the directed graphs aren't java.util.Collections, but you can grab the vertices, which are a java.util.Set. If you need the data structure itself to be a Collection, you could probably wrap a JGraphT directed graph with a thin wrapper that is a Collection, treating the vertices as elements.
这里的潜在缺点是您必须显式创建边缘，这可能会或可能不会被您的应用程序接受.
The potential drawback here is that you have to create edges explicitly, which may or may not be acceptable for your application.
这篇关于Java 部分有序集合<E>的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！