SSDN - Graph Traversal (Keep track of visited Path)

XML Editor

Sign Up

Search

Options

Chat

Help

News

Log in

Not Logged in

Topic

Topic Page 1 2 3 4 5 6 7 8 9

Mike Fine

Subject: 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"/> 
</links>
</element>
<element id="abc-002" name="B">
<links>
<link id="link-001" start="abc-001" end="abc-002"/>
<link id="link-002" start="abc-002" end="abc-003"/>
</links>
</element>
<element id="abc-003" name="C">
<links>
<link id="link-002" start="abc-002" end="abc-003"/>
<link id="link-003" start="abc-003" end="abc-004"/>
<link id="link-004" start="abc-003" end="abc-005"/>
<link id="link-005" start="abc-003" end="abc-006"/>
</links>
</element>
<element id="abc-004" name="D">
<links>
<link id="link-003" start="abc-003" end="abc-004"/>
<link id="link-006" start="abc-004" end="abc-007"/>
</links>
</element>
<element id="abc-005" name="E">
<links>
<link id="link-004" start="abc-003" end="abc-005"/>
<link id="link-010" start="abc-005" end="abc-010"/>
<link id="link-011" start="abc-005" end="abc-011"/>
<link id="link-012" start="abc-005" end="abc-012"/>
<link id="link-013" start="abc-005" end="abc-013"/>
<link id="link-014" start="abc-005" end="abc-014"/>
</links>
</element>
<element id="abc-006" name="F">
<links>
<link id="link-005" start="abc-003" end="abc-006"/>
<link id="link-008" start="abc-006" end="abc-008"/>
<link id="link-009" start="abc-006" end="abc-009"/>
<link id="link-015" start="abc-006" end="abc-010"/>
<link id="link-016" start="abc-006" end="abc-011"/>
</links>
</element>
<element id="abc-007" name="G">
<links>
<link id="link-006" start="abc-004" end="abc-007"/>
</links>
</element>

The desired output :
Starting with A :
link-001 →
link-001 link-002 →
link-001 link-002 link-003 link-004 link-005 →
link-001 link-002 link-003 link-004 link-005 link-006 →
link-001 link-002 link-003 link-004 link-005 link-006 link-007→
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-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">

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

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

<xsl:otherwise>

<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 →
link-001 link-002 →
link-001 link-002 link-003 link-004 link-005 →
link-001 link-002 link-003 link-004 link-005 link-006 →
link-001 link-002 link-003 link-004 link-005 link-006 link-007→
link-001 link-002 link-003 link-004 link-005 link-010 link-011 link-012 link-013 link-014 →
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

Tony Lavinio

Subject: 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

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 to Conference:

Log In Options Username: Password:

Site Map | Privacy Policy | Terms of Use | Trademarks

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.