Hi,
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. I have searched the list, checked the
errata for the book and googled to see if other's have had a
conversation on this before... but it seems to be undiscussed to date.
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>
--~--