XML Editor
Sign up for a WebBoard account Sign Up Keyword Search Search More Options... Options
search
Chat Rooms Chat Help Help News News Log in to WebBoard Log in Not Logged in
Home » Boards » Stylus Studio Developer Network » XSLT Help and Discussion » Graph Traversal (Keep track of visited Path)
Conferences Close Tree View
+ Stylus Studio Feature Requests (1192)
+ Stylus Studio Technical Forum (14621)
+ Website Feedback (249)
- XSLT Help and Discussion (7625)
-> - XSL-fo and how to line feed th... (1)
-> + Houston we have a problem (2)
-> + XSL-FO PDF generation (2)
-> + StylusStudio - pick XSLT 1.0 b... (6)
-> - Stylus Studio 2010 debugging f... (1)
-> - Drop down menu List / Option M... (1)
-> - XML transformation using Java ... (1)
-> + i can't to find XSLT editor in... (2)
-> - Copy xml input as value of an ... (1)
-> - Remove Name space from the Tab... (1)
-> - CGI formatted URL with name/va... (1)
-> - Problem with counting (1)
-> + for-each loop is only returnin... (3)
-> - sort date but some dates may b... (1)
-> - Entity Conversion (1)
-> - How can I build an xml convert... (1)
-> + Little Help (2)
-> + how do I merge nodes to one sc... (2)
-> - beginner help xslt and xpath (1)
-> - Convert XML Feed to CSV/SQL/XL... (1)
-> - Working with text node. (1)
-> - No Topic (1)
-> - API for XSLT Converter for .NE... (1)
-> - Getting started (1)
-> + saxon sql extensions - mysql a... (2)
-> - How do I copy and create new e... (1)
-> + substring-before and sums (3)
-> + Parsing special characters in ... (2)
-> + Schema - Require attribute in ... (2)
-> - Edit existing XSL files when n... (1)
-> + How can I use one single XSLT ... (2)
-> - Default selection of value in ... (1)
-> - Problem with watermark in pdf ... (1)
-> + XSLT Parameter Values dialog n... (3)
-> + Value of File Name is not acce... (10)
-> - Need help with a complex table... (1)
-> - How to replace all nordic char... (1)
-> - XSLT java heap space error wit... (1)
-> - Table Overflow to next page (1)
-> - Using XSLT 2.0 to define custo... (1)
-> - "standalone" attribute and xs... (1)
-> + Standardizing IP addresses (2)
-> + Programmatically changing page... (6)
-> + Can Stylus generate XSLT if so... (5)
-> + Extraction based on NODE Name. (2)
-> + NO XSLT:WYSIWYG (2)
-> + determine condition at run tim... (2)
-> - How to reduce top margin in ev... (1)
-> + need help on xsl looping (4)
-> - Convert Symbol to Element (1)
-> + Separator -only- between field... (3)
-> + DocBook (9)
-> + First Occurance of Alphabet (2)
-> + XSL:Key and Document (2)
-> + Excel Macro using XSLT (2)
-> + Add missing element and attrib... (2)
-> + XSL: Stop Count at First Match (2)
-> + XSD to EDI (4)
-> + How to access data from nested... (2)
-> + Simple division of XML file (2)
-> - XML to Flat File (1)
-> + Dispalying data whith xsl:for ... (3)
-> - distinct nodes - into 3 column... (1)
-> + Newbie at XML (2)
-> + XSL Not Working (3)
-> + to draw table using xsl (2)
-> + Base64 decoder (5)
-> + How to create a hidden sheet u... (3)
-> + XML Reports (2)
-> + Copying image files from one d... (2)
-> + XML conversion to RSS (2)
-> + Inserting Image (2)
-> + Xml to Pdf using Xsl (2)
-> + Using a parameter (or similar)... (2)
-> + How to avoid creating empty xm... (2)
-> + how to read txt files in xml (2)
-> + Limit records to 4 per page. P... (4)
-> + XSLT Mapping Based on JDK5 (2)
-> + XML Mappin (2)
-> + Format Datetime with xslt (3)
-> + Cell border missing (2)
-> + XSL: Key (not matches) (5)
-> + Loop through each char in stri... (2)
-> + What is the best way to sum va... (3)
-> + xslt sort help (2)
-> + getting the count (2)
-> + XSL dynamic variables (5)
-> + XSL:Key use (3)
-> + Help With Updating Attributes ... (8)
-> + GETTING COUNT AND POSITION usi... (3)
-> - Hi Everyone !! (1)
-> - Graph Traversal (Keep track of... (2)
-> ->Graph Traversal (Keep tra...
-> + XSL IF with sum (2)
-> + Param not incrementing (2)
-> + Iterating through value tags (3)
-> + URGENT :::: Remove the name sp... (2)
-> + Pass new param values to ASP O... (2)
-> + Detect Browser Version in XSL (2)
-> + xslt result-document (2)
-> + Unique nodes based on two attr... (3)
-- Previous [181-200] [201-220] [221-240] Next
+ XQuery Help and Discussion (2017)
+ Stylus Studio FAQs (159)
+ Stylus Studio Code Samples & Utilities (364)
+ Stylus Studio Announcements (113)
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.
   
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.