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

Question

我有一个 XML 文件，它编码定向无环图（DAG） 代表一个 偏序. 。此类图对于指定依赖关系和查找等事情很有用 关键路径. 。出于好奇，我当前的应用程序是指定组件依赖关系 构建系统, ，因此顶点是组件，边指定编译时依赖项。这是一个简单的例子：

<?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 样式表 产生另一个XML文档，仅包含与 最小元素 的偏序。即那些没有传入边的顶点。示例图的最小顶点集是 {A, B, F}. 。对于我的构建依赖项应用程序，找到这个集合很有价值，因为我知道如果我构建这个集合的成员，那么我的项目中的所有内容都将被构建。

这是我当前的样式表解决方案（我使用 Apache Ant 在 Java 上的 Xalan 上运行此解决方案） xslt 任务）。一个关键的观察是最小顶点不会在任何 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 目标生成 图形可视化 点 语言 用于渲染图形的代码。这是 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的隐性存在量化的：

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

当您使用任何六个比较运算符（=，!=，<，<=，>，和>=）的比较的节点集，表达式将返回真，如果在节点集合满足任何节点的条件。当比较一个节点集与另一个，则表达式返回true如果在第一节点设定满足任何节点当与在所述第二节点集的任何节点相比的条件。 XPath 2.0中引入了不执行此存在量化（eq，ne，lt，le，gt和ge）六个新的运营商。但是，在你的情况，你会希望使用“=”来获取存在量词。

当然，请注意，你还是会希望使用not()功能，你在干什么。在大多数情况下，这是很好的避免!=操作。如果你使用它，而不是在这里的not()，那么它会是否存在不等于@vertex价值，这是不是你的本意任何@name属性返回true。 （如果任一节点集合为空，则它将返回假，与空节点集比较总是返回false。）

如果你想使用eq代替，那么你就必须做一些像你这样：从迭代分离出的条件，所以你可以绑定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()结合是不同的）。

最后，我将添加一个更多的变化，在某些方面简化了（除去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"/>

哪种方法你把部分取决于味道，部分依赖于你的样式表的更广泛的范围和预期的数据（多少输入结构可能会有所不同，等等）。

我知道我又远远超出你问的什么，但我希望你至少发现了这种兴趣ING。 ： - ）

Answer 2

此类 XPath 1.0 表达式之一是:

        /*/vertex[not(@name = /*/vertex/directed-edge-to/@vertex)]

然后将其放入 XSLT 样式表中，如下所示:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

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

当此样式表应用于最初提供的 XML 文档时:

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

想要的结果已产生:

<minimal-vertices>
  <minimal-vertex name="A" />
  <minimal-vertex name="B" />
  <minimal-vertex name="F" />
</minimal-vertices>

请注意: XSLT 中提供了遍历完整（可能是循环）图的解决方案 这里.