0

我需要解决这个经典的图问题......在 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>

这是我编写的样式表，它使用带有两个参数的递归模板，用于存储已访问节点列表和要访问节点列表：

<?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>

我已经在一个更大的图（两千个节点）上测试了这个模板，但连接很弱（节点的子节点少于 7 个），我的 xslt 处理器只需要 2 秒就可以完成这项工作。

由于我需要使用更大的图，我的问题是：是否可以降低递归级别，这里等于最长路径的长度？更大的问题是这两个列表必须作为参数传递并且单调增长。

感谢您的提示！

S。

4

0 回答 0