On Sun, Apr 13, 2008 at 10:07 AM, Terry Brown <[EMAIL PROTECTED]> wrote:
> > Recall that a key part in my rejection of the graph world > > was a realization that iterators in any graph world are much more > > complex than Leo's iterators. > > True, but now you're on the slippery slope :-) True. One could imagine a different front end to the data. This is Brian's "sea of nodes", as far as I can tell. > It seems to me that hard part with the new node system will be not > implementing "general graph world" accidentally. I.e. it's up to the > interface to stop the user linking a node in a way that creates a > cycle, and the interface has to do that to avoid the more complicated > iterators (for now, at least :-) Exactly. I could not have stated it better. I avoided this discussion in the interest of brevity, but you have hit the nail on the head. > > P.S. As a matter of symmetry, a unified node could contain a list of > > the node's parents. This is not necessary: it is analogous to > double-linking a linked list. > > Unnecessary, but a big speed boost (at the cost of memory) if you > wanted to access the list of a nodes parents. I don't think so. In my present thinking it will not be possible to possible to access a *node's* parents--you can only access the parents of a node *at a particular position*. Positions give you parents instantly. BTW, in the unified node world I shall eliminate the unfortunate optimization in positions that added a node to the stack only if a node had two parents. The position stack will contain the full list of direct parents of a node *at a position*. > Seems to me that the concept of "parent" only exists as a side effect > of the position. Not exactly. n2 is a parent of n1 if and only if n1 is in n2.children. But the iterators are the way of getting at this information, in most cases. The read code will be an exception: it will populate the children arrays with "real" nodes, given info from the sax parser. The *present* read code does this with the createSaxVnodes and its helpers; I hope to simplify this code considerably. Indeed, I don't believe there is any need to keep track explicitly about whether a node is "shared" or not. Just creating the children array for each node will suffice (I think). Amazing. > What if a node simply had a list L of all nodes to which it connects, > and functions that return a list of children or iterate children simply > omit any members of L that point to p.parent? The children list of a node is the list of nodes to which the node points. At present, I seen no reason for a parents array, mostly because such data is not nearly as useful as the stack of direct ancestors that will be in all positions. Positions really are a basic part of this whole scheme. :-) > So for DAG world, iterating children requires a position? For *any* world. It's amazing how simple everything is: nodes simply have a children array: there are no other links in *nodes*. Positions give you the context in what is an amazingly natural way. > Nah, I guess it's not quite that simple, it doesn't account for loops > back to the parent through an intermediate node. But of course that's > not a concern if you know the interface doesn't allow creation of such > loops. No, it is that simple. In a graph world iterators define paths. Everything just works. > I think this is a great path your heading down - get all the current > DAG machinery working on top of the new structure, which sounds doable, > then there'll be some solid ground from which to explore the > possibilities for cyclic graphs. Imo, there is very little left to explore with regard to the implementation. The old "theory of relativity" applies: any node can be the start of a traversal. But yes, this is an amazing "collapse" of complexity". This kind of fundamental simplification will lead to undreamed of applications. > Bearing in mind that this is all future stuff not to be played with > before the DAG stuff is done, a node could have two lists; a list of > parents and a list of children, or a single list of tuples (o, d) where o > is anOther node to which the current node connects and d is the direction of > the connection. These two approaches are equivalent and the two list option > might be more convenient, anyway they're > equivalent so it doesn't matter much. True, but I believe the combination of nodes and iterators will render these secondary kinds of data structures unnecessary. This is very exciting because it makes the implementation dead simple. > Then iterators could have three flags, 'unique' as you discussed, > 'directed' meaning pay attention to direction (don't follow links to > "parents"), and 'cyclic' meaning don't shield me from cycles in the > data (the default being to shield the caller from cycles by maintaining > a list of visited nodes). Not sure how unique and cyclic interact, > unique makes sense is a DAG+clones context, where cyclic doesn't apply. Yes, there are all kinds of inventions possible, and iterators, not nodes, are where the real choices will happen. File formats also will be a source of future invention. > Again, none of that matters until the DAG stuff is done. It matters right now: the issues you raise are the reason why this Aha is so spectacular. Edward --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "leo-editor" group. To post to this group, send email to leo-editor@googlegroups.com 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 -~----------~----~----~----~------~----~------~--~---
