Re: [xsl] Finding paths in Visio XML exports - recursion question

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

Seems like a typical graph structure.

In 2004 I produced an  XSLT 1.0 solution to finding  all paths between
two given nodes (and can be used naturally for graph traversal):

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

Hope this will be helpful.


-- 
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 Sat, Sep 27, 2008 at 12:20 PM, Steven Davies <xsl-list@xxxxxxxxxxx> wrote:
> Hi everyone,
>
> while I'm not a total XSLT newbie I'm having trouble getting my head
> round a couple of things when trying to find paths through Visio
> flowcharts which have been exported in Visio's XML format.
>
> Very basically, for anyone who is unaware of Visio's schema I shall try
> to describe it below with a very simplified example:
>
> <Pages>
>  <Page ID="1">
>  <Shapes>
>   <Shape ID="1" NameU="CustomShape.112">
>    <Shape-specific-data />
>   </Shape>
>   <Shape ID="2" NameU="CustomShape.8">
>    <Shape-specific-data />
>   </Shape>
>   <Shape ID="3" NameU="CustomShape.32">
>    <Shape-specific-data />
>   </Shape>
>  </Shapes>
>  <Connects>
>   <Connect FromSheet="1" FromCell="BeginX" ToSheet="1" />
>   <Connect FromSheet="1" FromCell="EndX" ToSheet="2" />
>   <Connect FromSheet="2" FromCell="BeginX" ToSheet="2" />
>   <Connect FromSheet="2" FromCell="EndX" ToSheet="3" />
>  </Connects>
>  </Page>
> </Pages>
>
> Obviously there are many more <Shape>s and <Connect>s in the document!
> The <Connect>s map from a <Shape> whose ID is the same as @ToSheet and
> @FromCell="BeginX" to a <Shape> whose ID is the same as @ToSheet and
> @FromCell="EndX".
>
> Now, I can use an XPath expression to find the first node in the
> document easily enough (it has a certain property in its data set to
> "1") and the only way I've been able to find all connected shapes from
> this one is to use 3 for-each loops: the first over all <Connect>s
> beginning at the shape itself, the second nested loop over all other
> endpoints of the <Connect> (there will only ever be one) and the third
> over all <Shape>s connected to the <Connect>:
>
>  <xsl:variable name="thisShapeID" select="./@ID"/>
>  <xsl:for-each select="../../v:Connects/v:Connect[@ToSheet=$thisShapeID
> and @FromCell='BeginX']">
>   <xsl:variable name="connectFromSheet" select="./@FromSheet"/>
>   <xsl:for-each select="../v:Connect[@FromSheet=$connectFromSheet and
> @FromCell='EndX']">
>     <xsl:variable name="nextShapeID" select="./@ToSheet"/>
>     <xsl:for-each select="../../v:Shapes/v:Shape[@ID=$nextShapeID]">
>
> I had to use the xsl:variables because I couldn't get the equation
> [@ID=./@ToSheet], for example, to work (it never matched, any ideas with
> this?).
>
> Inside the innermost xsl:for-each I recursively call the template which
> works very well for a straight flow in Visio. However, there can be
> infinite loops in the flow so I have to first test whether the <Shape>
> has already been output before recursing. This works.
>
> Also the flows can branch off in multiple directions and each branch
> needs to be output one at a time (i.e. the nodes before the branch only
> need to be output once). This also works.
>
> My problem is that I need to output a message (well, an element - eventually
> this will be XSL-FO) every time the end of a path is reached. This could be
> because the flow looped back, that is, the recursion is stopped, or it could
> be because the end of a branch (and therefore outermost for-each) was
> reached. While this is relatively easy to do, I end up getting multiple
> copies of the node output because of the multiple levels of recursion.
>
> Does anyone have an idea how to get around this?
>
> If you have any questions about this please let me know - I'm thinking about
> this on a more conceptual level than practical level as I'd like to get my
> head around it rather than just trying things blindly! Unfortunately I can't
> provide the flowchart as it's confidential but I can make a mock-up in the
> Gimp if anyone thinks it would help.
>
> Many thanks if you got this far ;-)
> Steve