[xsl] paths through DAGs

Subject: [xsl] paths through DAGs
From: Saverio Perugini <sperugin@xxxxxxxxxxxxxxxx>
Date: Thu, 19 Feb 2004 14:41:55 -0500 (EST)

I realize my lack of clarity in the thread "extracting sequences" may
have confused some readers as to what my problem was.  Therefore, I am
starting from scratch.

The following is a textual depiction of a DAG (directed acyclic graph)
modeled by the RDF at the end of this message, where numbers represent
nodes, letters represent link labels, and indentation models
parent-child relationships.

 -a-> 2
      -d-> 5
      -e-> 6

 -b-> 3
      -g-> 7
      -f-> 6
 -c-> 4
      -h-> 7

In the above graph, edges f and h are crosslinks as their target nodes
already exist in the graph.  They are like symbolic links (e.g., links
prefaced with the '@' character in the Yahoo! taxonomy).  In other
words, leaf nodes 6 and 7 are not in the graph twice. Rather they just
each have two in-coming edges (and two parents) while every other node,
with the exception of the root (node 1), has only 1 in-coming edge (and
thus only one parent).  In my RDF data crosslinks are modeled with
<crosslink> tags while all other edges are modeled with <link> tags.

It can be seen that the paths through this DAG are the following, where a
path is a space delimited sequence of edge labels from the root of the
DAG to a leaf.

a d
a e
b g
b f
c h

I'd like to extract these sequences from the RDF data.  Does anyone have
any ideas regarding how this transformation might proceed?  I am having
trouble following nodes to their descendants as the RDF is not nested.

Thank You and Kind Regards,


<RDF xmlns:r="http://www.w3.org/TR/RDF/";

<Node r:id="Root">
   <link r:resource="Root/a"></link>
   <link r:resource="Root/b"></link>
   <link r:resource="Root/c"></link>

<Node r:id="Root/a">
   <link r:resource="Root/a/d"></link>
   <link r:resource="Root/a/e"></link>

<Node r:id="Root/b">
   <link r:resource="Root/b/g"></link>
   <crosslink r:resource="f:Root/a/e"></symbolic>

<Node r:id="Root/c">
   <crosslink r:resource="h:Root/b/g"></link>

<Node r:id="Root/a/d">

<Node r:id="Root/a/e">

<Node r:id="Root/b/g">


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list

Current Thread