Checking for Cycles in a Graph
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
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format