代码之家 › 专栏 › 技术社区 › Gary

如何使用xsl计算有向无环图中的子节点数

directed-acyclic-graphs xslt xml

1

Gary · 技术社区 · 7 年前

我简化了一个表示有向无环图的xml文件:

<?xml version="1.0" encoding="utf-8"?>
<items>
  <item id="1">
  </item>
  <item id="2">
    <parent idref="1" />
  </item>
  <item id="3">
    <parent idref="1" />
  </item>
  <item id="4">
    <parent idref="3" />
  </item>
  <item id="5">
    <parent idref="4" />
  </item>
  <item id="6">
    <parent idref="3" />
  </item>
  <item id="7">
    <parent idref="4" />
  </item>
  <item id="8">
    <parent idref="4" />
  </item>
  <item id="9">
    <parent idref="4" />
  </item>
  <item id="10">
    <parent idref="6" />
  </item>
</items>

这种表示允许无限深(我不知道数学术语)。每个项都有且只有一个父项,根项除外,它没有父项。每个项目可以有0到任意数量的子项目。每个项目都由其id标识,id是一个任意标签。

用点表示法将图形可视化可能更容易。在我的文件中,更容易看到项目3有两个子节点,项目4有4个子节点:

digraph
{
    1 -> {2, 3}
    3 -> {4, 6}
    4 -> {5, 7, 8, 9}
    6 -> 10
}

第3项的儿童人数计算如下:

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

<xsl:template match="/">
    <xsl:value-of select="count(items/item/parent[@idref='3'])" />
</xsl:template>

</xsl:stylesheet>

xslt样式表输出2,这是正确的。如果我将3更改为4,则输出为4,这也是正确的。

问题 :我要计算特定项目的所有子项目。

对于第3项,正确答案是7(第4、6、5、7、8、9、10项)。对于第1项,答案是9。第7项为0。我怀疑答案涉及递归,我已经成功地使用递归构造了树的部分,但没有传递值或计算和。

2 回复 | 直到 7 年前

1

3

Martin Honnen 7 年前

对于以下交叉引用,我建议设置键,然后,为了解决问题,递归是解决方案的关键(另一个),因此在XSLT 2或3中,可以使用递归函数来实现这一点:

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:mf="http://example.com/mf"
    exclude-result-prefixes="xs mf"
    version="3.0">

  <xsl:param name="start-id">7</xsl:param>

  <xsl:key name="id" match="item" use="@id"/>
  <xsl:key name="child" match="item" use="parent/@idref"/>

  <xsl:function name="mf:descendants" as="element(item)*">
      <xsl:param name="item" as="element(item)*"/>
      <xsl:sequence 
        select="let $children := key('child', $item/@id, root($item))
                return ($children | $children!mf:descendants(.))"/>
  </xsl:function>

  <xsl:template match="/">
      <xsl:value-of select="count(mf:descendants(key('id', $start-id)))"/>
  </xsl:template>

</xsl:stylesheet>

https://xsltfiddle.liberty-development.net/bdxtpH/0 和 https://xsltfiddle.liberty-development.net/bdxtpH/1 和 https://xsltfiddle.liberty-development.net/bdxtpH/2 下面是一些例子。

对于XSLT 2,您将使用本地 xsl:variable 而不是 let $children 以上使用:

<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0"
      xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:mf="http://example.com/mf"
    exclude-result-prefixes="xs mf">

  <xsl:param name="start-id">1</xsl:param>

  <xsl:key name="id" match="item" use="@id"/>
  <xsl:key name="child" match="item" use="parent/@idref"/>

  <xsl:function name="mf:descendants" as="element(item)*">
      <xsl:param name="item" as="element(item)*"/>
      <xsl:variable name="children" select="key('child', $item/@id, root($item))"/>
      <xsl:sequence 
        select="$children | $children/mf:descendants(.)"/>
  </xsl:function>

  <xsl:template match="/">
      <xsl:value-of select="count(mf:descendants(key('id', $start-id)))"/>
  </xsl:template>

</xsl:transform>

http://xsltransform.hikmatu.com/pPgCcou

对于XSLT 1,您可以使用一种稍微不同的方法,使用一个递归的命名模板来收集子体,直到它找不到更多的子体,然后输出计数:

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

    <xsl:param name="start-id">7</xsl:param>

    <xsl:key name="id" match="item" use="@id"/>
    <xsl:key name="child" match="item" use="parent/@idref"/>

    <xsl:template name="count-descendants">
        <xsl:param name="descendants" select="/.."/>
        <xsl:param name="level"/>
        <xsl:variable name="children" select="key('child', $level/@id)"/>
        <xsl:choose>
            <xsl:when test="not($children)">
                <xsl:value-of select="count($descendants)"/>
            </xsl:when>
            <xsl:otherwise>
                <xsl:call-template name="count-descendants">
                    <xsl:with-param name="descendants" select="$descendants | $children"/>
                    <xsl:with-param name="level" select="$children"/>
                </xsl:call-template>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:template>

    <xsl:template match="/">
        <xsl:variable name="start-item" select="key('id', $start-id)"/>
        <xsl:call-template name="count-descendants">
            <xsl:with-param name="level" select="$start-item"/>
        </xsl:call-template>
    </xsl:template>

</xsl:stylesheet>

https://xsltfiddle.liberty-development.net/3NzcBsK/0 和 https://xsltfiddle.liberty-development.net/3NzcBsK/1 和 https://xsltfiddle.liberty-development.net/3NzcBsK/2 拥有样本数据。

2

0

Michael Kay 7 年前

为了多样性,这里有另一种方法:

<xsl:param name="start-id">7</xsl:param>

<xsl:key name="id" match="item" use="@id"/>

<xsl:function name="f:has-ancestor" as="xs:boolean">
  <xsl:param name="d" as="item"/>
  <xsl:param name="a" as="item"/>
  <xsl:sequence select="exists($d) and ($a is $d or 
       f:has-ancestor(key('id', $d/parent/@idref), $a))"/>
</xsl:function>

然后

select="count(//item[f:has-ancestor(., key('id', $start-id))])"/>

(当然,哪种速度更快取决于你的树的茂密程度。)