Tìm đồ thị theo chu kỳ được chỉ định (DAG) Các thành phần tối thiểu (đỉnh) với XSLT/XPath?

Question

Tôi có tệp XML mã hóa directed acyclic graph (DAG) đại diện cho partial order. Các đồ thị như vậy rất hữu ích cho những thứ như chỉ định phụ thuộc và tìm kiếm critical paths. Đối với tò mò, ứng dụng hiện tại của tôi là để xác định phụ thuộc thành phần cho một build system, do đó, đỉnh là các thành phần và các cạnh xác định thời gian biên dịch phụ thuộc. Dưới đây là một ví dụ đơn giản:

<?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 Điều này có thể được rút ra như thế này:

http://iparelan.com/dag.png

Tôi muốn áp dụng một XSLTstylesheet sản xuất khác XML tài liệu có chứa chỉ các đỉnh tương ứng với minimal elements của đơn đặt hàng một phần. Đó là, những đỉnh không có cạnh tới. Tập hợp các đỉnh tối thiểu cho biểu đồ ví dụ là {A, B, F}. Đối với ứng dụng phụ thuộc xây dựng của tôi, việc tìm kiếm tập hợp này có giá trị bởi vì tôi biết rằng nếu tôi xây dựng các thành viên của tập hợp này, thì mọi thứ trong dự án của tôi sẽ được xây dựng.

Đây là giải pháp biểu định kiểu hiện tại của tôi (Tôi đang chạy với Xalan trên Java bằng cách sử dụng tác vụ xslt của Apache Ant). Một quan sát quan trọng là một đỉnh tối thiểu sẽ không được nhắc đến trong bất kỳ yếu tố 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> 

Áp dụng kiểu này xuất ra như sau (mà tôi tin là đúng):

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

Có điều là, Tôi không hoàn toàn hài lòng với giải pháp này. Tôi tự hỏi nếu có cách nào để kết hợp số select của số for-each và test của số if với cú pháp XPath.

Tôi muốn viết một cái gì đó như:

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

Nhưng điều đó không làm những gì tôi muốn vì current() chức năng không tham chiếu tới các nút bởi các //vertex biểu hiện bên ngoài được chọn.

Do đó, giải pháp của tôi sử dụng cú pháp XPath 1.0 và XSLT 1.0, mặc dù tôi cũng mở cho cú pháp XPath 2.0 và XSLT 2.0.

Dưới đây là xây dựng kịch bản Ant nếu bạn thích:

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

Mục tiêu dot tạo GraphvizDotlanguage mã cho render đồ thị.Dưới đây là 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

Bạn có thể tận dụng lượng hiện sinh ngầm XPath về các nhà điều hành =:

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

Khi bạn sử dụng bất kỳ trong số sáu nhà khai thác so sánh (=, !=, <, <=, > và >=) để so sánh tập hợp nút, biểu thức sẽ trả về true nếu bất kỳ nút nào trong tập hợp nút thỏa mãn điều kiện. Khi so sánh một bộ nút với một nút khác, biểu thức trả về true nếu bất kỳ nút nào trong bộ nút đầu tiên thỏa mãn điều kiện khi so sánh với bất kỳ nút nào trong bộ nút thứ hai. XPath 2.0 giới thiệu sáu toán tử mới không thực hiện định lượng hiện tại này (eq, ne, lt, le, gt và ge). Nhưng trong trường hợp của bạn, bạn sẽ muốn sử dụng "=" để có được định lượng tồn tại đó.

Lưu ý tất nhiên, bạn sẽ vẫn muốn sử dụng chức năng not() như bạn đang làm. Hầu hết thời gian, bạn nên tránh toán tử !=. Nếu bạn sử dụng nó ở đây thay vì not(), thì nó sẽ trả về true nếu có bất kỳ thuộc tính @vertex nào không bằng với giá trị @name, đó không phải là ý định của bạn. (Và nếu tập hợp nút trống, thì nó sẽ trả về false, vì so sánh với các bộ nút rỗng luôn trả về false.)

Nếu bạn muốn sử dụng eq thay vào đó, bạn phải làm điều gì đó giống như bạn đã làm: tách biệt điều kiện khỏi phép lặp để bạn có thể liên kết current(). Nhưng trong XPath 2.0, bạn có thể làm điều này trong một biểu thức:

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

này rất hữu ích cho khi tình trạng của bạn không phải là một sự so sánh bình đẳng đơn giản (và do đó không thể được existentially lượng sử dụng "="). Ví dụ: starts-with(@vertex, $v/@name).

XPath 2.0 cũng có cách rõ ràng để thực hiện định lượng hiện tại. Thay vì các biểu hiện for trên, chúng ta có thể viết này:

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

Ngoài cú pháp "some", XPath 2.0 cũng cung cấp một cú pháp tương ứng "every" để thực hiện phổ cập lượng.

Thay vì sử dụng for-each, bạn cũng có thể sử dụng quy tắc mẫu, đó là mô-đun hơn (và mạnh mẽ):

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

Một lần nữa, trong trường hợp này, chúng tôi đang dựa vào định lượng hiện sinh của =.

XSLT 1.0 cấm sử dụng chức năng current() trong các mẫu, tức là trong thuộc tính match, nhưng XSLT 2.0 cho phép nó. Trong trường hợp đó, current() là nút hiện đang được khớp. Vì vậy, trong XSLT 2.0, chúng ta cũng có thể viết những dòng này (mà không cần phải sử dụng một biểu for):

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

Lưu ý rằng mô hình này là cơ bản giống như các biểu hiện bạn đã cố gắng để sử dụng trong for-each, nhưng ngược lại nó không làm gì bạn muốn trong số for-each, nó làm làm những gì bạn muốn trong mẫu (vì những gì current() liên kết với khác nhau).

Cuối cùng, tôi sẽ thêm một biến thể khác theo một số cách đơn giản hóa logic (loại bỏ not()). Đây cũng quay ngược lại để sử dụng 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> 

Nếu bạn không thích những khoảng trắng đang được đầu ra, thêm một quy tắc trống cho các nút văn bản, do đó, họ sẽ nhận được tước ra (trọng quy tắc mặc định cho các nút văn bản , mà là để sao chép chúng):

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

Hoặc bạn chỉ có thể được chọn lọc hơn trong những gì các nút bạn áp dụng các mẫu để:

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

nào tiếp cận của chúng ta chứa một phần phụ thuộc vào hương vị, một phần d phụ thuộc vào ngữ cảnh rộng hơn của biểu định kiểu và dữ liệu dự kiến ​​của bạn (cấu trúc đầu vào có thể khác nhau bao nhiêu, v.v.).

Tôi biết tôi đã vượt xa những gì bạn đang yêu cầu, nhưng tôi hy vọng bạn ít nhất thấy điều này thú vị. :-)

Answer 2

Một trong những XPath 1.0 biểu thức là:

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

Sau đó chỉ cần đặt nó vào một kiểu XSLT như rằng:

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

Khi stylesheet này được áp dụng trên các tài liệu ban đầu-quy 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> 

Kết quả muốn được sản xuất:

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

Do lưu ý: Một giải pháp cho duyệt qua các biểu đồ đầy đủ (có thể tuần hoàn) có sẵn trong XSLThere.