XML Editor
Sign up for a WebBoard account Sign Up Keyword Search Search More Options... Options
Chat Rooms Chat Help Help News News Log in to WebBoard Log in Not Logged in
Show tree view Topic
Topic Page 1 2 3 4 5 6 7 8 9 Go to previous topicPrev TopicGo to next topicNext Topic
Postnext
Mike FineSubject: Graph Traversal (Keep track of visited Path)
Author: Mike Fine
Date: 12 Aug 2009 10:10 AM
Originally Posted: 12 Aug 2009 06:15 AM
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.

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 &#8594;
link-001 link-002 &#8594;
link-001 link-002 link-003 link-004 link-005 &#8594;
link-001 link-002 link-003 link-004 link-005 link-006 &#8594;
link-001 link-002 link-003 link-004 link-005 link-006 link-007&#8594;
link-001 link-002 link-003 link-004 link-005 link-006 link-007 link-010 link-011 link-012 link-013 link-014 &#8594;
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 &#8594;
link-001 link-002 &#8594;
link-001 link-002 link-003 link-004 link-005 &#8594;
link-001 link-002 link-003 link-004 link-005 link-006 &#8594;
link-001 link-002 link-003 link-004 link-005 link-006 link-007&#8594;
link-001 link-002 link-003 link-004 link-005 link-010 link-011 link-012 link-013 link-014 &#8594;
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 visited links after each iteration?

Many thanks in advance

Posttop
Tony LavinioSubject: Graph Traversal (Keep track of visited Path)
Author: Tony Lavinio
Date: 12 Aug 2009 10:31 AM
This is the sort of problem that would most likely best be handled
on the general-purpose XSL-LIST run by Mulberry Technologies. There
are many XSLT experts there who delight in this sort of problem.

 
Topic Page 1 2 3 4 5 6 7 8 9 Go to previous topicPrev TopicGo to next topicNext Topic
Download A Free Trial of Stylus Studio 6 XML Professional Edition Today! Powered by Stylus Studio, the world's leading XML IDE for XML, XSLT, XQuery, XML Schema, DTD, XPath, WSDL, XHTML, SQL/XML, and XML Mapping!  
go

Log In Options

Site Map | Privacy Policy | Terms of Use | Trademarks
Stylus Scoop XML Newsletter:
W3C Member
Stylus Studio® and DataDirect XQuery ™are from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2016 All Rights Reserved.