ढूँढना निर्देशित अचक्रीय ग्राफ़ (DAG) मिनिमल तत्वों (कोने) XSLT/XPath के साथ?

Question

मैं एक XML फ़ाइल है कि एक directed acyclic graph (DAG) कि एक partial order का प्रतिनिधित्व करता है encodes की है। ऐसे ग्राफ निर्भरताओं को निर्दिष्ट करने और critical paths खोजने जैसी चीजों के लिए उपयोगी हैं। जिज्ञासु के लिए, मेरे वर्तमान आवेदन तो कोने घटकों और किनारों संकलन समय निर्भरता निर्दिष्ट कर रहे हैं, एक build system के लिए घटक निर्भरता निर्दिष्ट करने के लिए है। यहाँ एक सरल उदाहरण है:

<?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 इस तरह से तैयार किया जा सकता है:

http://iparelan.com/dag.png

मैं लागू करना चाहते हैं एक XSLTstylesheet है कि एक और एक्सएमएल दस्तावेज है कि केवल कोने में शामिल है का उत्पादन जो आंशिक क्रम के minimal elements के अनुरूप है। यही वह ऊर्ध्वाधर है जिसमें कोई आने वाली किनार नहीं है। उदाहरण ग्राफ के लिए न्यूनतम शोर का सेट {A, B, F} है। अपने निर्माण निर्भरता आवेदन के लिए, यह सेट खोजने मूल्यवान है क्योंकि मुझे पता है कि अगर मैं इस सेट के सदस्यों का निर्माण, तो अपने प्रोजेक्ट में सब कुछ का निर्माण किया जाएगा है।

यहां मेरा वर्तमान स्टाइलशीट समाधान है (मैं इसे अपाचे एंटी के xslt कार्य का उपयोग कर जावा पर ज़लान के साथ चला रहा हूं)। ,

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

बात है: एक प्रमुख अवलोकन है कि एक न्यूनतम शिखर किसी भी 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> 

इस स्टाइलशीट लागू करने निम्नलिखित निर्गम (जो मेरा मानना ​​है कि सही है) पैदा करता है मैं इस समाधान से पूरी तरह संतुष्ट नहीं हूं। मैं अगर वहाँ for-each की select और XPath वाक्य रचना के साथ if की test गठबंधन करने के लिए एक रास्ता है सोच रहा हूँ।

मैं की तरह कुछ लिखना चाहते हैं:

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

लेकिन है कि मैं क्या चाहते current() समारोह बाहरी //vertex अभिव्यक्ति द्वारा चयनित नोड्स को संदर्भित नहीं करती क्योंकि नहीं करता है।

thusfar, मेरे समाधान 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 लक्ष्य ग्राफ प्रतिपादन के लिए GraphvizDotlanguage कोड उत्पन्न करता है।यहाँ 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)]"> 

, >, और >=) एक नोड-सेट की तुलना करने, अभिव्यक्ति सच वापस आ जाएगी अगर नोड सेट को संतुष्ट करता है में किसी भी नोड हालत। दूसरे के साथ एक नोड सेट की तुलना करते समय, अभिव्यक्ति सच लौटाता है यदि प्रथम नोड सेट को संतुष्ट करता है में किसी भी नोड हालत जब दूसरी नोड सेट में किसी भी नोड के साथ तुलना में। XPath 2.0 छह नए ऑपरेटरों को प्रस्तुत करता है जो इस अस्तित्वत्मक मात्रा (eq, ne, lt, le, gt, और ge) नहीं करते हैं। लेकिन आपके मामले में, आप उस मौजूदा मात्रा को प्राप्त करने के लिए "=" का उपयोग करना चाहेंगे।

बेशक, ध्यान दें कि आप अभी भी not() फ़ंक्शन का उपयोग करना चाहते हैं जैसा आप कर रहे थे। अधिकांश समय, != ऑपरेटर से बचना अच्छा होता है। यदि आपने इसे not() के बजाय यहां उपयोग किया है, तो यह गुणों के बराबर नहीं है, जो @name मान के बराबर नहीं हैं, जो आपकी मंशा नहीं है। (और यदि नोड-सेट खाली है, तो यह झूठी वापसी करेगा, क्योंकि रिक्त नोड-सेट के साथ तुलना हमेशा झूठी होती है।)

यदि आप इसके बजाय eq का उपयोग करना चाहते हैं, तो आपको कुछ ऐसा करना होगा किया: पुनरावृत्ति से सशर्त को अलग करें ताकि आप current() बांध सकें। लेकिन XPath 2.0 में, आप एक अभिव्यक्ति के भीतर ऐसा कर सकते हैं:

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

यह जब अपनी हालत के लिए एक सरल समानता तुलना नहीं है के लिए उपयोगी है (और इस प्रकार existentially "=" का उपयोग मात्रा निर्धारित नहीं किया जा सकता)। उदाहरण के लिए: 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> 

फिर, इस मामले में, हम = के अस्तित्व मात्रा में निर्भर हैं।

एक्सएसएलटी 1.0 पैटर्न में current() फ़ंक्शन का उपयोग प्रतिबंधित करता है, यानी, match विशेषता में, लेकिन XSLT 2.0 इसे अनुमति देता है। उस स्थिति में, current() वर्तमान में मिलान किए जा रहे नोड को संदर्भित करता है। तो एक्सएसएलटी 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> 

ध्यान दें करो: के लिए एक समाधान XSLThere में पूर्ण (शायद चक्रीय) ग्राफ का ट्रैवर्सिंग उपलब्ध है।