[xsl] Graph processing

Subject: [xsl] Graph processing
From: "Ken Tam" <kentam@xxxxxxxxxxxxxxx>
Date: Wed, 19 Mar 2008 21:49:44 -0700
Hi all,

I need to process graphs in GraphML format. For example,

given the following graph:

                  A
                / | \
               B  C  D
              / \
             E   F
            / \ / \
           G   H   I
              / \
             J   K

will be represented in GraphML as:

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns";
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance";
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd";>
  <graph id="G" edgedefault="directed">
    <node id="A"/>
    <node id="B"/>
    <node id="C"/>
    <node id="D"/>
    <node id="E"/>
    <node id="F"/>
    <node id="G"/>
    <node id="H"/>
    <node id="I"/>
    <node id="J"/>
    <node id="K"/>
    <edge source="A" target="B"/>
    <edge source="A" target="C"/>
    <edge source="A" target="D"/>
    <edge source="B" target="E"/>
    <edge source="B" target="F"/>
    <edge source="E" target="G"/>
    <edge source="E" target="H"/>
    <edge source="F" target="H"/>
    <edge source="F" target="I"/>
    <edge source="H" target="J"/>
    <edge source="H" target="K"/>
  </graph>
</graphml>

One sample process is to find all paths starting from "B" passing through
"H" ending in "K". The results are:

B->E->H->K
B->F->H->K

Can XSL/XPATH be used to find the paths? or a transformation needs to be
done first from graph to tree with ID and IDREF before applying XPATH axis
expressions. This is just a simple example and the real graphs contain many
shared paths. Thus, a tree representation will be very large with many
duplicated branches.

Thanks,
Ken

Current Thread