Отбраковка ребер графа с использованием XSLT

Question

У меня есть ориентированный граф, представленный в XML, как показано в минималистском примере ниже.Я ищу способ программно отбирать избыточные ребра для создания минимизированного орграфа.

В частности, A -> B -> C, поэтому мне не нужна ссылка непосредственно из A -> C: отношениямежду А и С уже подразумевается связь между А и В, а между В и С.

Я начинаю с

<graph>
  <node id="A" />
  <node id="B" />
  <node id="C" />
  <edge src="A" dest="B" />
  <edge src="A" dest="C" />
  <edge src="B" dest="C" />
</graph>

То, что я хочу, это

<graph>
  <node id="A" />
  <node id="B" />
  <node id="C" />
  <edge src="A" dest="B" />
  <edge src="B" dest="C" />
</graph>

Я почти уверен, что ищу <xsl:template> с правилом сопоставления, которое говорит что-то вроде "edge, у которого есть два родных брата, так что у одного такой же src, как у меня, у другого такое же назначение, как у меня, иони совпадают по своим соотношениям dest и source vales "(что даже на английском языке).Я не вижу, как сформулировать это как шаблон соответствия шаблону или даже выделение в шаблоне.Я могу понять, как это сделать, проверяя (сравнивая каждую пару братьев и сестер, чтобы увидеть, могу ли я выбрать эту), но я бы предпочел избежать этого: это сработало бы, и у меня не так много ребер, что яМеня особенно беспокоит время выполнения O (nn), но оно не элегантно.

Answer 1

Я пытался использовать XSLT (2 или 3), чтобы указать условие вашего паттерна:

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

  <xsl:mode on-no-match="shallow-copy"/>

  <xsl:variable name="edges" select="/graph/edge"/>

  <xsl:template match="edge[some $edge1 in ($edges except .) 
                            satisfies 
                              $edge1/@src = @src
                              and 
                              (some $edge2 in ($edges except (., $edge1))
                               satisfies ($edge2/@dest = @dest and $edge1/@dest = $edge2/@src))]"/>

</xsl:stylesheet>

Результат (https://xsltfiddle.liberty -development.net / eiZQaFb )

<graph>
  <node id="A"/>
  <node id="B"/>
  <node id="C"/>
  <edge src="A" dest="B"/>

  <edge src="B" dest="C"/>
</graph>

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

Обратите внимание, что если вы используете XSLT 2, вам нужно заменить <xsl:mode on-no-match="shallow-copy"/> на идентификаторшаблон преобразования.

Чтобы найти другие ребра, можно также использовать ключи:

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

  <xsl:mode on-no-match="shallow-copy"/>

  <xsl:variable name="edges" select="/graph/edge"/>

  <xsl:key name="src" match="edge" use="@src"/>
  <xsl:key name="dest" match="edge" use="@dest"/>

  <xsl:template match="edge[some $edge1 in (key('src', @src) except .) 
                            satisfies 
                              some $edge2 in (key('dest', @dest) except (., $edge1))
                              satisfies $edge1/@dest = $edge2/@src]"/>

</xsl:stylesheet>

https://xsltfiddle.liberty -development.net / eiZQaFb / 1