[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

RE: Using XSLT and XPath for graph data structure processing?

• To: <felciano@y...>,<xml-dev@l...>
• Subject: RE: Using XSLT and XPath for graph data structure processing?
• From: "Michael Kay" <michael.h.kay@n...>
• Date: Mon, 12 Jan 2004 00:19:37 -0000
• Importance: Normal
• In-reply-to: <4001D1FE.60005@y...>
• Reply-to: <michael.h.kay@n...>

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>

• References:
  • Using XSLT and XPath for graph data structure processing?
    • From: "Ramon M. Felciano Yahoo" <felciano@y...>

• Prev by Date: Re: Using XSLT and XPath for graph data structure processing?
• Next by Date: RE: Urgent help needed. XML Parser
• Previous by thread: Re: Using XSLT and XPath for graph data structure processing?
• Next by thread: The XSLT Solution for the General Graph Path Problem(Was:Re: Using XSLT and XPath for graph data structure processing?)
• Index(es):
  • Date
  • Thread