Confusion on contents of saved Graph.adjacentNodes(n) if n is eventually removed

[jbduncan]

I recently found myself writing this code.

MutableGraph<Integer> graph = GraphBuilder.undirected().build();
graph.addNode(1);

Set<Integer> adjacentNodesView = graph.adjacentNodes(1);
System.out.println(graph.edges()); // []
System.out.println(adjacentNodesView); // []
System.out.println(graph.adjacentNodes(1)); // []

graph.putEdge(1, 2);
System.out.println(graph.edges()); // [[2, 1]]
System.out.println(adjacentNodesView); // [2]
System.out.println(graph.adjacentNodes(1)); // [2]

graph.removeNode(1);
System.out.println(graph.edges()); // []
System.out.println(adjacentNodesView); // [2] <-- Unexpected! Should be []?
System.out.println(graph.adjacentNodes(1)); // throws IAE

I was surprised by the contents of adjacentNodesView at the end, because if graph.edges() is cleared, then I intuitively expected the adjacent nodes to be cleared too.

But then I thought about it some more and realised this is a weird grey area, because if a user calls graph.adjacentNodes(1) again, then an IAE is rightfully thrown to prevent bugs.

I'm torn between adjacentNodesView being [] or [2] in this case.

@jrtom, what do you think?

[netdpb]

It seems to me that the set view of adjacent nodes of a node that was since removed from the graph is invalid, and its behavior could be undefined. It might be nice to invalidate that set-view, such that all calls throw IllegalStateException, but I don't know how urgent that might be.

[jrtom]

That is an interesting one, for sure.

Logically, the behavior is undefined (that is, we've never formally defined that behavior and I think that there are a couple of reasonable choices we could make, including both throwing ISE and returning the empty set), but we've never formally declared it to be undefined. We might consider that solution, although it's not very satisfying.

As a practical matter, I am surprised that adjacentNodesView isn't empty; as a live view I would expect it to have been cleared. This seems like it might indicate the presence of a bug that might have other manifestations.

Since adjacentNodes() is defined to return the set union of predecessors() and successors() (and is implemented via Sets.union() at present), it would take a bit of digging to figure out exactly where this is breaking down, as there are a few layers involved.

I don't have the bandwidth to look into this right now, so if you'd like to take a look we'd appreciate your insights. :)

[jbduncan]

@jrtom Sure! I've just had a look, and I think it's breaking down somewhere at the end of StandardMutableValueGraph.removeNode, on line 153.

I've observed that when the respective line of code is run...

    nodeConnections.remove(node);

...then that is when subsequent calls to graph.adjacentNodes(node) throws an IAE, and when I'd expect any existing adjacent node views of node to become empty or throw ISEs.

I don't know how to achieve this yet, as I'd need to understand how GraphConnections works and how (Value)Graph::adjacentNodes accesses the underlying graph connections. If I find time to look into this further, I'll report any findings here.

[jrtom]

@jbduncan Thanks for taking a look. I think that where you started to look is the right place to start. That said, note that line 139 (same file, a few lines previous) is a loop that removes all the predecessors* from the node to be removed, and that's the operation that I would have expected to clean up those relationships.

In other words, before we remove the node, we remove all the incident edges...which should mean that any views that we have of the predecessors/successors of that node should be empty.

So it appears that the view we're constructing is not as transparent as it should be.

It might be illuminating to try that same test with

• the successors() (or predecessors()) method rather than adjacentNodes() (to remove the Sets.union() from the equation)
• a directed graph

That might help to narrow down the source of the problem.

*The subsequent loop removes all the successors, for directed graphs.

[ineuwirth]

I've delved into this matter and might have reached the bottom of it. Please find my findings described in comment and code in this PR: #6553. In short: the confusion arises because the removeNode function, which deletes node connections, can leave outdated references in the GraphConnections that is associated with the node to be deleted. Both directed and undirected graphs are affected but networks are apparently not.

[jbduncan]

@ineuwirth Wow, thank you very much for looking into this, much appreciated!

I'll leave it to the Guava maintainers to decide the next steps, but in my experience this sort of bug fix is usually accepted after being reworked a bit internally at Google, so fingers crossed. 🤞