Re: Re: Checking for Cycles in a Graph

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