Immutability and Graphs Models - How to create them?

C# is able to get around this with its built-in Lazy<T>. A Lazy is an object whose actual value has not yet been computed - when you construct a Lazy, you pass a factory function as a parameter.

You can ask a Lazy for its value with the Value property. If the factory function has already run, then the already-constructed value is returned. If the factory function hasn't run, then it will run at this time. Whatever the case, the return of the Value property is always the same. Once a particular Lazy's value has been determined, it sticks.

A lazy is an immutable reference to a possibly-not-yet constructed object. It uses mutability internally, but from the outside, it appears to be immutable.

In your case, if you had a Java equivalent to Lazy, you would change your collections from, say, Collection<Y> to Collection<Lazy<Y>>. This would enable an instance of X to refer to some not-yet-constructed instances of Y. And the code which constructs the Xs, Ys, and Zs would not directly build those instances, but would instead build instances of Lazy. These instances would take factory functions as parameters; these factory functions, in turn, would need to reference to some of the Lazy values. This means that, within the context of the function that's constructing and wiring these things together, you'll need to have mutable references to Lazy instances.

To see what I mean, if you try to create a cycle of two objects (I'm not completely up on Java 8, so I might have syntax errors):

Lazy<X> a;
Lazy<Y> b;

a = new Lazy<X>(() -> {
    List<Y> ys = new ArrayList<Y>();
    ys.add(b.getValue());
    return new X(ys);
});

b = new Lazy<Y>(() -> {
    List<X> xs = new ArrayList<X>();
    xs.add(a.getValue());
    return new Y(xs);
});

In practice, I don't think that will work. I think closed-over variables need to be final in Java (this isn't the case in C#). So I think you'd need to actually do this:

final Lazy<X>[] a = new Lazy<X>[1];
final Lazy<Y>[] b = new Lazy<Y>[1];

a[0] = new Lazy<X>(() -> {
    List<Y> ys = new ArrayList<Y>();
    ys.add(b[0].getValue());
    return new X(ys);
});

b[0] = new Lazy<Y>(() -> {
    List<X> xs = new ArrayList<X>();
    xs.add(a[0].getValue());
    return new Y(xs);
});

This works because the two lambdas aren't evaluated immediately. As long as a[0] and b[0] get set to valid values before these lambdas are executed, everything will work fine.

Note that this uses mutability, but mutability in very limited scopes. There's mutability inside the Lazy instances, but these instances appear to be immutable. There's mutability in the wire-up function, but that function will run up front and terminate, whereas the constructed objects can live for much longer. This constrained mutability is, at least for me, an acceptable tradeoff.