إيجاد توجه احلقي الرسم البياني (DAG) الحد الأدنى من العناصر (القمم) مع XSLT/XPath?

Question

لدي ملف XML التي يشفر توجه احلقي الرسم البياني (DAG) الذي يمثل الأمر الجزئي.هذه الرسوم البيانية مفيدة في أشياء مثل تحديد تبعيات وإيجاد مسارات حرجة.غريبة, بلدي التطبيق الحالي هو تحديد العنصر تبعيات عن بناء نظام, لذا القمم هي مكونات حواف تحديد وقت التحويل البرمجي التبعيات.هنا مثال بسيط:

<?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 الأنماط التي تنتج آخر XML المستند الذي يحتوي فقط على القمم التي تتوافق مع الحد الأدنى من العناصر الجزئي النظام.تلك القمم التي لا واردة الحواف.مجموعة الحد الأدنى من القمم على سبيل المثال الرسم البياني {A, B, F}.أجل بناء التبعية تطبيق العثور على هذه المجموعة القيمة لأنني أعرف أنه إذا كنت بناء أعضاء هذه المجموعة ، ثم كل شيء في بلدي المشروع سيتم بناؤها.

هنا هو بلدي الحالي الأنماط الحل (أنا أدير هذا مع 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 بناء الجملة كذلك.

هنا النمل بناء السيناريو إذا كنت ترغب في:

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

Answer 1

يمكنك الاستفادة من XPath الضمني الوجودي الكمي على = المشغل:

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

عند استخدام أي من ستة عوامل تشغيل المقارنة (=, !=, <, <=, >, ، >=) مقارنة عقدة-تعيين التعبير سوف ترجع true إذا كان أي عقدة في عقدة مجموعة تستوفي الشرط.عند مقارنة عقدة واحدة-مع مجموعة أخرى ، التعبير ترجع صحيح إذا كان أي عقدة في العقدة الأولى-مجموعة تستوفي الشرط عند مقارنة مع أي عقدة في العقدة الثانية-مجموعة.XPath 2.0 يدخل ستة شركات جديدة أن لا تؤدي هذه الوجودي الكمي (eq, ne, lt, le, gt, ، ge).لكن في حالتك سوف تحتاج إلى استخدام "="للحصول على هذا الوجودية الكمي.

ملاحظة بالطبع هذا سوف لا تزال تريد استخدام not() وظيفة كما كنت تفعل.معظم الوقت, إنه جيد لتجنب != المشغل.إذا كنت تستخدم هنا بدلا من not(), ثم يعود صحيحا إذا كان هناك أي @vertex الصفات التي لا تساوي @name القيمة التي ليست نيتك.(و إذا أي عقدة مجموعة فارغة ، ثم فإنه return false, كما مقارنات مع فارغة عقدة مجموعات دائما return 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"/>

الذي تسلكه جزئيا تعتمد على الذوق جزئيا تعتمد على سياق أوسع من الأنماط الخاصة بك و البيانات المتوقعة (كم هيكل المدخلات قد تختلف ، إلخ.).

وأنا أعلم أنني ذهبت الى ابعد ما كنت طالبا ، لكن أتمنى على الأقل وجدت هذه مثيرة للاهتمام.:-)

Answer 2

واحدة من هذه 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 هنا.