Guava: ImmutableValueGraph.Builder does not respect iteration order

[oliviercailloux]

The doc, if I understand it correctly, states that iteration order of successors nodes should follow insertion order in the following case.

Person root = new Person("ROOT");
Person personLeft = new Person("l");
Person personRight = new Person("r");
ImmutableValueGraph.Builder<Person, Integer> builder = ValueGraphBuilder.directed().immutable();
builder.putEdgeValue(root, personLeft, 1);
builder.putEdgeValue(root, personRight, 2);
ImmutableValueGraph<Person, Integer> tree = builder.build();
Iterator<Person> iterator = tree.successors(root).iterator();
LOGGER.info("First successor of root: {}.", iterator.next());
LOGGER.info("Second successor of root: {}.", iterator.next());

I expect, thus, to see “l” as the first successor of root, and “r” as the second one. But I observe the reverse instead.

Here is the Person class.

private static class Person {
    String name;

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

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

(This does not happen, on my computer where I tested this, with String instead of Person, or with Graph instead of ValueGraph.)

[oliviercailloux]

I observed this with guava 28.2-jre. I just switched to 29.0-jre, and this does not happen any more. I am not sure if this means that the iteration order is unpredictable and I just can’t exhibit a problem now by chance (although there is still a problem); or if this bug was corrected in between 28.2-jre and 29.0-jre? I suspect the second case is not the right one, as I checked in the issues before posting mine, but, sorry if I missed something.

[perceptron8]

@oliviercailloux I believe you may have at least partially missed __Changelog__ of https://github.com/google/guava/releases/tag/v29.0

• graph: Made it possible to set a stable incident edge order by calling the newly added method [Value]Graph.Builder.incidentEdgeOrder(ElementOrder.stable()). (7016402)
• graph: Added incidentEdgeOrder() to the [Value]Graph interfaces. (cde576e)

Ordering guarantees are mentioned with "Since 29.0" in javadoc:
https://guava.dev/releases/29.0-jre/api/docs/com/google/common/graph/ElementOrder.html#stable-- ("incidentEdgeOrder(ElementOrder.stable()) guarantees the ordering of the returned collections of the following methods: ...") and https://guava.dev/releases/29.0-jre/api/docs/com/google/common/graph/ValueGraphBuilder.html#incidentEdgeOrder-com.google.common.graph.ElementOrder- ("For immutable graphs, this value is ignored; they always have a stable order.").

Finally, here's how it started: https://github.com/google/guava/issues/2650.

[oliviercailloux]

Thanks. I had seen the issue, but didn’t look at it carefully because it seemed irrelevant to the case of Immutable structures.

I still believe these discussions to be only vaguely related to my case, as I deal with immutable graph builders, which, as you quoted, should not be affected by the change.

Anyway, it’s quite possible that closing this for now in wait that someone can reproduce the problem would be a reasonable reaction.

[perceptron8]

I still believe these discussions to be only vaguely related to my case, as I deal with immutable graph builders, which, as you quoted, should not be affected by the change.

@oliviercailloux Please review linked javadoc once more. Immutable graph builders _are_ affected. Before 29.0, all incident edges were implicitly ElementOrder.unordered(). There were no guarantees at all. Since 29.0 one can choose between ElementOrder.unordered() (which is the default for mutable graph / network builders) and ElementOrder.stable() (which is the default - and the only possible option [edit] - for immutable graph / network builders).