Re: Keep track of visited path

> I am trying to navigate through a graph by going through every path between
elements.
> I face the problem of not being able to accumulate the visited paths(links
between elements). The graph contain cycles, to avoid infinite loops (and
stack overflow) i need to keep track of the visited path.


Has been done five years ago and is not difficult to do in XSLT 1.0,
See for example:

     http://lists.xml.org/archives/xml-dev/200401/msg00444.html


--
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
-------------------------------------
I enjoy the massacre of ads. This sentence will slaughter ads without
a messy bloodbath.




On Wed, Aug 12, 2009 at 8:21 AM, MMM FINE<mm1fine@xxxxxxxxx> wrote:
>
> Hello Everybody,
> I am trying to navigate through a graph by going through every path between
elements.
> I face the problem of not being able to accumulate the visited paths(links
between elements). The graph contain cycles, to avoid infinite loops (and
stack overflow) i need to keep track of the visited path.
>
>
> I am using Altova XML Spy 2009 sp1, and XSLT 2.0
>
>
> Any help is appreciated,
>
>
> Waiting your responses :)
>
>
>
>
> Simplified version of the source file:
>
>
> <element id="abc-001" name="A">
> <links>
> <link id="link-001" start="abc-001" end="abc-002"/> <!--out link-->
> </links>
> </element>
> <element id="abc-002" name="B">
> <links>
> <link id="link-001" start="abc-001" end="abc-002"/><!--in link-->
> <link id="link-002" start="abc-002" end="abc-003"/><!--out link-->
> </links>
> </element>
> <element id="abc-003" name="C">
> <links>
> <link id="link-002" start="abc-002" end="abc-003"/><!--in link-->
> <link id="link-003" start="abc-003" end="abc-004"/><!--out link-->
> <link id="link-004" start="abc-003" end="abc-005"/><!--out link-->
> <link id="link-005" start="abc-003" end="abc-006"/><!--out link-->
> </links>
> </element>
> <element id="abc-004" name="D">
> <links>
> <link id="link-003" start="abc-003" end="abc-004"/><!--in link-->
> <link id="link-006" start="abc-004" end="abc-007"/><!--out link-->
> </links>
> </element>
> <element id="abc-005" name="E">
> <links>
> <link id="link-004" start="abc-003" end="abc-005"/><!--in link-->
> <link id="link-010" start="abc-005" end="abc-010"/><!--out link-->
> <link id="link-011" start="abc-005" end="abc-011"/><!--out link-->
> <link id="link-012" start="abc-005" end="abc-012"/><!--out link-->
> <link id="link-013" start="abc-005" end="abc-013"/><!--out link-->
> <link id="link-014" start="abc-005" end="abc-014"/><!--out link-->
> </links>
> </element>
> <element id="abc-006" name="F">
> <links>
> <link id="link-005" start="abc-003" end="abc-006"/><!--in link-->
> <link id="link-008" start="abc-006" end="abc-008"/><!--out link-->
> <link id="link-009" start="abc-006" end="abc-009"/><!--out link-->
> <link id="link-015" start="abc-006" end="abc-010"/><!--out link-->
> <link id="link-016" start="abc-006" end="abc-011"/><!--out link-->
> </links>
> </element>
> <element id="abc-007" name="G">
> <links>
> <link id="link-006" start="abc-004" end="abc-007"/><!--in link-->
> </links>
> </element>
>
>
>
>
>
>
>
>
> The desired output :
> Starting with A :
> link-001 b
> link-001 link-002 b
> link-001 link-002 link-003 link-004 link-005 b
> link-001 link-002 link-003 link-004 link-005 link-006 b
> link-001 link-002 link-003 link-004 link-005 link-006 link-007b
> link-001 link-002 link-003 link-004 link-005 link-006 link-007 link-010
link-011 link-012 link-013 link-014 b
> link-001 link-002 link-003 link-004 link-005 link-006 link-007 link-010
link-011 link-012 link-013 link-014 link-008 link-009 link-015 link-016
>
>
>
>
> Current XSLT Stylesheet:
>
>
> <xsl:template name="followLink">
> <xsl:param name="sortedLinks" as="node()+"/>
> <xsl:param name="oldLinks" as="xs:string" select="''"/>
>
> <xsl:variable name="visitedLinks" select="doc:visitedLinks($sortedLinks,
$oldLinks)"/>
> <xsl:for-each select="$sortedLinks">
> <!--elementNode contains the current element-->
> <xsl:variable name="elementNode" select="key('elemKey',./@end)"/>
> <xsl:choose>
> <xsl:when test="count( $elementNode/links/link[(@start = ../../@id) and
(@start != @end) ] ) > 0">
> <xsl:choose>
> <!--number of outlinks and not self referenced = 1 -->
> <xsl:when test="count( $elementNode/links/link[(@start = ../../@xmi:idref)
and (@start != @end) ] ) = 1">
> <xsl:call-template name="followLink">
> <xsl:with-param name="sortedLinks" select="$elementNode/links/link[@start =
../../@id]"/>
> <xsl:with-param name="oldLinks" select="$visitedLinks"/>
> </xsl:call-template>
> </xsl:when>
> <!-- number of outlinks and not self referenced > 1 -->
> <xsl:otherwise>
> <!--Sort links according to some criteria-->
> <xsl:call-template name="followLink">
> <xsl:with-param name="sortedLinks" select="$sortedLinks"/>
> <xsl:with-param name="oldLinks" select="$visitedLinks"/>
> </xsl:call-template>
> </xsl:otherwise>
> </xsl:choose>
> </xsl:when>
> <xsl:otherwise/>
> </xsl:choose>
> </xsl:for-each>
> </xsl:template>
>
>
> <xsl:function name="doc:visitedLinks" as="xs:string*">
> <xsl:param name="sortedLinks" as="node()+"/>
> <xsl:param name="oldLinks" as="xs:string+"/>
>
> <xsl:variable name="visitedLinks" as="xs:string+">
> <xsl:for-each select="$sortedLinks">
> <xsl:sequence select="concat($delimiter, ./@id, $delimiter)"/>
> </xsl:for-each>
> </xsl:variable>
> <xsl:sequence select="string-join(($oldLinks, $visitedLinks), ' ')"/>
> </xsl:function>
>
>
> The current output is like this:
> If i output the visited links at each iteration i get this:
>
>
> link-001 b
>
> link-001 link-002 b
>
> link-001 link-002 link-003 link-004 link-005 b
>
> link-001 link-002 link-003 link-004 link-005 link-006 b
>
> link-001 link-002 link-003 link-004 link-005 link-006 link-007b
>
> link-001 link-002 link-003 link-004 link-005 link-010 link-011 link-012
link-013 link-014 b
>
> link-001 link-002 link-003 link-004 link-005 link-008 link-009 link-015
link-016
>
>
> How can i write the doc:visitedLinks functions so it can return the result
of for-each loop after each iteration?
>
>
> Many thanks in advance,
>
> Mike