RE: graph traversal

["Justin Ludwig" <justinl at datachannel dot com>]

>How can I traverse a graph with XSL?
...
>I can do a tree traversal with the document() function, for
example this
>stylesheet:
...
>gives me "6 2 1 3 1", but what I really want is "6 2 1 3".
>(Actually what I really want is "6 2 3 1", but that may be
harder.)

	I don't think you can get the output you actually really
want. You might get closer by adding another level of
recursion to traverse the tree to depth n, outputting only
the nodes at that depth. That would give you 6 2 3 1 1; a
result still less than ideal.

>Normally one marks the nodes of a graph when they're
visited,
>and then skips the marked nodes if they're seen again.
>Can that be done in XSL?

	You can't 'mark' nodes exactly. With a classic tree
traversal in XSLT, you could keep track of the nodes you've
visited on the direct path between the current node and the
root. But since XSLT doesn't allow templates to return
values, you won't be able to remember any of the nodes
you've visited that have branched off from that path. (Or,
important to this specific question, if any of those nodes
happen to be the same as the current node).

	The only way I see a graph traversal possible in XSLT that
can keep track of the nodes it has already tried is if the
graph is bi-directional. When you'd hit a leaf (or a node
already in your list), you could continue back up (as
opposed to recursively returning back up) to try the
siblings of that node.

	I hope someone else has a better answer; it's a really good
question: How powerful is this XSLT?

	Justin


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list