paths through DAGs

Hello,

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.

1
 -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,
Saverio

--

<RDF xmlns:r="http://www.w3.org/TR/RDF/";
xmlns:d="http://purl.org/dc/elements/1.0/";>

<Node r:id="Root">
   <num>1</num>
   <d:Title>Root</d:Title>
   <link r:resource="Root/a"></link>
   <link r:resource="Root/b"></link>
   <link r:resource="Root/c"></link>
</Node>

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

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

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

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

<Node r:id="Root/a/e">
   <num>6</num>
   <d:Title>e</d:Title>
</Node>

<Node r:id="Root/b/g">
   <num>7</num>
   <d:Title>g</d:Title>
</Node>

</RDF>

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