[
Lists Home |
Date Index |
Thread Index
]
You'll probably find that the "dynamic templates" technique used by
Dimitre Novatchev (search for FXSL) is ideally suited to this kind of
problem.
I have solved similar problems such as looking for circular definitions
of attribute sets in a stylesheet. It can be done directly using
recursive templates, but dynamic templates make it much easier.
Stylesheet functions as provided by XSLT 2.0 also simplify the coding a
lot.
You'll probably get more response to this on xsl-list at
mulberrytech.com
Michael Kay
> -----Original Message-----
> From: Ramon M. Felciano Yahoo [mailto:felciano@yahoo.com]
> Sent: 11 January 2004 22:45
> To: xml-dev@lists.xml.org
> Subject: [xml-dev] Using XSLT and XPath for graph data
> structure processing?
>
>
> 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?
>
> Thanks!
>
> Ramon
>
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org
> <http://www.xml.org>, an initiative of OASIS
<http://www.oasis-open.org>
The list archives are at http://lists.xml.org/archives/xml-dev/
To subscribe or unsubscribe from this list use the subscription
manager: <http://lists.xml.org/ob/adm.pl>
|
