ccp999/Expr4j

Spurious GraphCycleException

Opened this issue · 1 comments

sgilbertson commented

I'm working with an admittedly heavily-modified Expr4j, but I haven't touched Graph.java, and I'm getting GraphCycleExceptions like:
Circular reference found: G71 - I71 (visited: [J71, H71, I71, G71, D71, E71, $B$50])

It's happening in cases when there is no real circular reference. It seems like the problem is that "visited" as seen in Graph.checkCycle includes a whole tree of visited nodes, whereas a true circular reference would require all of the ranges in that list to be in a single line drawn through that tree.

Has anybody else looked at this issue?

In the example above:

  • J71 is used in H71, I71 and D71
  • H71 is not used in any of the other expressions
  • I71 is not used in any of the other expressions
  • G71 is used in I71
  • D71 is used in E71, G71, I71 and H71
  • E71 is used in G71
  • B50 is used in J71, E71, I71 and H71

Drawing that as a tree there's no circle, but there are branches. In the drawing below, all the lines go up and none go down, so there's no circle. Yet I get a "circular reference" exception.

image

joevansteen commented

I am not using this repository, but am using the fork at [https://github.com/dotloop/Expr4j] which seem to have both of the issues identified here.

With respect to this issue, it appears to me the issue is NOT a function of your graph, but rather it is a function of the order in which the dependencies are created. The exception is thrown when an edge is added to the graph. If I build your graph in order, I have no problem. If I extend your graph by adding a new node dependent on I71, I have no problem. If I add a new node, A7, and then change B50 to depend on A7 I then generate the GraphCycleException.

The "check for cycles" function starts with the modified (new) edge and traces outbound, depended paths. However, when an outbound node has multiple outbound paths it has to process that node more than one time. The problem is that the algorithm assumes the node should only appear once. When it appears a second time for processing (has already been looked at) it declares an exception rather than processing the other (remaining) outbound path(s).