On Sat, Jul 4, 2009 at 10:00 PM, Edward K. Ream <[email protected]> wrote:
> The "one node" world would, in fact, be equivalent, from a data point > of view, to a general graph world. In particular, traversing the tree > becomes a bit tricky because *exactly* the same node can appear > arbitrarily many times in a traversal. > > To handle this, a "generational" marking algorithm would be natural. > For example, to mark all nodes reachable from a given node, we > increment a generation count N, and "mark" a node v by setting v.mark > = N. We can test whether a node v is marked by testing whether N > > v.mark. We can also maintain that information outside the nodes, e.g. maintain a dict that maps gnx's to reference counts (or a list of parents, perhaps?). This table would be per-controller, and it would have valid data at all times. It can be used to identify cloned nodes (those have refcount >1, or len(parentlist) > 1. -- Ville M. Vainio http://tinyurl.com/vainio --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "leo-editor" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/leo-editor?hl=en -~----------~----~----~----~------~----~------~--~---
