XSLT: проверить, прошел ли элемент ранее - PullRequest
Новая
       3

XSLT: проверить, прошел ли элемент ранее

2 голосов
/ 22 декабря 2011

Я пытаюсь визуализировать некоторые данные из большого XML-файла с помощью XSLT. Данные XML на самом деле являются графическими данными, а не иерархическими. и элементы связаны друг с другом и, как таковые, могут иметь круговую ссылку (однако типы отношений различны).

Я пытаюсь пройти через отношения одного элемента, посещая каждый связанный элемент и так далее. Таким образом, иногда я достигаю одного элемента, который я уже прошел. В таком случае я должен прекратить движение дальше, иначе я буду работать в цикле.

Моя проблема в том, что я не могу сохранить список элементов, которые я уже просмотрел, и проверять каждый раз, когда я начинаю обходить элемент, чтобы я мог прекратить обход, если элемент находится в поиске.

Проще говоря, я хотел сохранить элементы в справочной таблице и добавлять каждый элемент в нее при прохождении.

Есть ли какое-то решение для этого?

Ответы [ 2 ]

7 голосов
/ 23 декабря 2011

Рекурсивный шаблон может сам передавать параметры, которые содержат набор узлов «ранее» обработанных узлов и очередь узлов, подлежащих обработке.Это функциональный программный эквивалент изменения переменных состояния.

Пример ввода: 

<graph startNode="a">
    <graphNode id="a">
        <edge target="b" />
        <edge target="c" />
    </graphNode>
    <graphNode id="b">
        <edge target="c" />
    </graphNode>
    <graphNode id="c">
        <edge target="d" />
    </graphNode>
    <graphNode id="d">
        <edge target="a" />
        <edge target="b" />
    </graphNode>
</graph>

Таблица стилей XSL 2.0: 

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

    <xsl:output method="xml" indent="yes"/>

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

    <xsl:template match="/graph">
        <results>
            <xsl:apply-templates select="key('graphNodeByID', @startNode)"
                     mode="process"/>            
        </results>
    </xsl:template>

    <xsl:template match="graphNode" mode="process">
        <xsl:param name="already-processed" select="/.." />
        <xsl:param name="queue" select="/.." />

        <!-- do stuff with context node ... -->
        <processing node="{@id}" />

        <!-- Add connected nodes to queue, excluding those already processed. -->
        <xsl:variable name="new-queue"
              select="($queue | key('graphNodeByID', edge/@target))
                        except ($already-processed | .)" />

        <!-- recur on next node in queue. -->
        <xsl:apply-templates select="$new-queue[1]" mode="process">
            <xsl:with-param name="already-processed"
                            select="$already-processed | ." />
            <xsl:with-param name="queue" select="$new-queue" />
        </xsl:apply-templates>
    </xsl:template>

</xsl:stylesheet>

Вывод (проверено): 

<results>
   <processing node="a"/>
   <processing node="b"/>
   <processing node="c"/>
   <processing node="d"/>
</results>

Как указано, ни один узел не обрабатывается дважды, даже если график содержит циклы.

3 голосов
/ 22 декабря 2011

Это не сложно сделать в XSLT 1.0, см. Мой ответ 2004 года на более конкретную проблему обхода графа:

http://lists.xml.org/archives/xml-dev/200401/msg00444.html

Вотполное решение для обхода направленного графа XSLT 1.0 , предполагающее конкретное представление XML для направленных ссылок (как вы забыли показать нам исходный документ XML ...): 

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

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

 <xsl:template match="/">
  <xsl:call-template name="gTraverse">
   <xsl:with-param name="pNode" select="/*/a"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="gTraverse">
   <xsl:param name="pNode"/>
   <xsl:param name="pVisited" select="/.."/>
   <xsl:param name="pMustVisit" select="/.."/>

   <xsl:variable name="vnewVisited" select=
   "$pVisited | $pNode"/>

   <xsl:variable name="vnewNodes" select=
   "key('kNodeById',
         ($pNode/linkTo
        |
          /*/*[linkTo=$pNode/@id])/@id
          )
          [not(@id = $vnewVisited/@id)]
   "/>

   <xsl:variable name="vnewMustVisit" select=
    "$pMustVisit[count(.|$pNode) > 1] | $vnewNodes"/>

   <xsl:choose>
    <xsl:when test="not($vnewMustVisit)">
     <xsl:copy-of select="$vnewVisited"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="gTraverse">
       <xsl:with-param name="pNode" select=
       "$vnewMustVisit[1]"/>
       <xsl:with-param name="pVisited" select="$vnewVisited"/>
       <xsl:with-param name="pMustVisit" select=
       "$vnewMustVisit[position() > 1]"/>
      </xsl:call-template>
    </xsl:otherwise>
   </xsl:choose>
 </xsl:template>
</xsl:stylesheet>

когда это преобразование применяется к следующему документу XML , представляющему ориентированный граф с 5 вершинами: 

<graph>
 <a id ="1">
  <linkTo>2</linkTo>
  <linkTo>5</linkTo>
 </a>
 <b id ="2">
  <linkTo>3</linkTo>
  <linkTo>5</linkTo>
 </b>
 <c id ="3">
  <linkTo>1</linkTo>
  <linkTo>4</linkTo>
 </c>
 <d id ="4">
  <linkTo>1</linkTo>
 </d>
 <e id ="5">
  <linkTo>3</linkTo>
  <linkTo>4</linkTo>
 </e>
 <f id ="6">
  <linkTo>1</linkTo>
 </f>
</graph>

получается правильный результат (все узлы графа) * ​​1018*: 

<a id="1">
   <linkTo>2</linkTo>
   <linkTo>5</linkTo>
</a>
<b id="2">
   <linkTo>3</linkTo>
   <linkTo>5</linkTo>
</b>
<c id="3">
   <linkTo>1</linkTo>
   <linkTo>4</linkTo>
</c>
<d id="4">
   <linkTo>1</linkTo>
</d>
<e id="5">
   <linkTo>3</linkTo>
   <linkTo>4</linkTo>
</e>
<f id="6">
   <linkTo>1</linkTo>
</f>
...