Поиск минимальных элементов (вершин) ориентированного ациклического графа (DAG) с помощью XSLT / XPath? - PullRequest
7 голосов
/ 09 мая 2009

У меня есть файл 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}. Для моего приложения для построения зависимостей найти этот набор полезно, потому что я знаю, что если я соберу членов этого набора, то все в моем проекте будет построено.

Вот мое текущее решение для таблиц стилей (я запускаю его с Xalan на Java, используя задачу Apache Ant 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 генерирует 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>

Ответы [ 2 ]

8 голосов
/ 10 мая 2009

Вы можете воспользоваться неявной экзистенциальной квантификацией 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(), то он вернул бы true, если есть какие-либо атрибуты @vertex, которые не равны значению @name, что не является вашим намерением. (И если любой набор узлов пуст, тогда он вернет 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"/>

Какой подход вы выберете, частично зависит от вкуса, частично зависит от более широкого контекста вашей таблицы стилей и ожидаемых данных (насколько может изменяться структура ввода и т. Д.).

Я знаю, что я вышел далеко за рамки того, о чем вы просили, но я надеюсь, что вы хотя бы нашли это интересным : -)

5 голосов
/ 10 мая 2009

Одним из таких выражений 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 здесь .

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...