How can I traverse a Guava graph in a deterministic order?

Is there a way to traverse a Guava Graph in a deterministic order?

I’ve attempted to do it via this test:

import com.google.common.graph.ElementOrder;
import com.google.common.graph.Graph;
import com.google.common.graph.GraphBuilder;
import com.google.common.graph.Traverser;

import java.util.Random;

public class TestGraph {
    private static final Random random = new Random();

    static class Node { //Node class with volatile hashcode
        private final int hashcode = random.nextInt();
        private final String name;

        public Node(String name) {this.name = name; }

        @Override public String toString() {return name; }

        @Override public int hashCode() {return hashcode;}
    }

    public static void main(String argv[]) {
        Node root = new Node("root");
        Graph<Node> graph = GraphBuilder.directed()
                .nodeOrder(ElementOrder.insertion())
                .<Node>immutable()
                .putEdge(root, new Node("one"))
                .putEdge(root, new Node("two"))
                .putEdge(root, new Node("three"))
                .build();

        //Print the nodes in traversal order.
        Traverser.forGraph(graph).depthFirstPostOrder(root)
                .forEach(x->System.out.println(x));
    }
}

Each time it evaluates in a different order. I think the root cause is that the graph successors are not ordered.

1
Leave a Reply

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Jason Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Jason
Guest

You can see some discussion on this topic, and hacks to get what you want, here: https://github.com/google/guava/issues/2650

That said, we’ve recently been looking into some alternatives for providing this capability, and it seems likely that it will be possible in an upcoming Guava release. It will probably come with some extra memory overhead (10-20%), though.

If we do provide this capability, it will almost certainly be specified via the GraphBuilder as a property of the graph.