Re: avoiding recursion in a dump_table function

[David Favro <lua@...>]

This is a standard problem in graph theory, detecting/avoiding cycles.  The
typical solution, especially when the graph is a digraph or a tree, is to
maintain a stack of visited nodes, representing the path from the root to
the current node.  Since nested tables form a _directed_ graph, there could
be multiple paths to the same node without an actual cycle (causing
"infinite recursion").

All the solutions I've seen here, however, seem to be using a 'seen' table
which is passed into the lower recursion level, but from which the value is
not 'popped' when the recursed function returns.  This means that if there
are multiple paths to the same node, the second-visited path will be
incorrectly interpreted as infinite recursion, and some edges not printed.

E.g. (all nodes here are tables, but a more complex example is easy to pose).

[root-node]--------+
     |             |
     V             V
   [item1]<-----[item2]


Or put another way:

do
  local item1 = {};
  dump_table( { sub1 = item1, sub2 = {sub1=item1} } );
end


Since the prefix parameter is a string, it becomes a new reference when it
is modified and passed into the recursive call; but the seen table is passed
by reference, referring to the same table as the calling function, so it
remains modified when backtracking.  I think it more appropriate to add,
e.g. in Jo-Philipp Wich's function, "seen[t] = nil" just after the end of
the for loop.

Am I missing something?  Some upvalue magic that 'pops' nodes from the seen
table when the function returns?  Some reason why this would be considered
an undirected graph?

-- David