Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > XML > Using XSLT and XPath for graph data structure processing?

Reply
Thread Tools

Using XSLT and XPath for graph data structure processing?

 
 
Ramon M. Felciano
Guest
Posts: n/a
 
      01-11-2004
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
 
Reply With Quote
 
 
 
 
Dimitre Novatchev
Guest
Posts: n/a
 
      01-12-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) (Ramon M. Felciano) wrote in message news:<(E-Mail Removed). com>...
> 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.



Before starting to solve a problem, one should understand it well.

I don't understand what you're saying above. In particular, V5 is not
a connecting node, because there is no arc from V2 to V5, so no path
V2 -> V5 -> V4 exists.

So, I do not have understanding about the following:

1. Does direction matter -- would any path from V4 to V2 (as opposed
to a path from V2 to V4) also be a solution?

2. Should the graph be regarded as a directed one (e.g. V5 -> V4 is
different from V4 -> V5) or not?

Please, correct/explain.


Dimitre Novatchev.
FXSL developer, XML Insider,

http://fxsl.sourceforge.net/ -- the home of FXSL
Resume: http://fxsl.sf.net/DNovatchev/Resume/Res.html
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Using Boost Graph Library to create very large graph Almoni C++ 0 01-17-2010 05:13 AM
Missing Graph.h and (Graph.lib) woes - any help Dr Ann Huxtable C Programming 6 12-21-2004 11:15 AM
perl graph theory (using Graph::Directed) IRR Perl Misc 2 07-27-2004 03:08 AM
Using XSLT and XPath for graph data structure processing? Ramon M. Felciano XML 6 01-15-2004 12:43 AM
GD::Graph: "mixed" graph doesn't recognize "area" graph type Emilio Mayorga Perl Misc 6 10-08-2003 02:14 AM



Advertisments