半順序を表す有向非巡回グラフ (DAG)をエンコードする XML ファイルがあります 。このようなグラフは、依存関係の指定やクリティカル パスの検索などに役立ちます。興味深いことに、私の現在のアプリケーションはビルド システムのコンポーネントの依存関係を指定することなので、頂点はコンポーネントであり、エッジはコンパイル時の依存関係を指定します。簡単な例を次に示します。
<?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）
半順序の最小要素に対応する頂点のみを含む別の XML ドキュメントを生成するXSLT スタイルシートを適用したいと考えています。つまり、着信エッジを持たない頂点です。サンプル グラフの最小頂点のセットは です。私のビルド依存関係アプリケーションでは、このセットを見つけることは価値があります。なぜなら、このセットのメンバーをビルドすると、プロジェクト内のすべてがビルドされることがわかっているからです。{A, B, F}
これが私の現在のスタイルシート ソリューションです (Apache Ant のxsltタスクを使用して、Java 上の Xalan でこれを実行しています)。重要な観察事項は、最小頂点はどの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>
問題は、私はこのソリューションに完全に満足していないということです。のとのを XPath 構文と組み合わせる方法があるかどうか疑問に思っています。selectfor-eachtestif
私は次のようなものを書きたい：
<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 言語コードを生成し ます 。ここにある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>