xslt - 使用 XSLT/XPath 查找有向无环图 (DAG) 最小元素(顶点)？

Question

我有一个编码一个 XML 文件
directed acyclic graph(DAG)表示 partial order .这样的图表对于指定依赖关系和查找 critical paths 等事情很有用。 .出于好奇，我当前的应用程序是为 build system 指定组件依赖项。 ，所以顶点是组件，边指定编译时依赖项。这是一个简单的例子:

<?xml version="1.0"?>
<dag>
    <vertex name="A">
        <directed-edge-to vertex="C"/>
    </vertex>
    <vertex name="B">
        <directed-edge-to vertex="C"/>
        <directed-edge-to vertex="D"/>
    </vertex>
    <vertex name="C">
        <directed-edge-to vertex="E"/>
    </vertex>
    <vertex name="D">
        <directed-edge-to vertex="E"/>
    </vertex>
    <vertex name="E">
        <directed-edge-to vertex="G"/>
    </vertex>
    <vertex name="F">
        <directed-edge-to vertex="G"/>
    </vertex>
    <vertex name="G"/>
</dag>

这个 DAG 可以这样绘制:


(来源: iparelan.com)

我想申请 XSLT stylesheet生成另一个 XML
仅包含与 minimal elements 对应的顶点的文档的偏序。也就是说，那些没有传入边的顶点。示例图的最小顶点集是 {A, B, F} .对于我的构建依赖应用程序，找到这个集合很有值(value)，因为我知道如果我构建这个集合的成员，那么我的项目中的所有内容都将被构建。

这是我当前的样式表解决方案(我使用 Apache Ant 的 xslt 任务在 Java 上使用 Xalan 运行它)。一个关键的观察结果是任何 directed-edge-to 中都不会引用最小顶点。元素:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
                xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:xalan="http://xml.apache.org/xslt"
                exclude-result-prefixes="xalan">
    <xsl:output method="xml" indent="yes" xalan:indent-amount="4"/>

    <xsl:template match="dag">
        <minimal-vertices>
            <xsl:for-each select="//vertex">
                <xsl:if test="not(//vertex/directed-edge-to[@vertex=current()/@name])">
                    <minimal-vertex name="{@name}"/>
                </xsl:if>
            </xsl:for-each>
        </minimal-vertices>
    </xsl:template>
</xsl:stylesheet>

应用此样式表会产生以下输出(我认为这是正确的):

<?xml version="1.0" encoding="UTF-8"?>
<minimal-vertices>
    <minimal-vertex name="A"/>
    <minimal-vertex name="B"/>
    <minimal-vertex name="F"/>
</minimal-vertices>

问题是，我对这个解决方案并不完全满意。 我想知道是否有一种方法可以组合 select的for-each和 test的if使用 XPath 语法。

我想写一些类似的东西:

<xsl:for-each select="//vertex[not(//vertex/directed-edge-to[@vertex=current()/@name])]">

但这并不能满足我的要求，因为 current()函数不引用外部 //vertex 选择的节点表达。

到目前为止，我的解决方案使用 XPath 1.0和 XSLT 1.0语法，尽管我对 XPath 2.0 持开放态度和 XSLT 2.0语法也是如此。

如果您愿意，这是 Ant 构建脚本:

<?xml version="1.0"?>
<project name="minimal-dag" default="default">
    <target name="default">
        <xslt in="dag.xml" out="minimal-vertices.xml" style="find-minimal-vertices.xsl"/>
    </target>
    <target name="dot">
        <xslt in="dag.xml" out="dag.dot" style="xml-to-dot.xsl"/>
    </target>
</project>

dot目标生成 Graphviz Dot language用于渲染图形的代码。这里是 xml-to-dot.xsl :

<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
                xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:xalan="http://xml.apache.org/xslt"
                exclude-result-prefixes="xalan">
    <xsl:output method="text"/>

    <xsl:template match="dag">
        digraph {
        rankdir="BT";
        node [style="filled", fillcolor="cyan", fontname="Helvetica"];
        <xsl:apply-templates select="//directed-edge-to"/>
        }
    </xsl:template>

    <xsl:template match="directed-edge-to">
        <xsl:value-of select="concat(ancestor::vertex/@name, '->', @vertex, ';')"/>
    </xsl:template>
