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

Using XSLT and XPath for graph data structure processing?

• To: xml-dev@l...
• Subject: Using XSLT and XPath for graph data structure processing?
• From: "Ramon M. Felciano Yahoo" <felciano@y...>
• Date: Sun, 11 Jan 2004 12:45:18 -1000
• Organization: Yahoo Organization
• Reply-to: felciano@y...
• User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.6b) Gecko/20031205 Thunderbird/0.4

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

• Follow-Ups:
  • The XSLT Solution for the General Graph Path Problem(Was:Re: Using XSLT and XPath for graph data structure processing?)
    • From: "Dimitre Novatchev" <dnovatchev@y...>
  • RE: Using XSLT and XPath for graph data structure processing?
    • From: "Michael Kay" <michael.h.kay@n...>
  • Re: Using XSLT and XPath for graph data structure processing?
    • From: Sjoerd Visscher <sjoerd@w...>

• Prev by Date: Re: Non-Borg servers can authenticate Borg clients (Was Re: Re: Cookies at XML Europe 2004 -- Call for Participation)
• Next by Date: Re: Using XSLT and XPath for graph data structure processing?
• Previous by thread: JSR 206 Java(TM) API for XML Processing (JAXP) 1.3
• Next by thread: Re: Using XSLT and XPath for graph data structure processing?
• Index(es):
  • Date
  • Thread