Graphs: ensure and document consistent behavior for invalidated view-collections

[ineuwirth]

While I was investigating #6478, I encountered the following case that might be a bug:

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

graph.putEdge(1, 2);

Set<EndpointPair<Integer>> n1IncidentEdges = graph.incidentEdges(1);
assertThat(n1IncidentEdges).hasSize(1);

graph.removeNode(1);
assertThatIllegalArgumentException()
        .isThrownBy(() -> n1IncidentEdges.size()); // implementations of `Collection.size` should not throw any Exception

In case of undirected graph the returning view of Graph.incidentEdges might not fully adhere the collection API contract as it can throw an exception it is not supposed to throw. This might happen as IncidentEdgeSet.size calls BaseGraph.adjacentNodes that throws IAE in case the node is no longer an element of the graph.

[ineuwirth]

Same goes for directed graphs.

[kevinb9n]

Thanks for being eagle-eyed and reporting this.

Although many Collection methods explicitly invite implementations to throw various unchecked exceptions, the reality is that any method can throw any unchecked exception at any time for any reason -- and in fact should if the alternative is to return a bogus value.

Returning zero for size indicates that the node in question is an island in the graph, which would be wrong here, and could easily lead to bugs. So the only way to address this concern would be to not implement Collection at all, which (a) it's too late for, and (b) is to "throw the baby out with the bathwater".

So... it seems to me like what we should do is make sure that all the methods on view-collections in this circumstances do throw. And, we should document this situation much better in a couple ways.

[ineuwirth]

I am in strong agreement with the proposition to enhance the documentation. Specifically, what I found lacking in the Javadoc for Graph was an explicit mention that the collections returned are actually views, rather than immutable snapshots captured at the moment of invoking the respective method. Granted, the page at https://github.com/google/guava/wiki/GraphsExplained#accessor-methods does touch upon this topic, but it requires some steps to navigate to it. For instance, currently, the Javadoc for Graph.incidentEdges reads:

Returns the edges in this graph whose endpoints include node.

This phrasing could easily lead one to interpret that the method calculates the edges, places them into an immutable or unmodifiable container, and then returns them and that's all.

I appreciate the fail-fast approach being adopted here. I'm curious, was this inspired by any lessons learned from using Multimap views? The graph example above can be more or less reformulated as follows:

Multimap<String, String> multimap = HashMultimap.create();

multimap.put("N1", "N2");
Collection<String> viewOfN1 = multimap.get("N1");

multimap.keys().remove("N1");
assertThat(viewOfN1).isEmpty();

In this scenario, the view does not throw an exception if the element it was associated with no longer exists.

I'm inclined to agree that employing the fail-fast approach and throwing exceptions when methods are called on a view that is no longer valid is likely the best solution. However, could we introduce a more specific exception type than IllegalArgumentException, perhaps something like InvalidViewException? Otherwise, how is a method without any parameters, such as size(), supposed to throw an IllegalArgumentException? 😃

[kevinb9n]

I am in strong agreement with the proposition to enhance the documentation.

I'm in agreement with your agreement :-)

In this scenario, the view does not throw an exception if the element it was associated with no longer exists.

Multimap.get(k) (or at least our implementations of it) does something highly questionable; it always returns the values mapped from k even if k had been fully removed from the multimap and later added back. So it doesn't need to throw because it can actually give a solid answer.

That might have been a mistake. For one thing, the key can't get GC'd until that collection does, which is something the user would be unlikely to have thought about.

I think we intentionally didn't want to repeat that for Graphs.

I'm inclined to agree that employing the fail-fast approach and throwing exceptions when methods are called on a view that is no longer valid is likely the best solution. However, could we introduce a more specific exception type than IllegalArgumentException, perhaps something like InvalidViewException? Otherwise, how is a method without any parameters, such as size(), supposed to throw an IllegalArgumentException? 😃

True point, this is what IllegalStateException is made for. Changing the exception type now wouldn't necessarily be catastrophic, but I'm undecided; if it causes anyone even a little bit of trouble I might wonder if it was worth it.

[jrtom]

Thanks for your patience (I was out for a week with an injury and have only just now made the space to reply), and especially thanks for spotting and reporting this issue.

That said, there are (I think) at least two different issues here which we should probably address individually, and perhaps in separate issues:

Sets as views
(b) Do we want common.graph to contractually guarantee that returned Sets are views? (Currently, we do not, which is why the documentation is somewhat indirect.)

https://github.com/google/guava/wiki/GraphsExplained#accessor-behavior states that it is technically valid for an implementation of the common.graph interfaces to have any of the following behaviors for its accessors:

1. immutable copy
2. unmodifiable view
3. mutable copy
4. modifiable view

but goes on to say that the provided implementations use (2) (i.e., return unmodifiable views).

This may be a case where we provided implementation flexibility that no one actually needs. OTOH, I suspect that if anyone did want to create their own implementation of these interfaces, they might well choose to go with (3) or (1); creating copies is less efficient (and often less convenient for the user), but it makes for a much simpler implementation. (This library's predecessor, JUNG used (3).)

View invalidation
(b) What should the behavior be of a view returned by a graph accessor [0] parameterized by an element n, after n is removed from the graph?

Options in increasing order of implementation difficulty:

• state that the behavior is undefined?
  • requires only a documentation update
• state that the view will report as though it's empty?
  • this is already mostly true, modulo the bugs raised in Confusion on contents of saved Graph.adjacentNodes(n) if n is eventually removed #6478 and in this issue
• throw on invocation
  • this would probably require a fair amount of work and might prevent us from using Guava's SetView class (an implementation of Set used by Guava's set operations).

At this stage in Guava's development, I'm tempted to go with one of the first two options.

Feedback/suggestions welcome.

---

[0] Relevant methods [1] in all types:

• incidentEdges(n)
• adjacentNodes(n)
• predecessors(n), successors(n)

Relevant methods, Network only:

• adjacentEdges(e)
• incidentNodes(e)

[1] Very nitpicky related note: while degree(N) states that it is equivalent to incidentEdges(node).size() (for an undirected graph), the fact that these methods exist breaks the view abstraction a bit: there's no way to update, or invalidate, the return value of this accessor in this case:

graph.putEdge(u, v); // assume this is the first edge

int uDegree = graph.degree(u);  // returns 1
int vDegree = graph.degree(v); // returns 1
Set<EndpointPair<N>>  uIncident = graph.incidentEdges(u);
graph.removeNode(u);

// uDegree and vDegree each are still 1
// (although if we were to call the populating methods again we'd get IAE and 0, respectively)

I don't think that there's anything to be done here; the degree() methods are much more convenient than their equivalent formulations as Set.size() calls (or, worse, arithmetic on such calls). Hopefully it's obvious to anyone that the return value from the *degree methods, being a primitive type, is not going to update or become invalid in response to graph changes. :P :)

(If you want to get even more of a headache, consider that we could invalidate a returned EndpointPair if the corresponding connection no longer existed in the graph. Fortunately I don't think that anyone expects this.)