Trovare il grafico aciclico diretto (DAG) Elementi minimi (vertici) con XSLT/XPath?

Question

Ho un file XML che codifica uno directed acyclic graph (DAG) che rappresenta uno partial order. Questi grafici sono utili per cose come specificare le dipendenze e trovare critical paths. Per i curiosi, la mia attuale applicazione è di specificare le dipendenze dei componenti per un build system, quindi i vertici sono componenti e spigoli che specificano le dipendenze in fase di compilazione. Ecco un semplice esempio:

<?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> 

questo DAG può essere disegnato in questo modo:

http://iparelan.com/dag.png

mi piacerebbe applicare un XSLTstylesheet che produce un altro documento XML che contiene solo i vertici corrisponde a minimal elements dell'ordine parziale. Cioè quei vertici che non hanno bordi in entrata. L'insieme di vertici minimi per il grafico di esempio è {A, B, F}. Per la mia applicazione di dipendenza build, trovare questo set è prezioso perché so che se costruisco i membri di questo set, allora tutto il mio progetto sarà costruito.

Ecco la mia attuale soluzione per fogli di stile (sto eseguendo questa operazione con Xalan su Java utilizzando l'attività xslt di Apache Ant). Un'osservazione chiave è che un vertice minima non farà riferimento a qualsiasi elemento 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> 

Applicando questo foglio di stile produce il seguente output (che ritengo sia corretto):

<?xml version="1.0" encoding="UTF-8"?> 
<minimal-vertices> 
    <minimal-vertex name="A"/> 
    <minimal-vertex name="B"/> 
    <minimal-vertex name="F"/> 
</minimal-vertices> 

La cosa è, Non sono completamente soddisfatto di questa soluzione. Mi chiedo se sia possibile combinare loe lo test dello if con la sintassi XPath.

voglio scrivere qualcosa di simile:

<xsl:for-each select="//vertex[not(//vertex/directed-edge-to[@vertex=current()/@name])]"> 

Ma questo non fare quello che voglio perché la funzione current() non fa riferimento ai nodi selezionati dal esterna //vertex espressione.

thusfar, la mia soluzione usa XPath 1.0 e XSLT 1.0 sintassi, anche se io sono aperto a sintassi XPath 2.0 e XSLT 2.0 pure.

Ecco lo script Ant, se ti piace:

<?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> 

L'obiettivo dot genera codice GraphvizDotlanguage per il rendering grafico.Ecco 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> 

Answer 1

È possibile usufruire di implicita quantificazione esistenziale di XPath sull'operatore =:

<xsl:for-each select="//vertex[not(@name = //vertex/directed-edge-to/@vertex)]"> 

Quando si utilizza uno dei sei operatori di confronto (=, !=, <, <=, > e >=) per confrontare un set di nodi, l'espressione restituirà true se qualsiasi nodo nel set di nodi soddisfa la condizione. Quando si confronta un set di nodi con un altro, l'espressione restituisce true se qualsiasi nodo nel primo set di nodi soddisfa la condizione rispetto a qualsiasi nodo nel secondo set di nodi. XPath 2.0 introduce sei nuovi operatori che non eseguono questa quantificazione esistenziale (eq, ne, lt, le, gt e ge). Ma nel tuo caso, ti consigliamo di utilizzare "=" per ottenere quella quantificazione esistenziale.

Ovviamente, vorrete comunque utilizzare la funzione not() come stavate facendo. Nella maggior parte dei casi, è consigliabile evitare l'operatore !=. Se lo hai usato qui invece di not(), restituirebbe true se ci sono degli attributi @vertex che non sono uguali al valore @name, che non è la tua intenzione. (E se uno dei due set di nodi è vuoto, restituirà false, poiché i confronti con i set di nodi vuoti restituiscono sempre false.)

Se si desidera utilizzare eq, si dovrebbe fare qualcosa come te fatto: separare il condizionale dall'iterazione in modo da poter vincolare current(). Ma in XPath 2.0, è possibile farlo all'interno di un'espressione:

<xsl:for-each select="for $v in //vertex 
         return $v[not(//directed-edge-to[@vertex eq $v/@name])]"> 

Questo è utile per quando la condizione non è un semplice confronto di uguaglianza (e quindi non possono essere esistenzialmente quantificata utilizzando "="). Ad esempio: starts-with(@vertex, $v/@name).

XPath 2.0 ha anche un modo esplicito di eseguire la quantificazione esistenziale. Al posto della for espressione di cui sopra, avremmo potuto scrivere questo:

<xsl:for-each select="//vertex[not(some $e in //directed-edge-to 
            satisfies @name eq $e/@vertex)]"> 

Oltre al "some" sintassi, XPath 2.0 fornisce anche un corrispondente "every" Sintassi per l'esecuzione di universale quantificazione.

Piuttosto che usare for-each, si potrebbe anche utilizzare le regole di template, che sono più modulare (e potente):

<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> 

Ancora una volta, in questo caso, stiamo contando sulla quantificazione esistenziale di =.

XSLT 1.0 proibisce l'uso della funzione current() nei motivi, ad esempio nell'attributo match, ma XSLT 2.0 lo consente. In tal caso, current() fa riferimento al nodo correntemente associato. Quindi in XSLT 2.0, potremmo anche scrivere questo (senza dover utilizzare un for espressione):

<xsl:template match="vertex[not(//directed-edge-to[@vertex eq current()/@name])]"> 

Nota che questo modello è essenzialmente lo stesso come l'espressione si è tentato di utilizzare in for-each, ma mentre non fa quello che vuoi in for-each, è fa fai quello che vuoi nel modello (perché ciò che current() si lega a è diverso).

Infine, aggiungerò un'altra variazione che in qualche modo semplifica la logica (rimuovendo not()). Questo vale anche tornati a utilizzare 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> 

Se non vi piace l'uscita spazi essendo, aggiunge una regola vuota per i nodi di testo, in modo che otterranno spogliato fuori (ignorando la regola di default per i nodi di testo , che è quello di copiarli):

<xsl:template match="text()"/> 

Oppure si può semplicemente essere più selettivi in ​​quello che i nodi si applica i modelli per:

<xsl:apply-templates select="/dag/vertex"/> 

quale approccio si prende è parzialmente dipendente da gusti, in parte d ependent nel contesto più ampio del foglio di stile e dei dati previsti (quanto può variare la struttura di input, ecc.).

So che sono andato ben oltre quello che stavi chiedendo, ma spero che tu abbia trovato questo interessante. :-)

Answer 2

Un tale XPath 1.0 espressione è:

                /*/vertex[not(@name = /*/vertex/directed-edge-to/@vertex)]

Poi basta metterlo in un foglio di stile XSLT così:

<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> 

Quando questo foglio di stile viene applicato sul documento originariamente previsto 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> 

Il risultato voluto è prodotto:

<minimal-vertices> 
    <minimal-vertex name="A" /> 
    <minimal-vertex name="B" /> 
    <minimal-vertex name="F" /> 
</minimal-vertices> 

Do atto: Una soluzione per attraversando grafici completi (forse ciclici) è disponibile in XSLThere.