¿Cómo encontrar gráficos acíclicos dirigidos (DAG) Elementos mínimos (vértices) con XSLT/XPath?

Question

Tengo un archivo XML que codifica directed acyclic graph (DAG) que representa un partial order. Dichos gráficos son útiles para cosas como especificar dependencias y encontrar critical paths. Para los curiosos, mi aplicación actual es especificar dependencias de componentes para un build system, por lo que los vértices son componentes y los bordes especifican las dependencias en tiempo de compilación. Aquí está un ejemplo sencillo:

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

Este DAG puede extraerse de esta manera:

http://iparelan.com/dag.png

me gustaría aplicar un XSLTstylesheet que produce otro documento XML que contiene sólo los vértices que corresponden a minimal elements del orden parcial. Es decir, aquellos vértices que no tienen bordes entrantes. El conjunto de vértices mínimos para el gráfico de ejemplo es {A, B, F}. Para mi aplicación de dependencia de compilación, encontrar este conjunto es valioso porque sé que si construyo los miembros de este conjunto, se construirá todo en mi proyecto.

Aquí está mi solución de hoja de estilo actual (estoy ejecutando esto con Xalan en Java usando la tarea xslt de Apache Ant). Una observación clave es que un vértice mínimo no se hace referencia en cualquier 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> 

La aplicación de esta hoja de estilo produce la siguiente salida (que creo que es correcta):

<?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 es, No estoy completamente satisfecho con esta solución. Me pregunto si hay una manera de combinar el select del for-each y el test del if con sintaxis XPath.

Quiero escribir algo como:

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

Pero eso no quiere hacer lo que quiera porque la función current() no hace referencia a los nodos seleccionados por el //vertex expresión externa.

Thusfar, mi solución utiliza XPath 1.0 y XSLT 1.0 sintaxis, aunque estoy abierto a XPath 2.0 y XSLT 2.0 sintaxis también.

Aquí está el script de construcción Ant si te gusta:

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

El objetivo dot genera código GraphvizDotlanguage para representar el gráfico.Aquí es 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

Usted puede tomar ventaja de la cuantificación existencial implícita de XPath en el operador =:

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

Cuando se utiliza cualquiera de los seis operadores de comparación (=, !=, <, <=, > y >=) para comparar un conjunto de nodos, la expresión devolverá verdadero si cualquier nodo en el conjunto de nodos satisface la condición. Al comparar un conjunto de nodos con otro, la expresión devuelve verdadero si cualquier nodo en el primer conjunto de nodos cumple la condición en comparación con cualquier nodo en el segundo conjunto de nodos. XPath 2.0 presenta seis nuevos operadores que no realizan esta cuantificación existencial (eq, ne, lt, le, gt y ge). Pero en su caso, querrá usar "=" para obtener esa cuantificación existencial.

Nota, por supuesto, que igual querrá usar la función not() como lo estaba haciendo. La mayoría de las veces, es bueno evitar el operador !=. Si lo usó aquí en lugar de not(), devolvería verdadero si hay algún atributo @vertex que no sea igual al valor @name, que no es su intención. (Y si cualquiera de los conjuntos de nodos está vacío, devolverá falso, ya que las comparaciones con conjuntos de nodos vacíos siempre devuelven falso.)

En su lugar, si desea usar eq, debe hacer algo como usted did: separa el condicional de la iteración para que pueda enlazar current(). Pero en XPath 2.0, puede hacerlo dentro de una expresión:

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

Esto es útil para cuando su condición no es una simple comparación de igualdad (y por lo tanto no puede ser cuantificado usando existencialmente "="). Por ejemplo: starts-with(@vertex, $v/@name).

XPath 2.0 también tiene una forma explícita de realizar la cuantificación existencial. En lugar de la expresión for anterior, podríamos haber escrito esto:

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

Además de la "some" sintaxis, XPath 2.0 también suministra una "every" sintaxis correspondiente para la realización universal de cuantificación.

En lugar de utilizar for-each, también se puede utilizar reglas de plantilla, que son más modular (y poderosa):

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

Una vez más, en este caso, estamos confiando en la cuantificación existencial de =.

XSLT 1.0 prohíbe el uso de la función current() en patrones, es decir, en el atributo match, pero XSLT 2.0 lo permite. En ese caso, current() se refiere al nodo que se está emparejando actualmente. Entonces en XSLT 2.0, también podría escribir esto (y sin tener que utilizar una expresión for):

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

Tenga en cuenta que este patrón es esencialmente la misma que la expresión que ha intentado usar en for-each, pero mientras que no hace lo usted quiere en for-each, hace haga lo que quiera en el patrón (porque lo que current() se une es diferente).

Finalmente, añadiré una variación más que de alguna manera simplifica la lógica (eliminando not()). Esto también va de nuevo a usar 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> 

Si no le gusta al ser un espacio en blanco de salida, agregar una regla de vacío para los nodos de texto, por lo que obtendrá quitó (anulando la regla por defecto para los nodos de texto , que es copiarlos):

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

O usted podría ser más selectivos en lo que los nodos se aplica a las plantillas:

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

qué enfoque se toma es parcialmente dependiente de sabor, parte d depende del contexto más amplio de su hoja de estilo y de los datos esperados (cuánto puede variar la estructura de entrada, etc.).

Sé que fui mucho más allá de lo que estaba pidiendo, pero espero que al menos haya encontrado esto interesante. :-)

Answer 2

Un tal expresión XPath 1.0 es:

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

A continuación, sólo ponerlo en una hoja de estilo XSLT como la:

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

Cuando se aplica esta hoja de estilo en el documento previsto originalmente en 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> 

El resultado deseado se produce:

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

Ten en cuenta: Una solución de el recorrido de gráficos completos (quizás cíclicos) está disponible en XSLThere.