ImmutableGraph should have ImmutableSet of nodes and edges

[oliviercailloux]

Please consider overriding ImmutableGraph#nodes() so that it returns an ImmutableSet, to make the contract clearer. Similarly for edges().
(Somewhat related to #3034.)

[netdpb]

The implementation does not currently use an ImmutableSet. It is an unmodifiable set.

[jrtom]

@netdpb is correct, and it would complicate our existing implementations to support returning an ImmutableSet in those cases. We might consider doing this, but not soon.

[oliviercailloux]

I can work on this with a student in the coming weeks. Would you be willing to review patches towards implementing this?

[jrtom]

@oliviercailloux I should have stated this more clearly: it's not just that it would complicate our existing implementations, but it would add unnecessary overhead.

In some cases, there are backing Sets that are, in fact, ImmutableSets. Bubbling that type up to the top API layer would require some work, and some duplicated code, but could be done.

In other cases, the backing sets are actually unions of other sets (e.g., adjacentNodes for a directed graph are a union of predecessors and successors). In order to be able to return an ImmutableSet in that case, we'd need to either create a copy of the union, or store that union separately.

In sum, I don't think that the advantages of being able to present an ImmutableSet would outweigh the disadvantages.

It's possible that I've missed something, in which case I encourage you to reopen this issue and outline how you think that this could be done.

Thanks!

[oliviercailloux]

Please correct me if I missed something obvious, but it seems possible to support this use case with ImmutableSet instances with no loss of performance.

Here is a sketch, details are obviously to be worked on, but I don’t see why it couldn’t be made to work.

• I’d keep the current logic of using DirectedGraphConnections and its map of adjacentNodeValues that contains both predecessors and successors, except it would be an ImmutableMap (just need to slightly change DirectedGraphConnections#ofImmutable).
• For adjacentNodes, we simply need to use an ImmutableMapKeySet (no copy involved).
• And for predecessors and successors, I’d create a child of ImmutableSet, say, FilteringImmutableMapKeySet, with a filtering ability (thus FilteringImmutableMapKeySet would not be an IndexedImmutableSet, contrary to ImmutableMapKeySet), so that it would “see” only the right kinds of nodes, as is currently done in the set view returned by DirectedGraphConnections#predecessors() for example.

(Of course, calling asList() on the ImmutableSet returned by predecessors() or successors() would still need to compute a copy, but that’s not a drawback compared to the current approach: if the user wants her set of connected nodes as a random-access list, she has to copy it in all cases, currently, including with adjacentNodes().)

I understand the concern with complexifying the code, but it seems on the contrary that this requires only relatively slight modifications of the code and the addition of a class, FilteringImmutableMapKeySet, that will not be overly complicated and that actually could be useful in other cases.

[oliviercailloux]

BTW, I can’t reopen the issue.