XSLT/XPath로 지시 된 Acyclic Graph (DAG) 최소 요소 (정점)를 찾으십니까?
https://stackoverflow.com/questions/843874
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
a를 인코딩하는 XML 파일이 있습니다지시 된 acyclic 그래프 (DAG) 그것은 a를 나타냅니다 부분 순서. 이러한 그래프는 종속성 지정 및 찾기와 같은 것들에 유용합니다. 중요한 경로. 호기심을 위해, 내 현재 응용 프로그램은 빌드 시스템, 정점은 구성 요소이며 가장자리는 컴파일 타임 종속성을 지정합니다. 간단한 예는 다음과 같습니다.
<?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>
이 멍청이는 다음과 같이 그릴 수 있습니다.
(원천: iparelan.com)
신청하고 싶습니다 xslt 스타일 시트 이는 최소한의 요소 부분 순서의. 즉, 들어오는 가장자리가없는 정점. 예제 그래프의 최소 정점 세트는 {A, B, F}. 내 빌드 종속성 응용 프로그램의 경우이 세트를 찾는 것이이 세트의 구성원을 구축하면 프로젝트의 모든 것이 구축 될 것임을 알고 있기 때문에 가치가 있습니다.
다음은 내 현재 스타일 시트 솔루션입니다 (Apache Ant 's를 사용하여 Java에서 Xalan과 함께이 작업을 실행하고 있습니다. 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 점 언어 그래프 렌더링 코드. 여기에 있습니다 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>
해결책
XPath의 암시 적 실존 정량화를 활용할 수 있습니다. = 운영자:
<xsl:for-each select="//vertex[not(@name = //vertex/directed-edge-to/@vertex)]">
6 개의 비교 연산자 중 하나를 사용할 때 (=, !=, <, <=, >, 그리고 >=) 노드 세트를 비교하기 위해 노드 세트의 노드가 조건을 만족하면 표현식이 true를 반환합니다. 한 노드 세트를 다른 노드 세트와 비교할 때, 첫 번째 노드 세트의 노드가 두 번째 노드 세트의 노드와 비교할 때 조건을 충족하면 표현식이 true를 반환합니다. XPath 2.0은이 실존 적 정량화를 수행하지 않는 6 명의 새로운 연산자를 소개합니다 (eq, ne, lt, le, gt, 그리고 ge). 그러나 귀하의 경우 사용하고 싶을 것입니다. "="그 실존 적 정량화를 얻기 위해.
물론, 당신은 여전히 not() 당신이하고있는 것처럼 기능하십시오. 대부분의 경우, 피하는 것이 좋습니다. != 운영자. 대신 여기에서 사용했다면 not(), 그러면 @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"/>
당신이 취하는 접근법은 부분적으로 취향에 따라 스타일 시트의 더 넓은 맥락과 예상 데이터 (입력 구조가 달라질 수있는 양 등)에 부분적으로 의존합니다.
나는 내가 당신이 요구하는 것 이상으로 나아 갔다는 것을 알고 있지만, 나는 당신이 적어도 이것을 흥미롭게 발견했기를 바랍니다. :-)
다른 팁
그러한 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에서 사용할 수 있습니다. 여기.
