On Wed, Mar 26, 2003 at 05:40:56PM +0100, Robin Berjon wrote: > Dan Sugalski wrote: > >At 4:47 PM +0100 3/26/03, Robin Berjon wrote: > >>Fast and efficient graphs of all sorts would be very useful. A way to > >>define a complex graph of interlinked arbitrary objects while being > >>reasonable on memory and good with GC would be a definitive big win, > >>especially if it can be lazy. Especially with nice ways to write > >>visitors and easy searches in the graph based on object properties > >>(but I could be asking for too much ;). > > > >Probably a bit much, yep. :) I'd be happy with simple graph > >representation, annotation, and traversal. And for my purposes a DAG is > >sufficient. Loops are terribly annoying to have to deal with. > > Efficient annotation and traversal would go a long way, but almost all > useful XML representations have loops unfortunately. > > >>DAGs wouldn't enough though, most XML tree representations aren't > >>really trees, they're very cyclic. Some automata can treat a stream of > >>events as a B-Tree being visited, but those are rather rare currently. > > > >I was under the impression XML was very much a tree, and didn't do > >loops. Am I missing something here? (I don't, in general, do XML)
By loop you mean attributes declared by DTD as IDREFs and pointing to element having the same value for the attribut ID? Like in the example pasted from "XML in a nutshell"? <project project_id="p1"> <goal>Develop Strategic Plan</goal> <team_member person="ss078-05-1120"/> <team_member person="ss987-65-4320"/> </project> <project project_id="p2"> <goal>Deploy Linux</goal> <team_member person="ss078-05-1120"/> <team_member person="ss9876-12-3456"/> </project> <employee social_security_label="ss078-05-1120"> <name>Fred Smith</name> <assignment project_id="p1"/> <assignment project_id="p2"/> </employee> <employee social_security_label="ss987-65-4320"> <name>Jill Jones</name> <assignment project_id="p1"/> </employee> <employee social_security_label="ss9876-12-3456"> <name>Sydney Lee</name> <assignment project_id="p2"/> </employee> In a way IDREF are similar to symlinks? they cannot create "real loops" because they are not followed by default by traversal tool juste like find does not follow symlinks by default. -- stef > > Your impression isn't wrong, it's just that in actual use one needs more > information. If you lose the cycles then you could as well just be working > on stream of parse events (which is typical in SAX), in which case an > in-memory representation is probably not useful. And that's just for basic > stuff, if you want to usefully represent ID/IDREFs, QName linking, internal > XLinks, etc you're basically pointing from random nodes to other random > nodes. > > Given what you describe plus loops we could take over and do Really Cool > Stuff :) > > -- > Robin Berjon <[EMAIL PROTECTED]> > Research Engineer, Expway http://expway.fr/ > 7FC0 6F5F D864 EFB8 08CE 8E74 58E6 D5DB 4889 2488 >
