How to get the same output order from a Java Collection

Question

I have some code:

Collection<MyGraph.MyVertex> vertCollection = graph.getVertices(); 

where getVertices is part of the JUNG package and is defined like:

public interface Hypergraph<V, E> {
    Collection<E> getEdges();

    Collection<V> getVertices();
...
...
}

> If I print out the collection I may get something like [v1,v2,v4,v3]
> and on another run something like [v2,v3,v1,v4]

That gives me back a list of vertices in random order each time. Because of this my results elsewhere in the code are not repeatable and it gets hard to trace.

I want to get the elements back in order each time the same way. My current guess is I'd have to convert the collection to some sort of data structure that preserves order then sort it so that the results are repeatable but is there a better way to do this? (I'm not sure if converting from a Collection to something else like an array would break the code elsewhere as I'm new to Collections). Any help would be great!

Answer 1

I understood that Hypergraph.getVertices() is a library method that you cannot modify. So you have to manipulate the result from a call to that method. Sorting is the option here, as suggested by Yamil's answer.

But this requires that either your implementation of <V> (MyGraph.MyVertex in your sample) will implement java.lang.Comparable, or that you provide an implementation of java.util.Comparator that ensures a static sort order for your vertices.

And java.util.Collections.sort() takes a List as argument; an instance of List is always an instance of Collection, too, but unfortunately not every instance of Collection is an instance of List – it could be a Set or even something absolute strange …

Considering this, and assuming that VertComparator is the comparator I talked about, your solution might look like this:

…
VertComparator comparator = new VertComparator();
List<MyGraph.MyVertex> vertCollection = new ArrayList<>( graph.getVertices() );
Collections.sort( vertCollection, comparator );
…

If all other code in your program does only deal with Collection instances of vertices (that means that no hidden assumptions are made somewhere what kind of collection it is), you should be safe.

Unfortunately, even if the returned Collection is already an instance of List (… instanceof List yields true), Collections.sort() may not work: create your list with List.of() and try to sort it …

Quite often, when a method returns a Collection that somehow represents the internal status of the object, this is an unmodifiable collection. Obviously sorting will fail here, too. So the only safe way is to copy the result and sort the copy.

Answer 2

You could use something like this:

List<String> names = Arrays.asList("Alex", "Charles", "Brian", "David");

//Natural order
Collections.sort(names);    //[Alex, Brian, Charles, David]

//Reverse order
Collections.sort(names, Collections.reverseOrder());    [David, Charles, Brian, Alex]   

Answer 3

Just use an ArrayList to implement the Collection. ArrayList's behave just like an array. They come out in the same order they are put in.

Collection<E> list = new ArrayList<>();
Collection<V> list = new ArrayList<>();

Answer 4

As you've seen, JUNG 2.x doesn't provide this option natively, so your only real option is to copy the output and sort it, and that assumes that you have a Comparator that makes sense for your vertex type. (Nor does this make it easy to preserve the original insertion order.)

The Guava graph library, also known as common.graph, is used by JUNG 3.0 (in development) and does support stable ordering, on a couple of different levels:

1. Immutable graphs' accessors each return a Set with a stable ordering.

2. If you want a mutable graph, the built-in implementations, which are constructed using GraphBuilder (and its sibling types) can specify using nodeOrder() that the graph nodes should be any of the following:

   • insertion-ordered (default)
   • unordered
   • naturally ordered (if your node type implements Comparable)
   • sorted

   For Networks (which are analogous to the JUNG Graph type) you can impose the same ordering on the edges of the graph.

3. You can also construct a mutable graph which provides stable-ordering guarantees for some of the node-level accessors (successors(), predecessors(), etc.) using incidentEdgeOrder() on the graph Builder.

(Disclaimer: I co-created JUNG and still maintain it, and also created common.graph.)