Re: Re: Checking for Cycles in a Graph

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@xxxxxxxxxxxx> 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