Using XSLT and XPath for graph data structure processing?

Discussion in 'XML' started by Ramon M. Felciano, Jan 11, 2004.

  1. 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
     
    Ramon M. Felciano, Jan 11, 2004
    #1
    1. Advertising

  2. (Ramon M. Felciano) wrote in message news:<>...
    > 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
     
    Dimitre Novatchev, Jan 12, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ramon M. Felciano
    Replies:
    6
    Views:
    403
    Ed Beroset
    Jan 15, 2004
  2. Dr Ann Huxtable

    Missing Graph.h and (Graph.lib) woes - any help

    Dr Ann Huxtable, Dec 21, 2004, in forum: C Programming
    Replies:
    6
    Views:
    656
    Dr Ann Huxtable
    Dec 21, 2004
  3. Almoni
    Replies:
    0
    Views:
    3,106
    Almoni
    Jan 17, 2010
  4. Emilio Mayorga
    Replies:
    6
    Views:
    344
    Martien Verbruggen
    Oct 8, 2003
  5. IRR
    Replies:
    2
    Views:
    411
Loading...

Share This Page