Cart
|
[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: The XSLT Solution for the General Graph Path Problem(Was:R
Dimitre Novatchev wrote:
>felciano@y... (Ramon M. Felciano) wrote in message
>news:<b3cf7422.0401111241.20293d7a@p...>...
>
>
>>Helo all --
>>
>>I'm trying to gain a deeper understand for what type of
>>semi-declarative programming can be done through XML and XPath/XSLT.
>>I'm looking at graph processing problems as a testbed for this, and
>>came across a problem that I haven't been able to solve elegantly. The
>>problem is to find "linker" vertexes that a pair of verteces from a
>>pre-defined set. For example, if the graph verteces represent cities
>>and edges represent flights between them, then given a list of cities,
>>find all intermediate cities that you would stop in via a "connecting
>>flight".
>>
>>For example, given the following simple graph:
>>
>>V1 -> V2 -> V3 -> V4
>> \<- V5 ->/
>>
>>(V5 points to both V2 and V4), and its XML serialization:
>>
>><graph>
>> <vertex id="V1"/>
>> <vertex id="V2" type="anchor"/>
>> <vertex id="V3"/>
>> <vertex id="V4" type="anchor"/>
>> <vertex id="V5"/>
>> <edge source="V1" target="V2"/>
>> <edge source="V2" target="V3"/>
>> <edge source="V3" target="V4"/>
>> <edge source="V5" target="V2"/>
>> <edge source="V5" target="V4"/>
>></graph>
>>
>>I would like to transform this into a second graph where all vertexes
>>that "link" two anchor distinct vertexes are flagged as link nodes. In
>>this case, there are two anchor vertexes V2 and V4, and I can link
>>them through V3 (V2 -> V3 -> V4) and V5 (V2 <- V5 -> V4). Note that
>>linked verteces must be distinct, so traversing the V2 <- V1 -> V2
>>path should not yield V1 as a link node. So I'd like to see something
>>like this:
>>
>><graph>
>> <vertex id="V1"/>
>> <vertex id="V2" type="anchor"/>
>> <vertex id="V3" linker="true"/>
>> <vertex id="V4" type="anchor"/>
>> <vertex id="V5" linker="true"/>
>> <edge source="V1" target="V2"/>
>> <edge source="V2" target="V3"/>
>> <edge source="V3" target="V4"/>
>> <edge source="V5" target="V2"/>
>> <edge source="V5" target="V4"/>
>></graph>
>>
>>It would be ideal to come up with a generalized solution that would
>>let you use 1, 2, .. N intermediate linking nodes. I've been able to
>>get this working with nested loops, but it isn't particularly
>>declarative or speedy, and is certainly more verbose than I'd like, so
>>I'm wondering if anyone here has insights into how to do this
>>elegantly and in XSLT/XPath style. For example, is it possible to
>>write a single XPath expression that will select <vertex> elements
>>that obey the above criteria? If not, does anyone have any suggestions
>>for how to code this effectively and efficiently with XSLT? Or is
>>XPath/XSLT not the right paradigm for this type of information
>>processing and transformation?
>>
>>Thanks!
>>
>>Ramon
>>
>>
>
>
>Ramon,
>
>Here's the general solution and it is quite simple and
>straightforward. I use a recursive template based on the following
>rule:
>
> Paths(/.., X, Z) = Union( {X -> Xi} . Paths(X, Xi, Z) )
>
>Where the function Paths(Eset, X, Z) returns all paths from X to Z,
>that do not include any vertices belonging to the exclusion-set Eset.
>
>Here {X -> Xi} are all arcs from X.
>
>Informally,
> {X -> Xi} . Paths(X, Xi, Z)
>
>is the Cartesian product of the arc {X -> Xi} with the set of paths Paths(X,
>Xi, Z), giving a new set of paths.
>
>As you can see the code of the transformation is 71 lines long, but it
>should be noted that for the purpose of readability I write some XPath
>expressions on several lines and also almost half of these 71 lines are just
>closing tags.
>
>Here's the code. This transformation:
>
><xsl:stylesheet version="1.0"
> xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
> xmlns:exsl="http://exslt.org/common"
> exclude-result-prefixes="exsl"
> >
> <xsl:output omit-xml-declaration="yes" indent="yes"/>
>
> <xsl:key name="kNeighbors" match="vertex"
> use="../edge[@target = current()/@id]/@source"/>
>
> <xsl:key name="kNeighbors" match="vertex"
> use="../edge[@source = current()/@id]/@target"/>
>
> <xsl:template match="/">
> <xsl:call-template name="getPaths">
> <xsl:with-param name="pNode1"
> select="/*/vertex[@type='anchor'][1]"/>
> <xsl:with-param name="pNode2"
> select="/*/vertex[@type='anchor'][2]"/>
> </xsl:call-template>
> </xsl:template>
>
> <xsl:template name="getPaths">
> <xsl:param name="pNode1" select="/.."/>
> <xsl:param name="pNode2" select="/.."/>
> <xsl:param name="pExcluded" select="/.."/>
>
> <xsl:for-each select=
> "key('kNeighbors', $pNode1/@id)
> [not(@id = $pExcluded/@id)]">
> <xsl:choose>
> <xsl:when test="@id = $pNode2/@id">
> <path>
> <xsl:copy-of
> select="/*/edge[$pNode1/@id = @*
> and
> $pNode2/@id = @*
> ]"/>
> </path>
> </xsl:when>
> <xsl:otherwise>
> <xsl:variable name="vrtfTail">
> <xsl:call-template name="getPaths">
> <xsl:with-param name="pNode1"
> select="."/>
> <xsl:with-param name="pNode2"
> select="$pNode2"/>
> <xsl:with-param name="pExcluded"
> select="$pExcluded | $pNode1"/>
> </xsl:call-template>
> </xsl:variable>
>
> <xsl:variable name="vTail"
> select="exsl:node-set($vrtfTail)/*"/>
>
> <xsl:if test="$vTail">
> <path>
> <xsl:copy-of
> select="/*/edge[$pNode1/@id = @*
> and
> current()/@id = @*
> ]"/>
>
> <xsl:copy-of select="$vTail/*"/>
> </path>
> </xsl:if>
> </xsl:otherwise>
> </xsl:choose>
> </xsl:for-each>
> </xsl:template>
></xsl:stylesheet>
>
>when applied on this source.xml:
>
><graph>
> <vertex id="V1"/>
> <vertex id="V2" type="anchor"/>
> <vertex id="V3"/>
> <vertex id="V4" type="anchor"/>
> <vertex id="V5"/>
> <edge source="V1" target="V2"/>
> <edge source="V1" target="V3"/>
> <edge source="V2" target="V3"/>
> <edge source="V3" target="V4"/>
> <edge source="V5" target="V2"/>
> <edge source="V5" target="V4"/>
></graph>
>
>produces thewanted result:
>
><path>
> <edge source="V1" target="V2"/>
> <edge source="V1" target="V3"/>
> <edge source="V3" target="V4"/>
></path>
><path>
> <edge source="V2" target="V3"/>
> <edge source="V3" target="V4"/>
></path>
><path>
> <edge source="V5" target="V2"/>
> <edge source="V5" target="V4"/>
></path>
>
>These are all three different paths (with all nodes in the path only
>once) from V2 to V4 in the graph described by the xml above.
>
>The first solution:
>
> V2 -> V1 -> V3 ->V4
>
>is 3 edges long.
>
>The other two are two edges long each (Note that I added to your original
>graph structure a new arc from V1 to V3 in order to make it more "general").
>
>
>I hope this helped in this specific problem and also to answer
>positively your questions about the expressiveness of XPath/XSLT and
>the appropriateness of XSLT as a tool for solving this type of
>problems.
>
>
>Dimitre Novatchev.
>FXSL developer
>
>http://fxsl.sourceforge.net/ -- the home of FXSL
>Resume: http://fxsl.sf.net/DNovatchev/Resume/Res.html
>
>
Very nice! So if you wanted to restrict this to operate over a finite
search space by limiting the maximum path length, you'd just add some
sort of extra "current-path-length" variable and fail when it maxes out?
Also, is there a way to accomplish the same thing but delivering the
output I listed? That is, rather than constructing a result document
based on a new (implicit) DTD that has <path> elements, is there a way
to do this by flagging nodes in the original document with @linker
attributes?
Thanks -- very cool demo regardless!
Ramon
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! 
Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|
|||||||||
