使用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可能如下所示:

http://iparelan.com/dag.png

我想应用一个XSLT 样式表来生成另一个XML文档,该文档只包含与偏序的最小元素对应的顶点.也就是说,那些没有传入边的顶点.示例图的最小顶点集是{A, B, F}.对于我的构建依赖项应用程序,找到这个集合是有价值的,因为我知道如果我构建这个集合的成员,那么我的项目中的所有内容都将被构建.

这是我当前的样式表解决方案(我使用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 点 的语言渲染图形的代码.这是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,如果在节点集满足任何节点的条件.将一个节点集与另一个节点集进行比较时,如果第一个节点集中的任何节点在与第二个节点集中的任何节点进行比较时满足条件,则表达式返回true.XPath 2.0中引入了不执行此存在量化(六个新的运营商eq,ne,lt,le,gt,和ge).但在你的情况下,你会想用" ="来获得存在量化.

当然,请注意,您仍然希望使用该not()功能.大多数时候,避免!=操作员是件好事.如果你在这里使用它而不是not(),那么如果有任何@vertex属性不等于@name值,它将返回true ,这不是你的意图.(如果任一节点集为空,那么它将返回false,因为与空节点集的比较总是返回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"/>

您采用哪种方法部分取决于品味,部分取决于样式表和预期数据的更广泛背景(输入结构可能变化多少等).

我知道我超越了你的要求,但我希望你至少发现这很有趣.:-)

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可用 这里.