Bug in TopologicalOrderIterator about jgrapht

[Isaac-Kleinman]

Why are you setting CrossComponentTraversal to true? if you remove that line from your code, the iterator will traverse over all components and won't throw that exception.

[altenbernd]

According to AbstractGraphIterator's JavaDoc, setting CrossComponentTraversal to true indicates that a graph should be traversed across connected components. This is the behaviour I need, because the graphs I work with may consist of several unconnected subgraphs. After looking at the code, and I may be wrong here, I think that I have to set that flag, at least that's what line 202 in CrossComponentIterator suggests.

[Isaac-Kleinman]

I'm not disputing the existence of a bug. I'm just saying that it seems you can get the desired behavior (cross component traversal) without setting the crossComponenetTraversal flag.

[altenbernd]

Interesting. If I do not set the CrossComponentTraversal flag (or set it to false explicitly), I still get an exception in the 4th call to iterator.next(). I also get the same behaviour when omitting the edges, that is, the graph consists of only three nodes, but no edges. But, as you suggested, the traversal yields all three nodes.

[Isaac-Kleinman]

The exception thrown at the fourth call to next() (as opposed to hasNext() ) on a graph with 3 nodes should not come as a surprise...

[altenbernd]

I agree, that is not surprising; but the fact that iterator.hasNext() returns true 4 times is (see comment in the code snippet).

[Isaac-Kleinman]

Yes, but as discussed, omitting the

iterator.setCrossComponentTraversal(true);

will cause iterator.hasNext() to return true only 3 times.

[jsichi]

If someone wants to submit a pull request to override setCrossComponentTraversal (probably make it a nop?), along with this test case, that would be an improvement.

[altenbernd]

After running the initial test using the code of the current master branch (and not that of version 0.8.3, as I originally did), I have come to realize that indeed, as @Isaac-Kleinman noted, omitting the call to setCrossComponentTraversal makes iterator.hasNext() return true only 3 times. So that problem seems to have been fixed already somehow; I apologize for the misunderstanding.

However, if I also omit the graph's edges (after which it will consist of 3 unconnected components), the graph is still fully traversed, that is, all three nodes are visited, which is probably not intended, or at least not in line with the JavaDoc.

So there appear to be two problems: the exception thrown when enabling crossComponentTraversal, and the full traversal of a disconnected graph even when crossComponentTraversal is not enabled.

[Isaac-Kleinman]

At least in the case of TopologicalOrderIterator, I believe traversing all of the components is actually the expected behavior; thus, a sensible default (does the Javadoc indicate somewhere that the default is false?)

The exception thrown by enabling crossComponentTraversal can be dealt with by making it a nop as @jsichi suggested . That leaves us with the issue of disabling cross component traversal when the argument to setCrossComponentTraversal() is false.

[altenbernd]

After some further analysis, it seems that the problem is caused by the way in which CrossComponentIterator and TopologicalOrderIterator interact on a DAG with more than one source node.

To understand the problem, consider the following example. We want to traverse the DAG g that has only two nodes a and b, but no edges; that is, g is a disconnected DAG with two components. When creating a TopologicalOrderIterator for g, all of g's source nodes (a and b) are added to a queue (in initialize()), which is used to provide vertices in calls to provideNextVertex(). This already means that the traversal will encounter all vertices in components of g that have at least one source node, which makes the notion of crossComponentTraversal a bit questionable.

In the call to CrossComponentIterator's constructor one of the nodes in the queue is used as the start vertex, say, a. In the following traversal (via hasNext() and next()), the start vertex is encountered, which causes TopologicalOrderIterator to mark a as seen (via putSeenData()). Since the queue is not empty yet, another vertex (b) can be provided in the second call to next(). However, b is not marked as seen, because it has not been encountered by traversing an edge. The reason for this is that in CrossComponentIterator's next(), only vertices that can be reached via an edge starting at nextVertex are encountered and thereby marked as seen (by a call to addUnseenChildrenOf()), but not nextVertex itself.

After providing b, the TopologicalOrderIterator's queue is empty, and so isConnectedComponentExhausted() returns true. If crossComponentTraversal is enabled, then CrossComponentIterator's hasNext() will try to find another unseen vertex by using its own iterator over g's vertex set. Since b has not been marked as seen, it becomes the next vertex and is encountered. This, however, does not cause TopologicalOrderIterator to add b to the empty queue in its decrementInDegree(), because the in-degree of b is already 0. As a consequence, hasNext() returns true, but next() cannot provide a vertex, which causes TopologicalOrderIterator's provideNextVertex() to throw an exception.

As I see it, the solution to this is an additional check in CrossComponentIterator's next() to encounter the next vertex if it has not been marked as seen yet.

Another problem is the traversal in topological order of a graph that contains a connected component in which every vertex has an in-degree of at least 2, if crossComponentTraversal is enabled. When the first vertex of such a component is encountered, TopologicalOrderIterator will decrement its in-degree internally, but not add it to the queue, since its new in-degree will not be 0. The resulting problem is then as above.

As suggested by @jsichi, this is fixed by making setCrossComponentTraversal a NOOP (actually, it must always set the flag to false).

I have fixed these problems and added some test cases, which are now in the master branch of my fork (probably should have used a topic branch, but I'm very new to git, github, and DVCS in general).

I would like to send a pull request; should I first merge in the latest changes from upstream into my fork, to get my origin up-to-date, or is that unnecessary?

[jsichi]

Yes, start from the latest upstream changes if you want to make sure the pull request can be merged without conflict.

[d-michail]

Closing due to PR #374.