Thank you Michael and Dimitre!
(Dimitre: Just learned about FXSL the other day and eager to study it further.)
(Michael: Good to hear about the 4th edition. I am going to order it
today. The 3rd edition has been invaluable to me.)
Darcy
On Thu, May 1, 2008 at 1:54 AM, Dimitre Novatchev
<dnovatchev(_at_)gmail(_dot_)com> wrote:
For an XSLT 1.0 solution see also:
http://lists.xml.org/archives/xml-dev/200401/msg00444.html
My recent blog entry on implementing a generic closure() function in
FXSL also has an example with the "reachable" relation on the set of
nodes of a graph:
http://dnovatchev.spaces.live.com/Blog/cns!44B0A32C2CCF7488!384.entry
--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
On Wed, Apr 30, 2008 at 6:17 PM, Michael Kay <mike(_at_)saxonica(_dot_)com>
wrote:
> >
> > I think I found a bug in some example code from XSLT 2.0
> > Programmer's Reference by Michael Kay and would like to
> > review it with Michael and/or other XSLT programmers.
>
> You are right, this code published in the 3rd edition is embarrassingly
> wrong. There's a corrected version in the 4th edition, which I believe is
> now shipping. Sorry about the inconvenience.
>
> The corrected algorithm passes an extra parameter on each recursive call,
> which is the list of nodes marking the route from the starting node to the
> node currently being visited. If the nto currently being visited contains a
> reference to any of the nodes in this list, there is a cycle in the data,
> which can be reported.in
>
> Most of the textbook algorithms for detecting cycles in graphs are written
> in a procedural way, and the error arose because I tried to rethink the
> problem in functional terms (and failed to get it right).
>
> Michael Kay
> http://www.saxonica.com/
>
>
> >
> > p.199 Checking for Cycles in a Graph:
> >
> > <xsl:function name="graph:refers" as="xs:boolean">
> > <xsl:param name="links" as="node()"/>
> > <!-- $links is a node that represents the template to be called -->
> > <xsl:param name="A" as="node()"/>
> > <xsl:param name="B" as="node()"/>
> >
> > <!-- find the directly-connected nodes -->
> > <xsl:variable name="direct" as="node()*">
> > <xsl:apply-templates select="$links">
> > <xsl:with-param name="from" select="$A"/>
> > </xsl:apply-templates>
> > </xsl:variable>
> >
> > <!-- return true if B is directly or indirectly connected
> > from A -->
> > <xsl:sequence select="if (exists($direct intersect $B)) then true()
> > else if (some $C in $direct
> > satisfies graph:refers($links, $C,
> > $B)) then true()
> > else false()"/> </xsl:function>
> >
> > I have defined a template for $links as required. (But it is
> > not necessary to see the bug because I think the bug is in
> > the higher order function noted above.)
> >
> > Typically cycles are checked for by evaluating:
> > graph:refers($something, $something). If there is connection
> > through $something's direct links and their direct links and
> > so on, then there is a cycle.
> >
> > The problem is that "graph:refers" may enter an infinite loop
> > if $direct contains a cycle. Consider the case where $A does
> > not refer to $B but one of $A's direct links contain a cycle.
> > In the XPath for xsl:sequence, the function recursively
> > calls itself with "graph:refers($links, $C, $B)". $C becomes
> > $A in the next iteration, and its direct links are found in
> > order to test if one of them refers back to $B. But notice
> > that there is no check if $C contains a cycle!
> > So it is possible that $C's direct links could be navigated
> > forever....without reaching $B first. (I am actually
> > experiencing this problem with a large data set and haven't
> > had time to make a simpler use-case. But I am hoping that
> > people can follow the problem generically with the thought
> > exercise I just described.)
> >
> > So it seems like $C the algorithm should check if $C contains
> > a cycle before testing "graph:refers($links,$C,$B)"... but
> > after some thinking, I am realizing that just because $C
> > contains a cycle, doesn't mean that $A doesn't refers to $B.
> > Perhaps the solution is to test if $C contains a cycle, and
> > if it does, remove the cycle(s) -> creating $D. And then
> > test "graph:refers(l$inks,$D,$B)".
> >
> > This seems complicated though... and I thought I should
> > discuss this issue with others before I continue to hack at
> > this algorithm. It seems like this type of algorithm/problem
> > would be well-known for graphs?
> >
> > Has anyone explored this problem? Any suggestions?
> >
> > Thanks
> > Darcy
> >
> > --~------------------------------------------------------------------
> > XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
> > To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
> > or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
> > --~--
> >
>
>
> --~------------------------------------------------------------------
> XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
> To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
> or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
> --~--
>
>
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--