johnyf
commented
9 years ago Adjusting the recursion limit is not a fail-proof solution, because a hard limit does exist. The general solution is to remove recursion. Nonetheless, another suggestion may allow to avoid this.
Though I am not familiar with the internals of the algorithm, a similar issue arises in flattening a syntax tree with more nested operators than the default recursion limit. Increasing the recursion limit is not a solution there, because an expression can have arbitrarily many operators. Clearly, an unbounded number of operators can't be handled (unless processing in a streaming fashion). Nonetheless, the bound can be increased significantly, compared to that imposed by the recursion limit.
The solution is to arrange the (associative) operators in a binary tree. The total number of operators is the same, but the recursion depth is their logarithm. So a the required recursion depth becomes logarithmic in the number of operators, as opposed to linear (which it was initially).
Sidenote: humans do not manually write expressions with more associative operators (e.g., conjunctions) than the recursion depth, but machines do. The expressions mentioned above are generated by a machine, so the number of conjunctions is unavoidable. At the same time, this also allows automatically generating them in a binary tree (using parentheses to prevent the parser from blindly applying the associativity of that operator, which would yield a linear tree).
As already noted, I am not familiar with the details of the layout algorithm, and whether its recursive calls can be arranged as a binary call tree, but it is a possibility that can avoid rewriting the whole algorithm in a non-recursive paradigm.
bdcht
well for the Linux platform its ok, but I've tested on OSX and an exception is raised at default depth (1000) without taking into account the setrecursionlimit call. This means that the SugiyamaLayout will fail during the recursive part of vertical alignment (__place_block step) whenever a "block" has more than 1000 aligned vertices. Fix: either remove recursion (painful) or catch exception, forget about further alignment, and continue.