Cart
[Home] [By Thread] [By Date] [Recent Entries]
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@y...] > Sent: 11 January 2004 22:45 > To: xml-dev@l... > Subject: 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>
|
