如何在XSL中获取有向无环图中关联元素的所有路径？

问题背景 #

我拥有一组元素和一组带有sourceRef与targetRef属性的有向链接，构成一个有向无环图（directed acyclic graph，DAG）。需要获取该图中的所有路径。

输入XML示例 #

<?xml version="1.0" encoding="UTF-8"?>
<root>
    <element id="a" />
    <element id="b" />
    <element id="c" />
    <element id="d" />
    <element id="e" />

    <link sourceRef="a" targetRef="b" />
    <link sourceRef="b" targetRef="c" />

    <link sourceRef="a" targetRef="d" />
    <link sourceRef="d" targetRef="c" />

    <link sourceRef="a" targetRef="e" />

</root>

期望输出XML #

<paths>
    <path>
        <element id="a" />
        <element id="b" />
        <element id="c" />
    </path>
    <path>
        <element id="a" />
        <element id="d" />
        <element id="c" />
    </path>
    <path>
        <element id="a" />
        <element id="e" />
    </path>
</paths>

XSLT 1.0实现方案 #

以下是基于递归遍历的XSLT 1.0解决方案，通过追踪路径节点避免循环（因输入是DAG，实际不会出现循环，但逻辑上保留防循环处理）：

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>

<xsl:key name="element-by-id" match="element" use="@id" />
<xsl:key name="outgoing-links" match="link" use="@sourceRef" />

<xsl:template match="/root">
    <paths>
        <!-- 遍历所有起始节点（无入度的节点） -->
        <xsl:apply-templates select="element[not(key('outgoing-links', @id)/@targetRef = current()/@id)]">
            <xsl:with-param name="path" select="." />
        </xsl:apply-templates>
    </paths>
</xsl:template>

<xsl:template match="element">
    <xsl:param name="path" />
    <!-- 检查当前节点是否已在路径中（防循环） -->
    <xsl:if test="not($path/element/@id = @id)">
        <xsl:variable name="new-path" select="$path | ." />
        <!-- 获取当前节点的所有出链目标 -->
        <xsl:variable name="targets" select="key('outgoing-links', @id)/@targetRef" />
        <xsl:choose>
            <!-- 如果没有出链，输出完整路径 -->
            <xsl:when test="not($targets)">
                <path>
                    <xsl:copy-of select="$new-path" />
                </path>
            </xsl:when>
            <!-- 否则递归遍历每个目标节点 -->
            <xsl:otherwise>
                <xsl:for-each select="key('element-by-id', $targets)">
                    <xsl:apply-templates select=".">
                        <xsl:with-param name="path" select="$new-path" />
                    </xsl:apply-templates>
                </xsl:for-each>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:if>
</xsl:template>

</xsl:stylesheet>

XSLT 2.0实现方案 #

XSLT 2.0支持更简洁的递归和序列处理，以下是优化后的实现：

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>

<xsl:key name="element-by-id" match="element" use="@id" />
<xsl:key name="outgoing-links" match="link" use="@sourceRef" />

<xsl:template match="/root">
    <paths>
        <!-- 处理所有起始节点 -->
        <xsl:for-each select="element[not(exists(key('outgoing-links', @id)/@targetRef = current()/@id))]">
            <xsl:call-template name="build-path">
                <xsl:with-param name="current-node" select="." />
                <xsl:with-param name="current-path" select="." />
            </xsl:call-template>
        </xsl:for-each>
    </paths>
</xsl:template>

<xsl:template name="build-path">
    <xsl:param name="current-node" as="element(element)" />
    <xsl:param name="current-path" as="element(element)*" />
    
    <xsl:variable name="target-ids" select="key('outgoing-links', $current-node/@id)/@targetRef" />
    <xsl:if test="empty($target-ids)">
        <path>
            <xsl:copy-of select="$current-path" />
        </path>
    </xsl:if>
    
    <!-- 递归处理每个目标节点 -->
    <xsl:for-each select="key('element-by-id', $target-ids)">
        <xsl:call-template name="build-path">
            <xsl:with-param name="current-node" select="." />
            <xsl:with-param name="current-path" select="$current-path, ." />
        </xsl:call-template>
    </xsl:for-each>
</xsl:template>

</xsl:stylesheet>

方案说明 #

• 两个版本均通过<xsl:key>建立元素ID和出链的索引，提升查询效率
• 从无入度的起始节点开始遍历，递归追踪每个节点的出链目标
• 当节点没有出链时，将当前累积的路径输出为<path>元素
• 因输入是有向无环图，无需额外处理循环，但代码中保留了防循环逻辑（XSLT 1.0版本通过检查节点是否已在路径中实现）

内容的提问来源于stack exchange，提问作者64kilobit