</xsl:stylesheet>

Answer 1

您可以在 = 上利用 XPath 的隐式存在量化。运算符(operator):

<xsl:for-each select="//vertex[not(@name = //vertex/directed-edge-to/@vertex)]">

当您使用六个比较运算符( = 、 != 、 < 、 <= 、 > 和 >= )来比较节点集时，如果有任何节点，表达式将返回 true在节点集中满足条件。在将一个节点集与另一个节点集进行比较时，如果第一个节点集中的任何节点在与第二个节点集中的任何节点进行比较时满足条件，则表达式返回 true。 XPath 2.0 引入了六个不执行这种存在量化的新运算符( eq、 ne、 lt、 le、 gt 和 ge)。但在你的情况下，你会想要使用“ =”来获得存在量化。

当然请注意，您仍然需要使用 not()像你做的那样工作。大多数时候，最好避免使用 !=运算符(operator)。如果你在这里使用它而不是 not() , 如果有 @vertex 则返回 true不等于 @name 的属性值，这不是你的意图。 (如果任一节点集为空，则返回 false，因为与空节点集的比较总是返回 false。)

如果你想使用 eq取而代之的是，您必须像以前那样做:将条件从迭代中分离出来，这样您就可以绑定(bind) current() .但在 XPath 2.0 中，您可以在表达式中执行此操作:

<xsl:for-each select="for $v in //vertex
                      return $v[not(//directed-edge-to[@vertex eq $v/@name])]">

当您的条件不是简单的相等比较时(因此无法使用“ =”进行存在量化)，这很有用。例如: starts-with(@vertex, $v/@name) .

XPath 2.0 还具有执行存在量化的显式方法。而不是 for上面的表达式，我们可以这样写:

<xsl:for-each select="//vertex[not(some $e in //directed-edge-to
                                   satisfies @name eq $e/@vertex)]">

除了“ some”语法之外，XPath 2.0 还提供了相应的“ every”语法来执行通用量化。

而不是使用 for-each ，您还可以使用更模块化(且功能强大)的模板规则:

<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

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

  <!-- Copy vertex elements that have no arrows pointing to them -->
  <xsl:template match="vertex[not(@name = //directed-edge-to/@vertex)]">
    <minimal-vertex name="{@name}"/>
  </xsl:template>

</xsl:stylesheet>

同样，在这种情况下，我们依赖于 = 的存在量化。 .

XSLT 1.0 禁止使用 current()模式中的函数，即在 match 中属性，但 XSLT 2.0 允许。在这种情况下， current()指当前匹配的节点。所以在 XSLT 2.0 中，我们也可以这样写(不必使用 for 表达式):

<xsl:template match="vertex[not(//directed-edge-to[@vertex eq current()/@name])]">

请注意，此模式与您尝试在 for-each 中使用的表达式基本相同。 , 但是它在 for-each 中并没有做你想做的事，它确实在模式中执行您想要的操作(因为 current() 绑定(bind)的内容不同)。

最后，我将添加一个在某些方面简化逻辑的变体(删除 not() )。这也可以追溯到使用 XSLT 1.0:

<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

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

  <!-- By default, copy vertex elements -->
  <xsl:template match="vertex">
    <minimal-vertex name="{@name}"/>
  </xsl:template>

  <!-- But strip out vertices with incoming arrows -->
  <xsl:template match="vertex[@name = //directed-edge-to/@vertex]"/>

</xsl:stylesheet>

如果您不喜欢输出空格，请为文本节点添加一个空规则，这样它们就会被剥离(覆盖文本节点的默认规则，即复制它们):

<xsl:template match="text()"/>

或者，您可以在将模板应用到的节点上更具选择性:

<xsl:apply-templates select="/dag/vertex"/>

您采用哪种方法部分取决于品味，部分取决于样式表的更广泛上下文和预期数据(输入结构可能有多少变化等)。

我知道我远远超出了你的要求，但我希望你至少觉得这很有趣。 :-)