14

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.

8
  • 1
    Depending on which sort algorithm is being used, returning 0 for incomparable elements might work. If you have a Comparator throw exceptions, you won't be able to use it with the standard library. Might as well define your own interface.
    – Thilo
    Sep 11, 2012 at 4:37
  • I guess it is Duplicate of stackoverflow.com/questions/2739392/… Sep 11, 2012 at 4:42
  • I am not asking for a topological sort algorithm. Please read the question carefully.
    – JimN
    Sep 11, 2012 at 4:45
  • There can be multiple valid linear extensions of any given partial order. You can usually generate a valid one by initiating with a seed extension that already satisfies the partial order, and then picking random elements to swap so long as the swap does not violate the partial order.
    – obataku
    Sep 11, 2012 at 4:51
  • 1
    @Thilo from the specification for Comparator... "A comparison function, which imposes a total ordering on some collection of objects."
    – obataku
    Sep 11, 2012 at 4:54

2 Answers 2

4

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.

1
  • Haven't looked at the library, but I think the edges could be created internally with no problem -- just relying on the comparator to determine if two elements are comparable and which one precedes the other to determine the presence and directionality of the edge.
    – JimN
    Sep 12, 2012 at 4:49
0

FYI, here's one in the JDK itself that you could potentially (re)use: PartiallyOrderedSet.java

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.