xslt - xsl テンプレートでの再帰の最適化

Question

この古典的なグラフの問題を解決する必要があります... in xsl : 特定のソース ノードからシンク ノードへのすべてのパスに属するすべてのノードのリストを計算する必要があります (最終的にはサイクルを伴います)。このようなグラフを表す xml ファイルの例を次に示します ((D,C) サイクルを使用)。

<?xml version="1.0"?>
<graph>
    <node id="A" source="yes">
        <child node="D"/>
        <child node="G"/>
    </node>
    <node id="B">
        <child node="E"/>
        <child node="F"/>
    </node>
    <node id="C">
        <child node="D"/>
        <child node="E"/>
        <child node="F"/>
    </node>
    <node id="D">
        <child node="C"/>
        <child node="E"/>
        <child node="F"/>
    </node>
    <node id="E"/>
    <node id="F"/>
    <node id="G"/>
</graph>

これは私が書いたスタイルシートで、すでに訪問したノードのリストと訪問するノードのリストを格納する2つのパラメータを持つ再帰テンプレートを使用しています:

<?xml version="1.0"?>

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:exslt="http://exslt.org/common"  exclude-result-prefixes="exslt">

  <xsl:output  method="xml" indent="yes"/>
    <xsl:key name="nodes" match="node" use="@id"/> 

    <xsl:template match="/">
        <xsl:apply-templates/>
    </xsl:template>

    <xsl:template match="graph">
        <graph>
            <xsl:call-template name="search-alt">
                <xsl:with-param name="todo">
                    <xsl:for-each select="node[@source='yes']">
                        <link node="{@id}"/>
                    </xsl:for-each>
                </xsl:with-param>
            </xsl:call-template>
        </graph>
    </xsl:template>

    <xsl:template name="search-alt">
        <xsl:param name="todo"/>
        <xsl:param name="visited"/>
        <xsl:variable name="nodeid" select="exslt:node-set($todo)/*[1]/@node"/>
        <xsl:choose>
            <xsl:when test="exslt:node-set($visited)/*[@node=$nodeid]">
                <xsl:if test="exslt:node-set($todo)/*[position()&gt;1]">
                    <xsl:call-template name="search-alt">
                        <xsl:with-param name="todo">
                            <xsl:copy-of select="exslt:node-set($todo)/*[position()&gt;1]"/>
                        </xsl:with-param>
                        <xsl:with-param name="visited">
                            <xsl:copy-of select="$visited"/>
                        </xsl:with-param>
                    </xsl:call-template>
                </xsl:if>
            </xsl:when>
            <xsl:when test="(key('nodes',$nodeid)/child) or (exslt:node-set($todo)/*[position()&gt;1])">
                <node id="{$nodeid}"/>
                <xsl:call-template name="search-alt">
                    <xsl:with-param name="todo">
                        <xsl:copy-of select="key('nodes',$nodeid)/child"/>
                        <xsl:copy-of select="exslt:node-set($todo)/*[position()&gt;1]"/>
                    </xsl:with-param>
                    <xsl:with-param name="visited">
                        <xsl:copy-of select="$visited"/>
                        <link node="{$nodeid}"/>
                    </xsl:with-param>
                </xsl:call-template>
            </xsl:when>
        </xsl:choose>
    </xsl:template>

</xsl:stylesheet>

上記のグラフでは、スタイルシートは私が期待するもの (訪問されたノードで構成される切断されたグラフ) を出力します。つまり、B ノードは訪問されません。

<graph>
    <node id="A"/>
    <node id="D"/>
    <node id="C"/>
    <node id="E"/>
    <node id="F"/>
</graph>

このテンプレートをより大きなグラフ (2,000 ノード) でテストしましたが、接続が弱く (ノードの子が 7 つ未満)、私の xslt プロセッサはジョブを実行するのに 2 秒しかかかりません。

より大きなグラフを扱う必要があるので、私の質問は次のとおりです。ここでは最長パスの長さに等しい再帰のレベルを下げることは可能ですか? より大きな問題は、2 つのリストをパラメーターとして渡す必要があり、単調に増加することです。

ヒントをありがとう！

S.