Java部分有序集合< E> [英] Java partially ordered Collection<E>

问题描述

我正在寻找一个数据结构的Java实现，它保存了定义了部分排序的元素集合，并允许在某些拓扑结构中迭代这些元素

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

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

这样的东西是否存在？在某些开源库中？

参考文献：

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

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

更新

我最后对我的问题采用了不同的方法， poset，在实现我的需求的性能影响（和各种其他问题，我不能完全解决，使用poset）。依靠比较器来确定元素之间的顺序意味着对于元素插入，我必须对每个现有元素查询比较器，每次插入花费O（n）。

如果性能不是很重要（它是），如果元素的数量有限的东西合理（不是），我想我会采取威利建议的方法，虽然也许与我自己的图实现和拓扑

解决方案

有向无环图是否足够满足您的需求？我知道这不会捕获posets一般，但你提到要排除图周期。

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

有一个图形迭代器用于拓扑排序。 p>

请注意，有向图不是java.util.Collections，而是可以抓取顶点，这是一个java.util.Set。如果你需要的数据结构本身是一个集合，你可能可以用一个薄的包装器来封装一个JGraphT有向图，是一个集合，将顶点作为元素。

这里潜在的缺点是，你必须显式地创建边，这对于你的应用程序来说可能是不可接受的。

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).

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).

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?

References:

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

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

Update

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.

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.

解决方案

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.

If so you might look at JGraphT: http://jgrapht.org/

There's a graph iterator for topological sorts.

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>的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！