साइक्लोमेटिक कम्पलेक्सिटी: Difference between revisions
No edit summary |
No edit summary |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 2: | Line 2: | ||
'''साइक्लोमैटिक कम्पलेक्सिटी''' एक [[सॉफ्टवेयर मीट्रिक]] है जिसका उपयोग [[प्रोग्रामिंग जटिलता|प्रोग्रामिंग कम्पलेक्सिटी]] को इंगित करने के लिए किया जाता है। यह प्रोग्राम के स्रोत कोड के माध्यम से रैखिक रूप से इंडिपेंडेंट पाथ्स की संख्या का एक मात्रात्मक माप है। इसे 1976 में थॉमस जे. मैककेबे, सीनियर द्वारा विकसित किया गया था। | '''साइक्लोमैटिक कम्पलेक्सिटी''' एक [[सॉफ्टवेयर मीट्रिक]] है जिसका उपयोग [[प्रोग्रामिंग जटिलता|प्रोग्रामिंग कम्पलेक्सिटी]] को इंगित करने के लिए किया जाता है। यह प्रोग्राम के स्रोत कोड के माध्यम से रैखिक रूप से इंडिपेंडेंट पाथ्स की संख्या का एक मात्रात्मक माप है। इसे 1976 में थॉमस जे. मैककेबे, सीनियर द्वारा विकसित किया गया था। | ||
साइक्लोमैटिक कम्पलेक्सिटी की कंप्यूटेड प्रोग्राम के [[नियंत्रण-प्रवाह ग्राफ|कंट्रोल-फ्लो ग्राफ]] का उपयोग करके की जाती है: ग्राफ़ (असतत गणित) के नोड्स एक प्रोग्राम के कमांड्स | साइक्लोमैटिक कम्पलेक्सिटी की कंप्यूटेड प्रोग्राम के [[नियंत्रण-प्रवाह ग्राफ|कंट्रोल-फ्लो ग्राफ]] का उपयोग करके की जाती है: ग्राफ़ (असतत गणित) के नोड्स एक प्रोग्राम के कमांड्स तथा इंडीविज़िबल समूहों के अनुरूप होते हैं, और एक [[निर्देशित ग्राफ|डायरेक्टेड ग्राफ]] एज दो नोड्स को जोड़ता है यदि दूसरे कमांड को पहले कमांड के पश्चात तेज़ी से निष्पादित किया जा सकता है। साइक्लोमैटिक कम्पलेक्सिटी को एक प्रोग्राम के समाविष्ट इंडिविजुअल [[फ़ंक्शन (कंप्यूटर विज्ञान)]], [[मॉड्यूलर प्रोग्रामिंग]], [[विधि (कंप्यूटर विज्ञान)|मेथड्स (कंप्यूटर विज्ञान)]] या क्लासेस (कंप्यूटर विज्ञान) पर भी लागू किया जा सकता है। | ||
एक [[सॉफ़्टवेयर परीक्षण|सॉफ़्टवेयर टैस्टिंग]] रणनीति, जिसे मैककेबे ने [[आधार पथ परीक्षण|बेसिस पाथ टैस्टिंग]] कहा है, जिन्होंने सबसे पहले इसे प्रस्तावित किया था, प्रोग्राम के माध्यम से प्रत्येक रैखिक रूप से इंडिपेंडेंट पाथ की टैस्टिंग करना है; इस | एक [[सॉफ़्टवेयर परीक्षण|सॉफ़्टवेयर टैस्टिंग]] रणनीति, जिसे मैककेबे ने [[आधार पथ परीक्षण|बेसिस पाथ टैस्टिंग]] कहा है, जिन्होंने सबसे पहले इसे प्रस्तावित किया था, प्रोग्राम के माध्यम से प्रत्येक रैखिक रूप से इंडिपेंडेंट पाथ की टैस्टिंग करना है; इस केस में, टैस्टिंग केसेस की संख्या प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी के समतुल्य होती है।<ref>{{cite web| | ||
url=http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/index.html| | url=http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/index.html| | ||
title=Basis Path Testing| | title=Basis Path Testing| | ||
Line 10: | Line 10: | ||
==विवरण== | ==विवरण== | ||
===परिभाषा=== | ===परिभाषा=== | ||
[[Image:control flow graph of function with loop and an if statement without loop back.svg|thumb|250px|right|एक साधारण प्रोग्राम का कंट्रोल-फ्लो ग्राफ़। प्रोग्राम लाल नोड पर निष्पादित होना शुरू होता है, फिर एक लूप में एंट्री करता है (लाल नोड के सही नीचे तीन नोड्स का समूह)। लूप से बाहर निकलने पर, एक कंडीशनल विवरण (लूप के नीचे समूह) होता है, और अंत में प्रोग्राम नीले नोड पर बाहर निकलता है। इस ग्राफ़ में 9 एज, 8 नोड्स और 1 [[जुड़ा हुआ घटक (ग्राफ़ सिद्धांत)]] है, इसलिए प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी है {{math|1=9 − 8 + 2×1 = 3}}.]]स्रोत कोड के एक अनुभाग की साईक्लोमैटिक कम्पलेक्सिटी इसके समाविष्ट [[रैखिक रूप से स्वतंत्र|रैखिक रूप से इंडिपेंडेंट]] [[पथ (ग्राफ सिद्धांत)|पाथ (ग्राफ सिद्धांत)]] की संख्या है - पाथ्स का एक | [[Image:control flow graph of function with loop and an if statement without loop back.svg|thumb|250px|right|एक साधारण प्रोग्राम का कंट्रोल-फ्लो ग्राफ़। प्रोग्राम लाल नोड पर निष्पादित होना शुरू होता है, फिर एक लूप में एंट्री करता है (लाल नोड के सही नीचे तीन नोड्स का समूह)। लूप से बाहर निकलने पर, एक कंडीशनल विवरण (लूप के नीचे समूह) होता है, और अंत में प्रोग्राम नीले नोड पर बाहर निकलता है। इस ग्राफ़ में 9 एज, 8 नोड्स और 1 [[जुड़ा हुआ घटक (ग्राफ़ सिद्धांत)|जुड़ा हुआ कम्पोनेंट (ग्राफ़ सिद्धांत)]] है, इसलिए प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी है {{math|1=9 − 8 + 2×1 = 3}}.]]स्रोत कोड के एक अनुभाग की साईक्लोमैटिक कम्पलेक्सिटी इसके समाविष्ट [[रैखिक रूप से स्वतंत्र|रैखिक रूप से इंडिपेंडेंट]] [[पथ (ग्राफ सिद्धांत)|पाथ (ग्राफ सिद्धांत)]] की संख्या है - पाथ्स का एक समुच्चय रैखिक रूप से निर्भर होता है यदि एक या अधिक पाथ्स का एक उपसमुच्चय होता है जहां उनके एज समुच्चय का [[सममित अंतर]] रिक्त होता है। उदाहरण के लिए, यदि स्रोत कोड में कोई कंट्रोल फ्लो (कंडीशनल या डिसीज़न पॉइंट) नहीं है, तो कम्पलेक्सिटी 1 होगी, क्योंकि कोड के माध्यम से केवल एक ही पाथ होता है। यदि कोड में एक एकल-केस IF स्टेटमेंट है, तो कोड के माध्यम से दो पाथ होंगे: एक जहां IF स्टेटमेंट TRUE का मूल्यांकन करता है और दूसरा जहां यह FALSE का मूल्यांकन करता है, इसलिए कम्पलेक्सिटी 2 होगी, दो नेस्टेड एकल-केस IF, या दो शर्तों वाला एक IF, 3 की कम्पलेक्सिटी उत्पन्न करता है। | ||
गणितीय रूप से, [[संरचित प्रोग्रामिंग|स्ट्रक्चर्ड प्रोग्रामिंग]] की साईक्लोमैटिक कम्पलेक्सिटी{{efn|1=Here "structured" means in particular "with a single exit ([[return statement]]) per function".}} के प्रोग्राम को कंट्रोल-फ्लो ग्राफ के संदर्भ में परिभाषित किया गया है, एक डायरेक्टेड ग्राफ जिसमें प्रोग्राम के [[बुनियादी ब्लॉक|बेसिक ब्लॉक]] होते हैं, दो बेसिक ब्लॉकों के बीच एक एज के साथ यदि कंट्रोल पहले से दूसरे तक जा सकता है। कम्पलेक्सिटी {{mvar|M}} को इसलिए परिभाषित किया गया है:<ref name="mccabe76">{{cite journal| last=McCabe|date=December 1976| journal=IEEE Transactions on Software Engineering|issue=4| pages=308–320| title=एक जटिलता उपाय| volume=SE-2| doi=10.1109/tse.1976.233837|s2cid=9116234}}</ref><math display="block">M = E - N + 2P,</math>जहाँ | गणितीय रूप से, [[संरचित प्रोग्रामिंग|स्ट्रक्चर्ड प्रोग्रामिंग]] की साईक्लोमैटिक कम्पलेक्सिटी{{efn|1=Here "structured" means in particular "with a single exit ([[return statement]]) per function".}} के प्रोग्राम को कंट्रोल-फ्लो ग्राफ के संदर्भ में परिभाषित किया गया है, एक डायरेक्टेड ग्राफ जिसमें प्रोग्राम के [[बुनियादी ब्लॉक|बेसिक ब्लॉक]] होते हैं, दो बेसिक ब्लॉकों के बीच एक एज के साथ यदि कंट्रोल पहले से दूसरे तक जा सकता है। तो कम्पलेक्सिटी {{mvar|M}} को इसलिए परिभाषित किया गया है:<ref name="mccabe76">{{cite journal| last=McCabe|date=December 1976| journal=IEEE Transactions on Software Engineering|issue=4| pages=308–320| title=एक जटिलता उपाय| volume=SE-2| doi=10.1109/tse.1976.233837|s2cid=9116234}}</ref><math display="block">M = E - N + 2P,</math>जहाँ | ||
*{{mvar|E}} = ग्राफ़ के एजेस की संख्या | *{{mvar|E}} = ग्राफ़ के एजेस की संख्या | ||
*{{mvar|N}} = ग्राफ़ के नोड्स की संख्या | *{{mvar|N}} = ग्राफ़ के नोड्स की संख्या | ||
*{{mvar|P}} = कनेक्टेड कम्पोनेंट्स की संख्या (ग्राफ़ सिद्धांत) | *{{mvar|P}} = कनेक्टेड कम्पोनेंट्स की संख्या (ग्राफ़ सिद्धांत) | ||
[[Image:control flow graph of function with loop and an if statement.svg|thumb|250px|ऊपर जैसा ही कार्य, वैकल्पिक फॉर्मूलेशन का उपयोग करके दर्शाया गया है, जहां प्रत्येक एग्जिट पॉइंट दोबारा एंट्री पॉइंट से जुड़ा हुआ है। इस ग्राफ़ में 10 एज, 8 नोड्स और 1 जुड़ा हुआ | [[Image:control flow graph of function with loop and an if statement.svg|thumb|250px|ऊपर जैसा ही कार्य, वैकल्पिक फॉर्मूलेशन का उपयोग करके दर्शाया गया है, जहां प्रत्येक एग्जिट पॉइंट दोबारा एंट्री पॉइंट से जुड़ा हुआ है। इस ग्राफ़ में 10 एज, 8 नोड्स और 1 जुड़ा हुआ कम्पोनेंट (ग्राफ़ सिद्धांत) है, जिसके परिणामस्वरूप वैकल्पिक फॉर्मूलेशन का उपयोग करके 3 की साइक्लोमैटिक कम्पलेक्सिटी भी उत्पन्न होती है ({{math|1=10 − 8 + 1 = 3}}).]] एक वैकल्पिक सूत्रीकरण एक ग्राफ़ का उपयोग करना है जिसमें प्रत्येक एग्जिट पॉइंट दोबारा एंट्री पॉइंट से जुड़ा होता है। इस केस में, ग्राफस्ट्रॉन्ग्ली कनेक्टेड होता है, और प्रोग्राम की साइक्लोमैटिक कम्पलेक्सिटी इसके ग्राफ की [[चक्रीय संख्या|साईक्लोमैटिक संख्या]] के समतुल्य है (जिसे ग्राफ सिद्धांत में पहली बेट्टी संख्या), जिसे इस प्रकार परिभाषित किया गया है<ref name="mccabe76" /><math display="block">M = E - N + P.</math>इसे ग्राफ़ में उपस्थित [[रैखिक रूप से स्वतंत्र चक्र|रैखिक रूप से इंडिपेंडेंट]] [[साइकल्स]] की संख्या की कंप्यूटेड रूप में देखा जा सकता है, अर्थात वे साइकल्स जिनके समाविष्ट अन्य साइकल्स सम्मिलित नहीं हैं। ध्यान दें कि क्योंकि प्रत्येक एग्जिट पॉइंट एंट्री पॉइंट पर दोबारा लूप करता है, प्रत्येक एग्जिट पॉइंट के लिए कम से कम एक ऐसी साईकल जरूर होती है। | ||
एकल प्रोग्राम (या सबरूटीन या मेथड्स) के लिए, {{mvar|P}} | एकल प्रोग्राम (या सबरूटीन या मेथड्स) के लिए, {{mvar|P}} निरंतर 1 के समतुल्य होता है। इसलिए एकल सबरूटीन के लिए एक सरल सूत्र है,<ref name="Laplante2007">{{cite book|author=Philip A. Laplante|title=सॉफ्टवेयर इंजीनियरिंग के बारे में प्रत्येक इंजीनियर को क्या पता होना चाहिए|date=25 April 2007|publisher=CRC Press|isbn=978-1-4200-0674-2|page=176}}</ref><math display="block">M = E - N + 2.</math> | ||
चूँकि, साइक्लोमैटिक कम्पलेक्सिटी को एक ही समय में ऐसे कई प्रोग्रामों या सबप्रोग्रामों पर लागू किया जा सकता है (उदाहरण के लिए, एक क्लासेस के सभी विधियों पर), और इन | चूँकि, साइक्लोमैटिक कम्पलेक्सिटी को एक ही समय में ऐसे कई प्रोग्रामों या सबप्रोग्रामों पर लागू किया जा सकता है (उदाहरण के लिए, एक क्लासेस के सभी विधियों पर), और इन केसेस में {{mvar|P}} विचाराधीन प्रोग्रामों की संख्या के समतुल्य होगा, क्योंकि प्रत्येक सबप्रोग्राम ग्राफ़ के डिस्कनेक्ट किए गए उपसमुच्चय के रूप में दिखाई देता है। | ||
मैककेबे ने दिखाया कि केवल एक एंट्री पॉइंट और एक एग्जिट पॉइंट के साथ किसी भी स्ट्रक्चर्ड प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी उस प्रोग्राम में निहित डिसीज़न पॉइंटओं (अर्थात, यदि | मैककेबे ने दिखाया कि केवल एक एंट्री पॉइंट और एक एग्जिट पॉइंट के साथ किसी भी स्ट्रक्चर्ड प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी उस प्रोग्राम में निहित डिसीज़न पॉइंटओं (अर्थात, यदि स्टेटमेंट या कंडीशनल लूप) की संख्या प्लस एक के समतुल्य है। चूँकि, यह केवल निम्नतम, मशीन-स्तर के निर्देशों पर गिने जाने वाले डिसीज़न पॉइंटओं के लिए ट्रू है।<ref>{{cite web| | ||
url=https://www.froglogic.com/blog/tip-of-the-week/what-is-cyclomatic-complexity/| title=What exactly is cyclomatic complexity?|quote=To compute a graph representation of code, we can simply disassemble its assembly code and create a graph following the rules: ... |first=Sébastien|last=Fricker|date=April 2018|website=froglogic GmbH|access-date=October 27, 2018}}</ref> यौगिक विधेय से जुड़े डिसीज़न जैसे उच्च-स्तरीय लैंगुएजेस में पाए जाते हैं <code>IF cond1 AND cond2 THEN ...</code> सम्मिलित विधेय चर के संदर्भ में गिना जाना चाहिए, अर्थात इस उदाहरण में किसी को दो डिसीज़न पॉइंट गिनने चाहिए, क्योंकि <code>IF cond1 THEN IF cond2 THEN ...</code> मशीन स्तर पर यह समतुल्य है।<ref name="mccabe76" /><ref name="ecst">{{cite book| | url=https://www.froglogic.com/blog/tip-of-the-week/what-is-cyclomatic-complexity/| title=What exactly is cyclomatic complexity?|quote=To compute a graph representation of code, we can simply disassemble its assembly code and create a graph following the rules: ... |first=Sébastien|last=Fricker|date=April 2018|website=froglogic GmbH|access-date=October 27, 2018}}</ref> यौगिक विधेय से जुड़े डिसीज़न जैसे उच्च-स्तरीय लैंगुएजेस में पाए जाते हैं <code>IF cond1 AND cond2 THEN ...</code> सम्मिलित विधेय चर के संदर्भ में गिना जाना चाहिए, अर्थात इस उदाहरण में किसी को दो डिसीज़न पॉइंट गिनने चाहिए, क्योंकि <code>IF cond1 THEN IF cond2 THEN ...</code> मशीन स्तर पर यह समतुल्य है।<ref name="mccabe76" /><ref name="ecst">{{cite book| | ||
title=Encyclopedia of Computer Science and Technology| | title=Encyclopedia of Computer Science and Technology| | ||
Line 29: | Line 29: | ||
pages=367–368}}</ref> | pages=367–368}}</ref> | ||
साइक्लोमैटिक कम्पलेक्सिटी को कई एग्जिट पॉइंटओं वाले प्रोग्राम तक बढ़ाया जा सकता है; इस | साइक्लोमैटिक कम्पलेक्सिटी को कई एग्जिट पॉइंटओं वाले प्रोग्राम तक बढ़ाया जा सकता है; इस केस में यह समतुल्य है<math display="block">\pi - s + 2,</math>जहाँ <math>\pi</math> प्रोग्राम में डिसीज़न पॉइंटओं की संख्या है, और {{mvar|s}} एग्जिट पॉइंटओं की संख्या है।<ref name="ecst" /><ref name="harrison">{{cite journal | journal=Software: Practice and Experience | title=मैकाबे की जटिलता माप को बहु-निकास कार्यक्रमों पर लागू करना| author=Harrison | date=October 1984 | doi=10.1002/spe.4380141009 | volume=14 | issue=10 | pages=1004–1007 | s2cid=62422337}}</ref> | ||
===बीजगणितीय टोपोलॉजी के संदर्भ में स्पष्टीकरण=== | ===बीजगणितीय टोपोलॉजी के संदर्भ में स्पष्टीकरण=== | ||
ग्राफ़ का एक सम | ग्राफ़ का एक सम उपसमुच्चय (जिसे [[यूलेरियन पथ|यूलेरियन पाथ]] के रूप में भी जाना जाता है) वह है जहां प्रत्येक शीर्ष (ग्राफ़ सिद्धांत) एजेस की सम संख्या के साथ घटना है; ऐसे उपसमुच्चय साइकल्स और पृथक शीर्षों के संघ हैं। निम्नलिखित में, सम सबग्राफ को उनके एज समुच्चय के साथ पहचाना जाएगा, जो केवल उन सम सबग्राफ पर विचार करने के समतुल्य है जिसमें पूर्ण ग्राफ के सभी शीर्ष सम्मिलित हैं। | ||
ग्राफ के सभी सम उपग्राफों का | ग्राफ के सभी सम उपग्राफों का समुच्चय सममित अंतर के तहत बंद है, और इस प्रकार इसे जीएफ (2) पर एक वेक्टर समष्टि के रूप में देखा जा सकता है; इस सदिश समष्टि को ग्राफ़ का साइकल्स समष्टि कहा जाता है। ग्राफ़ की साईक्लोमैटिक संख्या को इस समष्टि के आयाम के रूप में परिभाषित किया गया है। चूँकि [[GF(2)|जीएफ(2)]] में दो तत्व हैं और साइकल्स समष्टि एसेंशियल रूप से परिमित है, साइकल्स संख्या भी साइकल्स समष्टि में तत्वों की संख्या के 2-लघुगणक के समतुल्य है। | ||
साइकल्स समष्टि के लिए एक आधार सरलता से ग्राफ सिद्धांत के ट्री की लाइब्रेरी को सही करके बनाया जा सकता है, और फिर फॉरेस्ट में नहीं एक एज से बने साइकल्स और उस एज के अंतिम पॉइंटओं को जोड़ने वाले फॉरेस्ट में पाथ पर विचार किया जा सकता है; ये साइकल्स साइकल्स समष्टि के लिए आधार बनाते हैं। इसलिए, साइक्लोमैटिक संख्या ग्राफ़ के अधिकतम फैले हुए फॉरेस्ट में नहीं एजेस की संख्या के समतुल्य होती है। चूँकि ग्राफ़ के अधिकतम फैले हुए फॉरेस्ट में एजेस की संख्या शीर्षों की संख्या घटा | साइकल्स समष्टि के लिए एक आधार सरलता से ग्राफ सिद्धांत के ट्री की लाइब्रेरी को सही करके बनाया जा सकता है, और फिर फॉरेस्ट में नहीं एक एज से बने साइकल्स और उस एज के अंतिम पॉइंटओं को जोड़ने वाले फॉरेस्ट में पाथ पर विचार किया जा सकता है; ये साइकल्स साइकल्स समष्टि के लिए आधार बनाते हैं। इसलिए, साइक्लोमैटिक संख्या ग्राफ़ के अधिकतम फैले हुए फॉरेस्ट में नहीं एजेस की संख्या के समतुल्य होती है। चूँकि ग्राफ़ के अधिकतम फैले हुए फॉरेस्ट में एजेस की संख्या शीर्षों की संख्या घटा कम्पोनेंट्स की संख्या के समतुल्य होती है, सूत्र <math>E-N+P</math> साईक्लोमैटिक संख्या के लिए ऊपर इस प्रकार है।<ref>{{cite book | ||
|last=Diestel | |last=Diestel | ||
|first=Reinhard | |first=Reinhard | ||
Line 48: | Line 48: | ||
}}</ref> | }}</ref> | ||
अधिक टोपोलॉजिकली इंक्लाइनड के लिए, साइक्लोमैटिक कम्पलेक्सिटी को वैकल्पिक रूप से एक सापेक्ष बेट्टी संख्या, एक सापेक्ष होमोलॉजी समूह के | अधिक टोपोलॉजिकली इंक्लाइनड के लिए, साइक्लोमैटिक कम्पलेक्सिटी को वैकल्पिक रूप से एक सापेक्ष बेट्टी संख्या, एक सापेक्ष होमोलॉजी समूह के साइज़ के रूप में परिभाषित किया जा सकता है: | ||
<math display="block">M := b_1(G,t) := \operatorname{rank}H_1(G,t),</math> | <math display="block">M := b_1(G,t) := \operatorname{rank}H_1(G,t),</math> | ||
जिसे टर्मिनल नोड्स टी के सापेक्ष ग्राफ़ जी के पहले होमोलॉजी समूह की रैंक के रूप में पढ़ा जाता है। यह एक एंट्री से एग्जिट तक फ्लो ग्राफ के माध्यम से रैखिक रूप से इंडिपेंडेंट पाथ्स की संख्या कहने का एक तकनीकी विधि है, जहां: | जिसे टर्मिनल नोड्स टी के सापेक्ष ग्राफ़ जी के पहले होमोलॉजी समूह की रैंक के रूप में पढ़ा जाता है। यह एक एंट्री से एग्जिट तक फ्लो ग्राफ के माध्यम से रैखिक रूप से इंडिपेंडेंट पाथ्स की संख्या कहने का एक तकनीकी विधि है, जहां: | ||
Line 57: | Line 57: | ||
यह साईक्लोमैटिक कम्पलेक्सिटी की सहज धारणा से मेल खाता है, और ऊपर बताए अनुसार कंप्यूटेड की जा सकती है। | यह साईक्लोमैटिक कम्पलेक्सिटी की सहज धारणा से मेल खाता है, और ऊपर बताए अनुसार कंप्यूटेड की जा सकती है। | ||
वैकल्पिक रूप से, कोई किसी दिए गए | वैकल्पिक रूप से, कोई किसी दिए गए कम्पोनेंट पर सभी टर्मिनल नोड्स की पहचान करके (एक साथ चिपकाकर) पूर्ण बेट्टी संख्या (पूर्ण समरूपता - सापेक्ष नहीं) के माध्यम से इसकी कंप्यूटेड कर सकता है (या समकक्ष, एंट्री द्वार से एग्जिट को जोड़ने वाले पाथ बनाएं), जिस केस में (नए, संवर्धित ग्राफ को कॉल करना) <math>\tilde G</math>, जो है ), एक प्राप्त होता है | ||
<math display="block">M = b_1(\tilde G) = \operatorname{rank}H_1(\tilde G).</math> | <math display="block">M = b_1(\tilde G) = \operatorname{rank}H_1(\tilde G).</math> | ||
इसकी कंप्यूटेड [[होमोटॉपी]] के माध्यम से भी की जा सकती है। यदि कोई (जुड़े हुए) कंट्रोल-फ्लो ग्राफ को 1-आयामी [[सीडब्ल्यू कॉम्प्लेक्स]] मानता है, तो इसे कहा जाता है <math>X</math>, फिर का [[मौलिक समूह]] <math>X</math> होगा <math>\pi_1(X) \cong \Z^{*n}</math> | इसकी कंप्यूटेड [[होमोटॉपी]] के माध्यम से भी की जा सकती है। यदि कोई (जुड़े हुए) कंट्रोल-फ्लो ग्राफ को 1-आयामी [[सीडब्ल्यू कॉम्प्लेक्स]] मानता है, तो इसे कहा जाता है <math>X</math>, फिर का [[मौलिक समूह]] <math>X</math> होगा <math>\pi_1(X) \cong \Z^{*n}</math> का मान है <math>n+1</math> साईक्लोमैटिक कम्पलेक्सिटी है. मौलिक समूह कंप्यूटेड करता है कि होमोटॉपी तक ग्राफ़ के माध्यम से कितने लूप हैं, और इसलिए हम सहज रूप से जो अपेक्षा करते हैं उसके साथ संरेखित होता है। | ||
यह लूप की संख्या और | यह लूप की संख्या और कम्पोनेंट्स की संख्या के रूप में साइक्लोमैटिक कम्पलेक्सिटी के लक्षण वर्णन से मेल खाता है। | ||
=== व्याख्या === | === व्याख्या === | ||
अपनी प्रस्तुति में 'जोखिम की पहचान करने के लिए सॉफ्टवेयर गुणवत्ता मेट्रिक्स'<ref>{{cite web |url=http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |title=जोखिम की पहचान करने के लिए सॉफ़्टवेयर गुणवत्ता मेट्रिक्स|author=Thomas McCabe Jr. |year=2008 |archive-url=https://web.archive.org/web/20220329072759/http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |archive-date=2022-03-29 |url-status=live}}</ref> होमलैंड सिक्योरिटी विभाग के लिए, टॉम मैककेबे ने साईक्लोमैटिक कम्पलेक्सिटी की व्याख्या करने के लिए निम्नलिखित क्लासेसीकरण प्रस्तुत किया है: | अपनी प्रस्तुति में 'जोखिम की पहचान करने के लिए सॉफ्टवेयर गुणवत्ता मेट्रिक्स'<ref>{{cite web |url=http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |title=जोखिम की पहचान करने के लिए सॉफ़्टवेयर गुणवत्ता मेट्रिक्स|author=Thomas McCabe Jr. |year=2008 |archive-url=https://web.archive.org/web/20220329072759/http://www.mccabe.com/ppt/SoftwareQualityMetricsToIdentifyRisk.ppt |archive-date=2022-03-29 |url-status=live}}</ref> होमलैंड सिक्योरिटी विभाग के लिए, टॉम मैककेबे ने साईक्लोमैटिक कम्पलेक्सिटी की व्याख्या करने के लिए निम्नलिखित क्लासेसीकरण प्रस्तुत किया है: | ||
*1-10 | *1-10 सिंपल प्रोसीजर, लिटिल रिस्क | ||
*11-20 | *11-20 मोर काम्प्लेक्स, मॉडरेट रिस्क | ||
* 21 - 50 | * 21 - 50 काम्प्लेक्स, हाई रिस्क | ||
* > 50 | * > 50 अन्टेस्टेबल कोड, वैरी हाई रिस्क | ||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
=== | ===डेवलपमेंट के समय कम्पलेक्सिटी को सीमित करना=== | ||
मैककेबे के मूल अनुप्रयोगों में से एक प्रोग्राम | मैककेबे के मूल अनुप्रयोगों में से एक प्रोग्राम डेवलपमेंट के समय दिनचर्या की कम्पलेक्सिटी को सीमित करना था; उन्होंने सुझाव दिया कि प्रोग्रामर्स को अपने द्वारा विकसित किए जा रहे मॉड्यूल की कम्पलेक्सिटी की कंप्यूटेड करनी चाहिए, और जब भी मॉड्यूल की साइक्लोमैटिक कम्पलेक्सिटी 10 से अधिक हो तो उन्हें छोटे मॉड्यूल में विभाजित करना चाहिए,<ref name="mccabe76" /> इस अभ्यास को [[एनआईएसटी]] स्ट्रक्चर्ड टैस्टिंग पद्धति द्वारा अपनाया गया था, इस अवलोकन के साथ कि मैककेबे के मूल प्रकाशन के पश्चात से, 10 के आंकड़े को पर्याप्त पुष्ट साक्ष्य प्राप्त हुए थे, लेकिन कुछ परिकेसेस में प्रतिबंध में छोड़ देना और 15 तक की कम्पलेक्सिटी वाले मॉड्यूल को अनुमति देना उचित हो सकता है। चूंकि पद्धति ने स्वीकार किया कि सहमति-सीमा से परे जाने के लिए कभी-कभी कारण थे, इसने अपनी सिफारिश को प्रत्येक मॉड्यूल के लिए, या तो साइक्लोमैटिक कम्पलेक्सिटी को [सहमत-सीमा] तक सीमित कर दिया या एक प्रदान किया गया है। सीमा क्यों पार की गई इसका लिखित स्पष्टीकरण भी सम्मिलित होता है।<ref name="nist">{{cite web| | ||
url=http://www.mccabe.com/pdf/mccabe-nist235r.pdf| title=Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric|author1=Arthur H. Watson |author2=Thomas J. McCabe | year=1996|publisher=NIST Special Publication 500-235}}</ref> | url=http://www.mccabe.com/pdf/mccabe-nist235r.pdf| title=Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric|author1=Arthur H. Watson |author2=Thomas J. McCabe | year=1996|publisher=NIST Special Publication 500-235}}</ref> | ||
===किसी प्रोग्राम की संरचना को मापना=== | ===किसी प्रोग्राम की संरचना को मापना=== | ||
Line 81: | Line 81: | ||
मैककेबे के 1976 के पेपर का खंड VI यह निर्धारित करने से संबंधित है कि नॉन-स्ट्रक्चर्ड प्रोग्रामिंग के कंट्रोल-फ्लो ग्राफ़ (सीएफजी) उनके सबग्राफ के संदर्भ में कैसा दिखते हैं, जिसे मैककेबे पहचानते हैं। (उस भाग के विवरण के लिए [[संरचित कार्यक्रम प्रमेय|स्ट्रक्चर्ड प्रोग्राम प्रमेय]] देखें।) मैककेबे ने उस खंड को एक संख्यात्मक माप का प्रस्ताव देकर समाप्त किया है कि कोई दिया गया प्रोग्राम स्ट्रक्चर्ड प्रोग्रामिंग आदर्श के कितना निकट है, अर्थात मैककेबे के नवशास्त्रवाद का उपयोग करके इसकी स्ट्रक्चर्डता मैककेबे ने इस उद्देश्य के लिए जो माप तैयार किया, उसे एसेंशियल कम्पलेक्सिटी (स्ट्रक्चर्डता का संख्यात्मक माप) कहा जाता है।<ref name="mccabe76" /> | मैककेबे के 1976 के पेपर का खंड VI यह निर्धारित करने से संबंधित है कि नॉन-स्ट्रक्चर्ड प्रोग्रामिंग के कंट्रोल-फ्लो ग्राफ़ (सीएफजी) उनके सबग्राफ के संदर्भ में कैसा दिखते हैं, जिसे मैककेबे पहचानते हैं। (उस भाग के विवरण के लिए [[संरचित कार्यक्रम प्रमेय|स्ट्रक्चर्ड प्रोग्राम प्रमेय]] देखें।) मैककेबे ने उस खंड को एक संख्यात्मक माप का प्रस्ताव देकर समाप्त किया है कि कोई दिया गया प्रोग्राम स्ट्रक्चर्ड प्रोग्रामिंग आदर्श के कितना निकट है, अर्थात मैककेबे के नवशास्त्रवाद का उपयोग करके इसकी स्ट्रक्चर्डता मैककेबे ने इस उद्देश्य के लिए जो माप तैयार किया, उसे एसेंशियल कम्पलेक्सिटी (स्ट्रक्चर्डता का संख्यात्मक माप) कहा जाता है।<ref name="mccabe76" /> | ||
इस माप की कंप्यूटेड करने के लिए, मूल सीएफजी को एकल-प्रविष्टि और एकल-एग्जिट पॉइंट वाले सबग्राफ की पहचान करके पुनरावृत्त रूप से कम किया जाता है, जिन्हें फिर एक नोड द्वारा प्रतिस्थापित किया जाता है। यह कटौती इस बात से मेल खाती है कि यदि कोई इंसान कोड के बड़े हिस्से से एक सबरूटीन निकालता है तो वह क्या करेगा, (आजकल ऐसी प्रक्रिया [[पुनर्रचना]] के | इस माप की कंप्यूटेड करने के लिए, मूल सीएफजी को एकल-प्रविष्टि और एकल-एग्जिट पॉइंट वाले सबग्राफ की पहचान करके पुनरावृत्त रूप से कम किया जाता है, जिन्हें फिर एक नोड द्वारा प्रतिस्थापित किया जाता है। यह कटौती इस बात से मेल खाती है कि यदि कोई इंसान कोड के बड़े हिस्से से एक सबरूटीन निकालता है तो वह क्या करेगा, (आजकल ऐसी प्रक्रिया [[पुनर्रचना|रिफेक्टरिंग]] के अम्ब्रेला शब्द के अंतर्गत आती है।) मैककेबे की कटौती मेथड्स को पश्चात में कुछ पाठ्यपुस्तकों में संक्षेपण कहा गया, क्योंकि इसे संक्षेपण (ग्राफ सिद्धांत) के सामान्यीकरण के रूप में देखा गया था।<ref>{{cite book|author=Paul C. Jorgensen|title=Software Testing: A Craftsman's Approach, Second Edition|url=https://books.google.com/books?id=Yph_AwAAQBAJ&pg=PA150|year=2002|publisher=CRC Press|isbn=978-0-8493-0809-3|pages=150–153|edition=2nd}}</ref> यदि कोई प्रोग्राम स्ट्रक्चर्ड है, तो मैककेबे की कमी/संक्षेपण प्रक्रिया इसे एकल सीएफजी नोड में कम कर देती है। इसके विपरीत, यदि प्रोग्राम स्ट्रक्चर्ड नहीं है, तो पुनरावृत्त प्रक्रिया अपरिवर्तनीय भाग की पहचान करेगी। मैककेबे द्वारा परिभाषित एसेंशियल कम्पलेक्सिटी माप केवल इस अपरिवर्तनीय ग्राफ की साईक्लोमैटिक कम्पलेक्सिटी है, इसलिए यह सभी स्ट्रक्चर्ड प्रोग्रामों के लिए सटीक रूप से 1 होगा, लेकिन नॉन-स्ट्रक्चर्ड प्रोग्रामों के लिए एक से अधिक होता है।<ref name="nist"/>{{rp|80}} | ||
===सॉफ़्टवेयर टैस्टिंग के लिए | ===सॉफ़्टवेयर टैस्टिंग के लिए इम्प्लीकेशन=== | ||
साइक्लोमैटिक कम्पलेक्सिटी का एक अन्य अनुप्रयोग उन टैस्टिंग | साइक्लोमैटिक कम्पलेक्सिटी का एक अन्य अनुप्रयोग उन टैस्टिंग केसेस की संख्या निर्धारित करना है जो किसी विशेष मॉड्यूल के संपूर्ण टैस्टिंग कवरेज को प्राप्त करने के लिए एसेंशियल हैं। | ||
यह साईक्लोमैटिक कम्पलेक्सिटी के दो गुणों के कारण उपयोगी है, {{mvar|M}}, एक विशिष्ट मॉड्यूल के लिए: | यह साईक्लोमैटिक कम्पलेक्सिटी के दो गुणों के कारण उपयोगी है, {{mvar|M}}, एक विशिष्ट मॉड्यूल के लिए: | ||
* {{mvar|M}} पूर्ण [[शाखा कवरेज|ब्रांच कवरेज]] प्राप्त करने के लिए एसेंशियल टैस्टिंग | * {{mvar|M}} पूर्ण [[शाखा कवरेज|ब्रांच कवरेज]] प्राप्त करने के लिए एसेंशियल टैस्टिंग केसेस की संख्या के लिए ऊपरी सीमा है। | ||
* {{mvar|M}} कंट्रोल-फ्लो ग्राफ़ (सीएफजी) के माध्यम से पाथ्स की संख्या के लिए निचली सीमा है। यह मानते हुए कि प्रत्येक टैस्टिंग विधि एक पाथ लेती है, [[पथ कवरेज|पाथ कवरेज]] प्राप्त करने के लिए एसेंशियल | * {{mvar|M}} कंट्रोल-फ्लो ग्राफ़ (सीएफजी) के माध्यम से पाथ्स की संख्या के लिए निचली सीमा है। यह मानते हुए कि प्रत्येक टैस्टिंग विधि एक पाथ लेती है, [[पथ कवरेज|पाथ कवरेज]] प्राप्त करने के लिए एसेंशियल केसेस की संख्या उन पाथ्स की संख्या के समतुल्य होती है जिन्हें वास्तव में लिया जा सकता है। लेकिन कुछ पाथ असंभव हो सकते हैं, इसलिए चूंकि सीएफजी के माध्यम से पाथ्स की संख्या स्पष्ट रूप से पाथ कवरेज के लिए एसेंशियल टैस्टिंग केसेस की संख्या पर ऊपरी सीमा है, यह पश्चात वाली संख्या (पॉसिबल पाथ्स की) कभी-कभी कम होती है {{mvar|M}}. | ||
उपरोक्त तीनों संख्याएँ समान हो सकती हैं: ब्रांच कवरेज <math>\leq</math> साइक्लोमेटिक कम्पलेक्सिटी <math>\leq</math> पाथ्स की संख्या | उपरोक्त तीनों संख्याएँ समान हो सकती हैं: ब्रांच कवरेज <math>\leq</math> साइक्लोमेटिक कम्पलेक्सिटी <math>\leq</math> पाथ्स की संख्या | ||
उदाहरण के लिए, एक प्रोग्राम पर विचार करें जिसमें दो अनुक्रमिक यदि-तब-अन्यथा | उदाहरण के लिए, एक प्रोग्राम पर विचार करें जिसमें दो अनुक्रमिक यदि-तब-अन्यथा स्टेटमेंट सम्मिलित हैं। | ||
<syntaxhighlight lang="c"> | <syntaxhighlight lang="c"> | ||
Line 105: | Line 105: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
[[File:Control flow graph of function with two if else statements.svg|thumb|250px|right|उपरोक्त स्रोत कोड का कंट्रोल-फ्लो ग्राफ़; लाल वृत्त फ़ंक्शन का एंट्री पॉइंट है, और नीला वृत्त एग्जिट पॉइंट है। ग्राफ़ को मजबूती से कनेक्ट करने के लिए एग्जिट को एंट्री से जोड़ा गया है।]]इस उदाहरण में, पूर्ण ब्रांच कवरेज प्राप्त करने के लिए दो टैस्टिंग | [[File:Control flow graph of function with two if else statements.svg|thumb|250px|right|उपरोक्त स्रोत कोड का कंट्रोल-फ्लो ग्राफ़; लाल वृत्त फ़ंक्शन का एंट्री पॉइंट है, और नीला वृत्त एग्जिट पॉइंट है। ग्राफ़ को मजबूती से कनेक्ट करने के लिए एग्जिट को एंट्री से जोड़ा गया है।]]इस उदाहरण में, पूर्ण ब्रांच कवरेज प्राप्त करने के लिए दो टैस्टिंग केस पर्याप्त हैं, जबकि पूर्ण पाथ कवरेज के लिए चार एसेंशियल हैं। प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी 3 है (क्योंकि प्रोग्राम के लिए स्ट्रॉन्गली कनेक्टेड ग्राफ में 9 एज, 7 नोड्स और 1 जुड़ा कम्पोनेंट ({{math|9 − 7 + 1}}) सम्मिलित है)। | ||
समान्यता, किसी मॉड्यूल का | समान्यता, किसी मॉड्यूल का पूरे प्रकार से टैस्टिंग करने के लिए, मॉड्यूल के माध्यम से सभी निष्पादन पाथ्स का प्रयोग किया जाना चाहिए। इसका तात्पर्य यह है कि उच्च कम्पलेक्सिटी संख्या वाले मॉड्यूल को कम मूल्य वाले मॉड्यूल की तुलना में अधिक टैस्टिंग प्रयास की एसेंशियलता होती है क्योंकि उच्च कम्पलेक्सिटी संख्या कोड के माध्यम से अधिक मार्गों को इंगित करती है। इसका तात्पर्य यह भी है कि उच्च कम्पलेक्सिटी वाले मॉड्यूल को प्रोग्रामर के लिए समझना अधिक कठिन है क्योंकि प्रोग्रामर को विभिन्न मार्गों और उन मार्गों के परिणामों को समझना होता है। | ||
अनफॉरटुनेटली, किसी प्रोग्राम के माध्यम से सभी पॉसिबल पाथ्स का टैस्टिंग करना निरंतर व्यावहारिक नहीं होता है। ऊपर दिए गए उदाहरण को ध्यान में रखते हुए, हर बार एक अतिरिक्त if-then-else स्टेटमेंट जोड़ा जाता है, तो पॉसिबल पाथ्स की संख्या 2 गुना बढ़ जाती है। जैसे-जैसे प्रोग्राम इस प्रकार बढ़ता है, यह जल्दी से उस पॉइंट पर पहुंच जाता है जहां सभी पाथ्स की टैस्टिंग करना इम्प्रैक्टिकल हो जाता है। | |||
एक सामान्य टैस्टिंग रणनीति, उदाहरण के लिए एनआईएसटी स्ट्रक्चर्ड टैस्टिंग पद्धति द्वारा समर्थित, मॉड्यूल की पर्याप्त कवरेज प्राप्त करने के लिए एसेंशियल [[व्हाइट-बॉक्स परीक्षण|व्हाइट-बॉक्स टैस्टिंग]] की संख्या निर्धारित करने के लिए मॉड्यूल की साइक्लोमैटिक कम्पलेक्सिटी का उपयोग करना है। लगभग सभी | एक सामान्य टैस्टिंग रणनीति, उदाहरण के लिए एनआईएसटी स्ट्रक्चर्ड टैस्टिंग पद्धति द्वारा समर्थित, मॉड्यूल की पर्याप्त कवरेज प्राप्त करने के लिए एसेंशियल [[व्हाइट-बॉक्स परीक्षण|व्हाइट-बॉक्स टैस्टिंग]] की संख्या निर्धारित करने के लिए मॉड्यूल की साइक्लोमैटिक कम्पलेक्सिटी का उपयोग करना है। लगभग सभी केसेस में, ऐसी पद्धति के अनुसार, एक मॉड्यूल में कम से कम उतने ही टैस्टिंग होने चाहिए जितने उसकी साईक्लोमैटिक कम्पलेक्सिटी के हों; अधिकांश केसेस में, टैस्टिंगों की यह संख्या फ़ंक्शन के सभी प्रासंगिक पाथ्स का अभ्यास करने के लिए पर्याप्त है।<ref name="nist"/> | ||
एक फ़ंक्शन के उदाहरण के रूप में जिसे सटीक रूप से टैस्टिंग करने के लिए केवल ब्रांच कवरेज से अधिक की एसेंशियलता होती है, उपरोक्त फ़ंक्शन पर फिर से विचार करें, लेकिन मान लें कि बग होने से बचने के लिए, कोई भी कोड जो कॉल करता है <code>f1()</code> या <code>f3()</code> दूसरे को भी बुलाना चाहिए | एक फ़ंक्शन के उदाहरण के रूप में जिसे सटीक रूप से टैस्टिंग करने के लिए केवल ब्रांच कवरेज से अधिक की एसेंशियलता होती है, उपरोक्त फ़ंक्शन पर फिर से विचार करें, लेकिन मान लें कि बग होने से बचने के लिए, कोई भी कोड जो कॉल करता है <code>f1()</code> या <code>f3()</code> दूसरे को भी बुलाना चाहिए{{efn|This is a fairly common type of condition; consider the possibility that <code>f1</code> allocates some resource which <code>f3</code> releases.}} यह मानते हुए कि के परिणाम <code>c1()</code> और <code>c2()</code> इंडिपेंडेंट हैं, इसका अर्थ है कि ऊपर प्रस्तुत फ़ंक्शन में एक बग है। ब्रांच कवरेज हमें केवल दो टैस्टिंगों के साथ मेथड्स का टैस्टिंग करने की अनुमति देगा, और टैस्टिंगों का एक पॉसिबल समुच्चय निम्नलिखित केसेस का टैस्टिंग करना होगा: | ||
* <code>c1()</code> रिटर्न ट्रू है और <code>c2()</code> रिटर्न ट्रू है | * <code>c1()</code> रिटर्न ट्रू है और <code>c2()</code> रिटर्न ट्रू है | ||
Line 125: | Line 125: | ||
इनमें से कोई भी टैस्टिंग बग को उजागर करता है। | इनमें से कोई भी टैस्टिंग बग को उजागर करता है। | ||
=== | ===डिफेक्ट्स की संख्या से कोरिलेशन्स=== | ||
कई अध्ययनों ने किसी फ़ंक्शन या मेथड्स में होने वाले | कई अध्ययनों ने किसी फ़ंक्शन या मेथड्स में होने वाले डिफेक्ट्स की आवृत्ति के साथ मैककेबे की साइक्लोमैटिक कम्पलेक्सिटी संख्या के बीच कोरिलेशन्स की जांच की है।<ref name="fenton">{{cite journal | ||
|journal=IEEE Transactions on Software Engineering|author1=Norman E Fenton |author2=Martin Neil | | |journal=IEEE Transactions on Software Engineering|author1=Norman E Fenton |author2=Martin Neil | | ||
url=http://www.eecs.qmul.ac.uk/~norman/papers/defects_prediction_preprint105579.pdf| | url=http://www.eecs.qmul.ac.uk/~norman/papers/defects_prediction_preprint105579.pdf| | ||
title=A Critique of Software Defect Prediction Models| | title=A Critique of Software Defect Prediction Models| | ||
year=1999|volume=25|issue=3|pages=675–689|doi=10.1109/32.815326|citeseerx=10.1.1.548.2998 }}</ref> कुछ अध्ययन<ref name="schroeder99">{{cite journal| title=ऑब्जेक्ट-ओरिएंटेड मेट्रिक्स के लिए एक व्यावहारिक मार्गदर्शिका|author=Schroeder, Mark|s2cid=14945518|year=1999|volume=1|issue=6|pages=30–36|journal=IT Professional |doi=10.1109/6294.806902}}</ref> साईक्लोमैटिक कम्पलेक्सिटी और | year=1999|volume=25|issue=3|pages=675–689|doi=10.1109/32.815326|citeseerx=10.1.1.548.2998 }}</ref> कुछ अध्ययन<ref name="schroeder99">{{cite journal| title=ऑब्जेक्ट-ओरिएंटेड मेट्रिक्स के लिए एक व्यावहारिक मार्गदर्शिका|author=Schroeder, Mark|s2cid=14945518|year=1999|volume=1|issue=6|pages=30–36|journal=IT Professional |doi=10.1109/6294.806902}}</ref> साईक्लोमैटिक कम्पलेक्सिटी और डिफेक्ट्स के बीच एक सकारात्मक कोरिलेशन्स खोजें: जिन कार्यों और मेथड्स में सबसे अधिक कम्पलेक्सिटी होती है उनमें सबसे अधिक डिफेक्ट भी होते हैं। चूँकि, साइक्लोमैटिक कम्पलेक्सिटी और प्रोग्राम साइज़ (सामान्यतः कोड की पंक्तियों में मापा जाता है) के बीच संबंध को कई बार प्रदर्शित किया गया है। [[ द हैटन्स |द हैटन्स]] ने प्रमाणित किया है<ref name="taic"> | ||
{{cite web |url=http://www.leshatton.org/TAIC2008-29-08-2008.html |title=The role of empiricism in improving the reliability of future software |author=Les Hatton |year=2008 |at=version 1.1}}</ref> उस कम्पलेक्सिटी में कोड की पंक्तियों के समान ही पूर्वानुमान लगाने की क्षमता होती है। | {{cite web |url=http://www.leshatton.org/TAIC2008-29-08-2008.html |title=The role of empiricism in improving the reliability of future software |author=Les Hatton |year=2008 |at=version 1.1}}</ref> उस कम्पलेक्सिटी में कोड की पंक्तियों के समान ही पूर्वानुमान लगाने की क्षमता होती है। | ||
प्रोग्राम के | |||
{{cite book |title=Metrics and Models in Software Quality Engineering |author=Kan |pages=316–317 |publisher=Addison-Wesley |year=2003 |isbn=978-0-201-72915-3}}</ref> चूँकि यह संबंध संभवतः सत्य है, लेकिन इसे सरलता से उपयोग में नहीं लाया जा सकता।<ref name=cherf>{{cite journal| | प्रोग्राम के साइज़ को कंट्रोल करने वाले अध्ययन (अर्थात, भिन्न-भिन्न कम्पलेक्सिटी वाले लेकिन समान साइज़ वाले मॉड्यूल की तुलना करना) सामान्यतः कम निर्णायक होते हैं, जिनमें से कई में कोई महत्वपूर्ण कोरिलेशन्स नहीं पाया जाता है, जबकि अन्य में कोरिलेशन्स पाया जाता है। क्षेत्र का अध्ययन करने वाले कुछ शोधकर्ता कोई कोरिलेशन्स नहीं पाते हुए अध्ययन में उपयोग की जाने वाली मेथड्स की वैधता पर सवाल उठाते हैं।<ref name="kan"> | ||
{{cite book |title=Metrics and Models in Software Quality Engineering |author=Kan |pages=316–317 |publisher=Addison-Wesley |year=2003 |isbn=978-0-201-72915-3}}</ref> चूँकि यह संबंध संभवतः सत्य है, लेकिन इसे सरलता से उपयोग में नहीं लाया जा सकता।<ref name="cherf">{{cite journal| | |||
journal=Journal of Software Quality| | journal=Journal of Software Quality| | ||
author=G.S. Cherf| | author=G.S. Cherf| | ||
Line 139: | Line 140: | ||
year=1992|volume=1|issue=3|pages=147–158| | year=1992|volume=1|issue=3|pages=147–158| | ||
issn=1573-1367|doi=10.1007/bf01720922| | issn=1573-1367|doi=10.1007/bf01720922| | ||
s2cid=37274091}}</ref> चूँकि प्रोग्राम का | s2cid=37274091}}</ref> चूँकि प्रोग्राम का साइज़ व्यावसायिक सॉफ़्टवेयर की कंट्रोलीय विशेषता नहीं है, इसलिए मैककेब्स के नंबर की उपयोगिता पर प्रश्न उठाया गया है।<ref name="fenton" /> इस अवलोकन का सार यह है कि बड़े प्रोग्राम अधिक काम्प्लेक्स होते हैं और उनमें अधिक डिफेक्ट होते हैं। कोड की साईक्लोमैटिक कम्पलेक्सिटी को कम करने से कोरिलेशन्स उस कोड में त्रुटियों या बग की संख्या को कम करने का कारण नहीं बनता है। चूँकि, [[ISO 26262]] जैसे अंतर्राष्ट्रीय सुरक्षा मानक, कम कोड कम्पलेक्सिटी को लागू करने वाले कोडिंग दिशानिर्देशों को अनिवार्य करते हैं।<ref name="ISO26262Part3">{{cite book | title =ISO 26262-3:2011(en) Road vehicles — Functional safety — Part 3: Concept phase| publisher =International Standardization Organization | url =https://www.iso.org/obp/ui/#iso:std:iso:26262:-3:ed-1:v1:en}}</ref> | ||
==आर्टिफिसियल इंटेलिजेंस== | ==आर्टिफिसियल इंटेलिजेंस== | ||
आर्टिफिसियल इंटेलिजेंसमत्ता प्रोग्रामों की सिमेंटिक कम्पलेक्सिटी के मूल्यांकन के लिए साइक्लोमैटिक कम्पलेक्सिटी का भी उपयोग किया जा सकता है।<ref>{{cite journal |doi=10.1016/j.compag.2011.11.009 |title=भूमध्यसागरीय परिदृश्य परिवर्तनों की जटिलता के मॉडलिंग में कृत्रिम बुद्धिमत्ता|journal=Computers and Electronics in Agriculture |volume=81 |pages=87–96 |year=2012 |last1=Papadimitriou |first1=Fivos }}</ref> | आर्टिफिसियल इंटेलिजेंसमत्ता प्रोग्रामों की सिमेंटिक कम्पलेक्सिटी के मूल्यांकन के लिए साइक्लोमैटिक कम्पलेक्सिटी का भी उपयोग किया जा सकता है।<ref>{{cite journal |doi=10.1016/j.compag.2011.11.009 |title=भूमध्यसागरीय परिदृश्य परिवर्तनों की जटिलता के मॉडलिंग में कृत्रिम बुद्धिमत्ता|journal=Computers and Electronics in Agriculture |volume=81 |pages=87–96 |year=2012 |last1=Papadimitriou |first1=Fivos }}</ref> | ||
==अल्ट्रामेट्रिक टोपोलॉजी== | ==अल्ट्रामेट्रिक टोपोलॉजी== | ||
साइक्लोमैटिक कम्पलेक्सिटी जिओग्राफिकल और लैंडस्केप-इकोलॉजिकल एनालिसिस में उपयोगी सिद्ध हुई है, यह दिखाए जाने के पश्चात कि इसे [[अल्ट्रामेट्रिक स्पेस]] दूरी के ग्राफ़ पर लागू किया जा सकता है।<ref>{{cite journal |doi=10.1080/1747423X.2011.637136 |title=अल्ट्रामेट्रिक टोपोलॉजी के साथ भूमि उपयोग और परिदृश्य जटिलता का गणितीय मॉडलिंग|journal=Journal of Land Use Science |volume=8 |issue=2 |pages=234–254 |year=2013 |last1=Papadimitriou |first1=Fivos |s2cid=121927387 |doi-access=free }}</ref> | साइक्लोमैटिक कम्पलेक्सिटी जिओग्राफिकल और लैंडस्केप-इकोलॉजिकल एनालिसिस में उपयोगी सिद्ध हुई है, यह दिखाए जाने के पश्चात कि इसे [[अल्ट्रामेट्रिक स्पेस|अल्ट्रामेट्रिक]] दूरी के ग्राफ़ पर लागू किया जा सकता है।<ref>{{cite journal |doi=10.1080/1747423X.2011.637136 |title=अल्ट्रामेट्रिक टोपोलॉजी के साथ भूमि उपयोग और परिदृश्य जटिलता का गणितीय मॉडलिंग|journal=Journal of Land Use Science |volume=8 |issue=2 |pages=234–254 |year=2013 |last1=Papadimitriou |first1=Fivos |s2cid=121927387 |doi-access=free }}</ref> | ||
==यह भी देखें== | ==यह भी देखें== | ||
* प्रोग्रामिंग कम्पलेक्सिटी | * प्रोग्रामिंग कम्पलेक्सिटी | ||
Line 171: | Line 172: | ||
* [http://www.leshatton.org/Documents/TAIC2008-29-08-2008.pdf The role of empiricism in improving the reliability of future software] | * [http://www.leshatton.org/Documents/TAIC2008-29-08-2008.pdf The role of empiricism in improving the reliability of future software] | ||
* [https://www.cqse.eu/en/blog/mccabe-cyclomatic-complexity/ McCabe's Cyclomatic Complexity and Why We Don't Use It] | * [https://www.cqse.eu/en/blog/mccabe-cyclomatic-complexity/ McCabe's Cyclomatic Complexity and Why We Don't Use It] | ||
[[Category: | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
[[Category:Created On 24/07/2023]] | [[Category:Created On 24/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:सॉफ्टवेयर मेट्रिक्स]] |
Latest revision as of 10:11, 23 August 2023
साइक्लोमैटिक कम्पलेक्सिटी एक सॉफ्टवेयर मीट्रिक है जिसका उपयोग प्रोग्रामिंग कम्पलेक्सिटी को इंगित करने के लिए किया जाता है। यह प्रोग्राम के स्रोत कोड के माध्यम से रैखिक रूप से इंडिपेंडेंट पाथ्स की संख्या का एक मात्रात्मक माप है। इसे 1976 में थॉमस जे. मैककेबे, सीनियर द्वारा विकसित किया गया था।
साइक्लोमैटिक कम्पलेक्सिटी की कंप्यूटेड प्रोग्राम के कंट्रोल-फ्लो ग्राफ का उपयोग करके की जाती है: ग्राफ़ (असतत गणित) के नोड्स एक प्रोग्राम के कमांड्स तथा इंडीविज़िबल समूहों के अनुरूप होते हैं, और एक डायरेक्टेड ग्राफ एज दो नोड्स को जोड़ता है यदि दूसरे कमांड को पहले कमांड के पश्चात तेज़ी से निष्पादित किया जा सकता है। साइक्लोमैटिक कम्पलेक्सिटी को एक प्रोग्राम के समाविष्ट इंडिविजुअल फ़ंक्शन (कंप्यूटर विज्ञान), मॉड्यूलर प्रोग्रामिंग, मेथड्स (कंप्यूटर विज्ञान) या क्लासेस (कंप्यूटर विज्ञान) पर भी लागू किया जा सकता है।
एक सॉफ़्टवेयर टैस्टिंग रणनीति, जिसे मैककेबे ने बेसिस पाथ टैस्टिंग कहा है, जिन्होंने सबसे पहले इसे प्रस्तावित किया था, प्रोग्राम के माध्यम से प्रत्येक रैखिक रूप से इंडिपेंडेंट पाथ की टैस्टिंग करना है; इस केस में, टैस्टिंग केसेस की संख्या प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी के समतुल्य होती है।[1]
विवरण
परिभाषा
स्रोत कोड के एक अनुभाग की साईक्लोमैटिक कम्पलेक्सिटी इसके समाविष्ट रैखिक रूप से इंडिपेंडेंट पाथ (ग्राफ सिद्धांत) की संख्या है - पाथ्स का एक समुच्चय रैखिक रूप से निर्भर होता है यदि एक या अधिक पाथ्स का एक उपसमुच्चय होता है जहां उनके एज समुच्चय का सममित अंतर रिक्त होता है। उदाहरण के लिए, यदि स्रोत कोड में कोई कंट्रोल फ्लो (कंडीशनल या डिसीज़न पॉइंट) नहीं है, तो कम्पलेक्सिटी 1 होगी, क्योंकि कोड के माध्यम से केवल एक ही पाथ होता है। यदि कोड में एक एकल-केस IF स्टेटमेंट है, तो कोड के माध्यम से दो पाथ होंगे: एक जहां IF स्टेटमेंट TRUE का मूल्यांकन करता है और दूसरा जहां यह FALSE का मूल्यांकन करता है, इसलिए कम्पलेक्सिटी 2 होगी, दो नेस्टेड एकल-केस IF, या दो शर्तों वाला एक IF, 3 की कम्पलेक्सिटी उत्पन्न करता है।
गणितीय रूप से, स्ट्रक्चर्ड प्रोग्रामिंग की साईक्लोमैटिक कम्पलेक्सिटी[lower-alpha 1] के प्रोग्राम को कंट्रोल-फ्लो ग्राफ के संदर्भ में परिभाषित किया गया है, एक डायरेक्टेड ग्राफ जिसमें प्रोग्राम के बेसिक ब्लॉक होते हैं, दो बेसिक ब्लॉकों के बीच एक एज के साथ यदि कंट्रोल पहले से दूसरे तक जा सकता है। तो कम्पलेक्सिटी M को इसलिए परिभाषित किया गया है:[2]
- E = ग्राफ़ के एजेस की संख्या
- N = ग्राफ़ के नोड्स की संख्या
- P = कनेक्टेड कम्पोनेंट्स की संख्या (ग्राफ़ सिद्धांत)
एक वैकल्पिक सूत्रीकरण एक ग्राफ़ का उपयोग करना है जिसमें प्रत्येक एग्जिट पॉइंट दोबारा एंट्री पॉइंट से जुड़ा होता है। इस केस में, ग्राफस्ट्रॉन्ग्ली कनेक्टेड होता है, और प्रोग्राम की साइक्लोमैटिक कम्पलेक्सिटी इसके ग्राफ की साईक्लोमैटिक संख्या के समतुल्य है (जिसे ग्राफ सिद्धांत में पहली बेट्टी संख्या), जिसे इस प्रकार परिभाषित किया गया है[2]
एकल प्रोग्राम (या सबरूटीन या मेथड्स) के लिए, P निरंतर 1 के समतुल्य होता है। इसलिए एकल सबरूटीन के लिए एक सरल सूत्र है,[3]
मैककेबे ने दिखाया कि केवल एक एंट्री पॉइंट और एक एग्जिट पॉइंट के साथ किसी भी स्ट्रक्चर्ड प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी उस प्रोग्राम में निहित डिसीज़न पॉइंटओं (अर्थात, यदि स्टेटमेंट या कंडीशनल लूप) की संख्या प्लस एक के समतुल्य है। चूँकि, यह केवल निम्नतम, मशीन-स्तर के निर्देशों पर गिने जाने वाले डिसीज़न पॉइंटओं के लिए ट्रू है।[4] यौगिक विधेय से जुड़े डिसीज़न जैसे उच्च-स्तरीय लैंगुएजेस में पाए जाते हैं IF cond1 AND cond2 THEN ...
सम्मिलित विधेय चर के संदर्भ में गिना जाना चाहिए, अर्थात इस उदाहरण में किसी को दो डिसीज़न पॉइंट गिनने चाहिए, क्योंकि IF cond1 THEN IF cond2 THEN ...
मशीन स्तर पर यह समतुल्य है।[2][5]
साइक्लोमैटिक कम्पलेक्सिटी को कई एग्जिट पॉइंटओं वाले प्रोग्राम तक बढ़ाया जा सकता है; इस केस में यह समतुल्य है
बीजगणितीय टोपोलॉजी के संदर्भ में स्पष्टीकरण
ग्राफ़ का एक सम उपसमुच्चय (जिसे यूलेरियन पाथ के रूप में भी जाना जाता है) वह है जहां प्रत्येक शीर्ष (ग्राफ़ सिद्धांत) एजेस की सम संख्या के साथ घटना है; ऐसे उपसमुच्चय साइकल्स और पृथक शीर्षों के संघ हैं। निम्नलिखित में, सम सबग्राफ को उनके एज समुच्चय के साथ पहचाना जाएगा, जो केवल उन सम सबग्राफ पर विचार करने के समतुल्य है जिसमें पूर्ण ग्राफ के सभी शीर्ष सम्मिलित हैं।
ग्राफ के सभी सम उपग्राफों का समुच्चय सममित अंतर के तहत बंद है, और इस प्रकार इसे जीएफ (2) पर एक वेक्टर समष्टि के रूप में देखा जा सकता है; इस सदिश समष्टि को ग्राफ़ का साइकल्स समष्टि कहा जाता है। ग्राफ़ की साईक्लोमैटिक संख्या को इस समष्टि के आयाम के रूप में परिभाषित किया गया है। चूँकि जीएफ(2) में दो तत्व हैं और साइकल्स समष्टि एसेंशियल रूप से परिमित है, साइकल्स संख्या भी साइकल्स समष्टि में तत्वों की संख्या के 2-लघुगणक के समतुल्य है।
साइकल्स समष्टि के लिए एक आधार सरलता से ग्राफ सिद्धांत के ट्री की लाइब्रेरी को सही करके बनाया जा सकता है, और फिर फॉरेस्ट में नहीं एक एज से बने साइकल्स और उस एज के अंतिम पॉइंटओं को जोड़ने वाले फॉरेस्ट में पाथ पर विचार किया जा सकता है; ये साइकल्स साइकल्स समष्टि के लिए आधार बनाते हैं। इसलिए, साइक्लोमैटिक संख्या ग्राफ़ के अधिकतम फैले हुए फॉरेस्ट में नहीं एजेस की संख्या के समतुल्य होती है। चूँकि ग्राफ़ के अधिकतम फैले हुए फॉरेस्ट में एजेस की संख्या शीर्षों की संख्या घटा कम्पोनेंट्स की संख्या के समतुल्य होती है, सूत्र साईक्लोमैटिक संख्या के लिए ऊपर इस प्रकार है।[7]
अधिक टोपोलॉजिकली इंक्लाइनड के लिए, साइक्लोमैटिक कम्पलेक्सिटी को वैकल्पिक रूप से एक सापेक्ष बेट्टी संख्या, एक सापेक्ष होमोलॉजी समूह के साइज़ के रूप में परिभाषित किया जा सकता है:
- रैखिक रूप से इंडिपेंडेंट समरूपता से मेल खाता है, और इसका अर्थ है कि कोई बैकट्रैकिंग को दोगुना नहीं करता है;
- पाथ प्रथम समरूपता से मेल खाते हैं: पाथ एक 1-आयामी वस्तु है;
- सापेक्ष का अर्थ है कि पाथ किसी एंट्री या एग्जिट पॉइंट पर स्टार्ट और फ़िनिश होनी चाहिए।
यह साईक्लोमैटिक कम्पलेक्सिटी की सहज धारणा से मेल खाता है, और ऊपर बताए अनुसार कंप्यूटेड की जा सकती है।
वैकल्पिक रूप से, कोई किसी दिए गए कम्पोनेंट पर सभी टर्मिनल नोड्स की पहचान करके (एक साथ चिपकाकर) पूर्ण बेट्टी संख्या (पूर्ण समरूपता - सापेक्ष नहीं) के माध्यम से इसकी कंप्यूटेड कर सकता है (या समकक्ष, एंट्री द्वार से एग्जिट को जोड़ने वाले पाथ बनाएं), जिस केस में (नए, संवर्धित ग्राफ को कॉल करना) , जो है ), एक प्राप्त होता है
यह लूप की संख्या और कम्पोनेंट्स की संख्या के रूप में साइक्लोमैटिक कम्पलेक्सिटी के लक्षण वर्णन से मेल खाता है।
व्याख्या
अपनी प्रस्तुति में 'जोखिम की पहचान करने के लिए सॉफ्टवेयर गुणवत्ता मेट्रिक्स'[8] होमलैंड सिक्योरिटी विभाग के लिए, टॉम मैककेबे ने साईक्लोमैटिक कम्पलेक्सिटी की व्याख्या करने के लिए निम्नलिखित क्लासेसीकरण प्रस्तुत किया है:
- 1-10 सिंपल प्रोसीजर, लिटिल रिस्क
- 11-20 मोर काम्प्लेक्स, मॉडरेट रिस्क
- 21 - 50 काम्प्लेक्स, हाई रिस्क
- > 50 अन्टेस्टेबल कोड, वैरी हाई रिस्क
अनुप्रयोग
डेवलपमेंट के समय कम्पलेक्सिटी को सीमित करना
मैककेबे के मूल अनुप्रयोगों में से एक प्रोग्राम डेवलपमेंट के समय दिनचर्या की कम्पलेक्सिटी को सीमित करना था; उन्होंने सुझाव दिया कि प्रोग्रामर्स को अपने द्वारा विकसित किए जा रहे मॉड्यूल की कम्पलेक्सिटी की कंप्यूटेड करनी चाहिए, और जब भी मॉड्यूल की साइक्लोमैटिक कम्पलेक्सिटी 10 से अधिक हो तो उन्हें छोटे मॉड्यूल में विभाजित करना चाहिए,[2] इस अभ्यास को एनआईएसटी स्ट्रक्चर्ड टैस्टिंग पद्धति द्वारा अपनाया गया था, इस अवलोकन के साथ कि मैककेबे के मूल प्रकाशन के पश्चात से, 10 के आंकड़े को पर्याप्त पुष्ट साक्ष्य प्राप्त हुए थे, लेकिन कुछ परिकेसेस में प्रतिबंध में छोड़ देना और 15 तक की कम्पलेक्सिटी वाले मॉड्यूल को अनुमति देना उचित हो सकता है। चूंकि पद्धति ने स्वीकार किया कि सहमति-सीमा से परे जाने के लिए कभी-कभी कारण थे, इसने अपनी सिफारिश को प्रत्येक मॉड्यूल के लिए, या तो साइक्लोमैटिक कम्पलेक्सिटी को [सहमत-सीमा] तक सीमित कर दिया या एक प्रदान किया गया है। सीमा क्यों पार की गई इसका लिखित स्पष्टीकरण भी सम्मिलित होता है।[9]
किसी प्रोग्राम की संरचना को मापना
मैककेबे के 1976 के पेपर का खंड VI यह निर्धारित करने से संबंधित है कि नॉन-स्ट्रक्चर्ड प्रोग्रामिंग के कंट्रोल-फ्लो ग्राफ़ (सीएफजी) उनके सबग्राफ के संदर्भ में कैसा दिखते हैं, जिसे मैककेबे पहचानते हैं। (उस भाग के विवरण के लिए स्ट्रक्चर्ड प्रोग्राम प्रमेय देखें।) मैककेबे ने उस खंड को एक संख्यात्मक माप का प्रस्ताव देकर समाप्त किया है कि कोई दिया गया प्रोग्राम स्ट्रक्चर्ड प्रोग्रामिंग आदर्श के कितना निकट है, अर्थात मैककेबे के नवशास्त्रवाद का उपयोग करके इसकी स्ट्रक्चर्डता मैककेबे ने इस उद्देश्य के लिए जो माप तैयार किया, उसे एसेंशियल कम्पलेक्सिटी (स्ट्रक्चर्डता का संख्यात्मक माप) कहा जाता है।[2]
इस माप की कंप्यूटेड करने के लिए, मूल सीएफजी को एकल-प्रविष्टि और एकल-एग्जिट पॉइंट वाले सबग्राफ की पहचान करके पुनरावृत्त रूप से कम किया जाता है, जिन्हें फिर एक नोड द्वारा प्रतिस्थापित किया जाता है। यह कटौती इस बात से मेल खाती है कि यदि कोई इंसान कोड के बड़े हिस्से से एक सबरूटीन निकालता है तो वह क्या करेगा, (आजकल ऐसी प्रक्रिया रिफेक्टरिंग के अम्ब्रेला शब्द के अंतर्गत आती है।) मैककेबे की कटौती मेथड्स को पश्चात में कुछ पाठ्यपुस्तकों में संक्षेपण कहा गया, क्योंकि इसे संक्षेपण (ग्राफ सिद्धांत) के सामान्यीकरण के रूप में देखा गया था।[10] यदि कोई प्रोग्राम स्ट्रक्चर्ड है, तो मैककेबे की कमी/संक्षेपण प्रक्रिया इसे एकल सीएफजी नोड में कम कर देती है। इसके विपरीत, यदि प्रोग्राम स्ट्रक्चर्ड नहीं है, तो पुनरावृत्त प्रक्रिया अपरिवर्तनीय भाग की पहचान करेगी। मैककेबे द्वारा परिभाषित एसेंशियल कम्पलेक्सिटी माप केवल इस अपरिवर्तनीय ग्राफ की साईक्लोमैटिक कम्पलेक्सिटी है, इसलिए यह सभी स्ट्रक्चर्ड प्रोग्रामों के लिए सटीक रूप से 1 होगा, लेकिन नॉन-स्ट्रक्चर्ड प्रोग्रामों के लिए एक से अधिक होता है।[9]: 80
सॉफ़्टवेयर टैस्टिंग के लिए इम्प्लीकेशन
साइक्लोमैटिक कम्पलेक्सिटी का एक अन्य अनुप्रयोग उन टैस्टिंग केसेस की संख्या निर्धारित करना है जो किसी विशेष मॉड्यूल के संपूर्ण टैस्टिंग कवरेज को प्राप्त करने के लिए एसेंशियल हैं।
यह साईक्लोमैटिक कम्पलेक्सिटी के दो गुणों के कारण उपयोगी है, M, एक विशिष्ट मॉड्यूल के लिए:
- M पूर्ण ब्रांच कवरेज प्राप्त करने के लिए एसेंशियल टैस्टिंग केसेस की संख्या के लिए ऊपरी सीमा है।
- M कंट्रोल-फ्लो ग्राफ़ (सीएफजी) के माध्यम से पाथ्स की संख्या के लिए निचली सीमा है। यह मानते हुए कि प्रत्येक टैस्टिंग विधि एक पाथ लेती है, पाथ कवरेज प्राप्त करने के लिए एसेंशियल केसेस की संख्या उन पाथ्स की संख्या के समतुल्य होती है जिन्हें वास्तव में लिया जा सकता है। लेकिन कुछ पाथ असंभव हो सकते हैं, इसलिए चूंकि सीएफजी के माध्यम से पाथ्स की संख्या स्पष्ट रूप से पाथ कवरेज के लिए एसेंशियल टैस्टिंग केसेस की संख्या पर ऊपरी सीमा है, यह पश्चात वाली संख्या (पॉसिबल पाथ्स की) कभी-कभी कम होती है M.
उपरोक्त तीनों संख्याएँ समान हो सकती हैं: ब्रांच कवरेज साइक्लोमेटिक कम्पलेक्सिटी पाथ्स की संख्या
उदाहरण के लिए, एक प्रोग्राम पर विचार करें जिसमें दो अनुक्रमिक यदि-तब-अन्यथा स्टेटमेंट सम्मिलित हैं।
if (c1())
f1();
else
f2();
if (c2())
f3();
else
f4();
इस उदाहरण में, पूर्ण ब्रांच कवरेज प्राप्त करने के लिए दो टैस्टिंग केस पर्याप्त हैं, जबकि पूर्ण पाथ कवरेज के लिए चार एसेंशियल हैं। प्रोग्राम की साईक्लोमैटिक कम्पलेक्सिटी 3 है (क्योंकि प्रोग्राम के लिए स्ट्रॉन्गली कनेक्टेड ग्राफ में 9 एज, 7 नोड्स और 1 जुड़ा कम्पोनेंट (9 − 7 + 1) सम्मिलित है)।
समान्यता, किसी मॉड्यूल का पूरे प्रकार से टैस्टिंग करने के लिए, मॉड्यूल के माध्यम से सभी निष्पादन पाथ्स का प्रयोग किया जाना चाहिए। इसका तात्पर्य यह है कि उच्च कम्पलेक्सिटी संख्या वाले मॉड्यूल को कम मूल्य वाले मॉड्यूल की तुलना में अधिक टैस्टिंग प्रयास की एसेंशियलता होती है क्योंकि उच्च कम्पलेक्सिटी संख्या कोड के माध्यम से अधिक मार्गों को इंगित करती है। इसका तात्पर्य यह भी है कि उच्च कम्पलेक्सिटी वाले मॉड्यूल को प्रोग्रामर के लिए समझना अधिक कठिन है क्योंकि प्रोग्रामर को विभिन्न मार्गों और उन मार्गों के परिणामों को समझना होता है।
अनफॉरटुनेटली, किसी प्रोग्राम के माध्यम से सभी पॉसिबल पाथ्स का टैस्टिंग करना निरंतर व्यावहारिक नहीं होता है। ऊपर दिए गए उदाहरण को ध्यान में रखते हुए, हर बार एक अतिरिक्त if-then-else स्टेटमेंट जोड़ा जाता है, तो पॉसिबल पाथ्स की संख्या 2 गुना बढ़ जाती है। जैसे-जैसे प्रोग्राम इस प्रकार बढ़ता है, यह जल्दी से उस पॉइंट पर पहुंच जाता है जहां सभी पाथ्स की टैस्टिंग करना इम्प्रैक्टिकल हो जाता है।
एक सामान्य टैस्टिंग रणनीति, उदाहरण के लिए एनआईएसटी स्ट्रक्चर्ड टैस्टिंग पद्धति द्वारा समर्थित, मॉड्यूल की पर्याप्त कवरेज प्राप्त करने के लिए एसेंशियल व्हाइट-बॉक्स टैस्टिंग की संख्या निर्धारित करने के लिए मॉड्यूल की साइक्लोमैटिक कम्पलेक्सिटी का उपयोग करना है। लगभग सभी केसेस में, ऐसी पद्धति के अनुसार, एक मॉड्यूल में कम से कम उतने ही टैस्टिंग होने चाहिए जितने उसकी साईक्लोमैटिक कम्पलेक्सिटी के हों; अधिकांश केसेस में, टैस्टिंगों की यह संख्या फ़ंक्शन के सभी प्रासंगिक पाथ्स का अभ्यास करने के लिए पर्याप्त है।[9]
एक फ़ंक्शन के उदाहरण के रूप में जिसे सटीक रूप से टैस्टिंग करने के लिए केवल ब्रांच कवरेज से अधिक की एसेंशियलता होती है, उपरोक्त फ़ंक्शन पर फिर से विचार करें, लेकिन मान लें कि बग होने से बचने के लिए, कोई भी कोड जो कॉल करता है f1()
या f3()
दूसरे को भी बुलाना चाहिए[lower-alpha 2] यह मानते हुए कि के परिणाम c1()
और c2()
इंडिपेंडेंट हैं, इसका अर्थ है कि ऊपर प्रस्तुत फ़ंक्शन में एक बग है। ब्रांच कवरेज हमें केवल दो टैस्टिंगों के साथ मेथड्स का टैस्टिंग करने की अनुमति देगा, और टैस्टिंगों का एक पॉसिबल समुच्चय निम्नलिखित केसेस का टैस्टिंग करना होगा:
c1()
रिटर्न ट्रू है औरc2()
रिटर्न ट्रू हैc1()
रिटर्न फॉल्स है औरc2()
रिटर्न फॉल्स है
इनमें से कोई भी विधि बग को उजागर नहीं करता है। चूँकि, यदि हम एसेंशियल टैस्टिंगों की संख्या को इंगित करने के लिए साइक्लोमैटिक कम्पलेक्सिटी का उपयोग करते हैं, तो संख्या बढ़कर 3 हो जाती है। इसलिए हमें निम्नलिखित पाथ्स में से एक का टैस्टिंग करना चाहिए:
c1()
रिटर्न ट्रू है औरc2()
रिटर्न फॉल्स हैc1()
रिटर्न फॉल्स देता है औरc2()
रिटर्न ट्रू है
इनमें से कोई भी टैस्टिंग बग को उजागर करता है।
डिफेक्ट्स की संख्या से कोरिलेशन्स
कई अध्ययनों ने किसी फ़ंक्शन या मेथड्स में होने वाले डिफेक्ट्स की आवृत्ति के साथ मैककेबे की साइक्लोमैटिक कम्पलेक्सिटी संख्या के बीच कोरिलेशन्स की जांच की है।[11] कुछ अध्ययन[12] साईक्लोमैटिक कम्पलेक्सिटी और डिफेक्ट्स के बीच एक सकारात्मक कोरिलेशन्स खोजें: जिन कार्यों और मेथड्स में सबसे अधिक कम्पलेक्सिटी होती है उनमें सबसे अधिक डिफेक्ट भी होते हैं। चूँकि, साइक्लोमैटिक कम्पलेक्सिटी और प्रोग्राम साइज़ (सामान्यतः कोड की पंक्तियों में मापा जाता है) के बीच संबंध को कई बार प्रदर्शित किया गया है। द हैटन्स ने प्रमाणित किया है[13] उस कम्पलेक्सिटी में कोड की पंक्तियों के समान ही पूर्वानुमान लगाने की क्षमता होती है।
प्रोग्राम के साइज़ को कंट्रोल करने वाले अध्ययन (अर्थात, भिन्न-भिन्न कम्पलेक्सिटी वाले लेकिन समान साइज़ वाले मॉड्यूल की तुलना करना) सामान्यतः कम निर्णायक होते हैं, जिनमें से कई में कोई महत्वपूर्ण कोरिलेशन्स नहीं पाया जाता है, जबकि अन्य में कोरिलेशन्स पाया जाता है। क्षेत्र का अध्ययन करने वाले कुछ शोधकर्ता कोई कोरिलेशन्स नहीं पाते हुए अध्ययन में उपयोग की जाने वाली मेथड्स की वैधता पर सवाल उठाते हैं।[14] चूँकि यह संबंध संभवतः सत्य है, लेकिन इसे सरलता से उपयोग में नहीं लाया जा सकता।[15] चूँकि प्रोग्राम का साइज़ व्यावसायिक सॉफ़्टवेयर की कंट्रोलीय विशेषता नहीं है, इसलिए मैककेब्स के नंबर की उपयोगिता पर प्रश्न उठाया गया है।[11] इस अवलोकन का सार यह है कि बड़े प्रोग्राम अधिक काम्प्लेक्स होते हैं और उनमें अधिक डिफेक्ट होते हैं। कोड की साईक्लोमैटिक कम्पलेक्सिटी को कम करने से कोरिलेशन्स उस कोड में त्रुटियों या बग की संख्या को कम करने का कारण नहीं बनता है। चूँकि, ISO 26262 जैसे अंतर्राष्ट्रीय सुरक्षा मानक, कम कोड कम्पलेक्सिटी को लागू करने वाले कोडिंग दिशानिर्देशों को अनिवार्य करते हैं।[16]
आर्टिफिसियल इंटेलिजेंस
आर्टिफिसियल इंटेलिजेंसमत्ता प्रोग्रामों की सिमेंटिक कम्पलेक्सिटी के मूल्यांकन के लिए साइक्लोमैटिक कम्पलेक्सिटी का भी उपयोग किया जा सकता है।[17]
अल्ट्रामेट्रिक टोपोलॉजी
साइक्लोमैटिक कम्पलेक्सिटी जिओग्राफिकल और लैंडस्केप-इकोलॉजिकल एनालिसिस में उपयोगी सिद्ध हुई है, यह दिखाए जाने के पश्चात कि इसे अल्ट्रामेट्रिक दूरी के ग्राफ़ पर लागू किया जा सकता है।[18]
यह भी देखें
- प्रोग्रामिंग कम्पलेक्सिटी
- कम्पलेक्सिटी जाल
- कंप्यूटर प्रोग्राम
- कंप्यूटर प्रोग्रामिंग
- बहाव को काबू करें
- डिसीज़न-से-डिसीज़न पाथ
- डिज़ाइन विधेय
- एसेंशियल कम्पलेक्सिटी (स्ट्रक्चर्डता का संख्यात्मक माप)
- हालस्टेड कम्पलेक्सिटी उपाय
- सॉफ्टवेयर इंजीनियरिंग
- सॉफ़्टवेयर टैस्टिंग
- स्थैतिक प्रोग्राम एनालिसिस
- रख-रखाव
टिप्पणियाँ
- ↑ Here "structured" means in particular "with a single exit (return statement) per function".
- ↑ This is a fairly common type of condition; consider the possibility that
f1
allocates some resource whichf3
releases.
संदर्भ
- ↑ A J Sobey. "Basis Path Testing".
- ↑ 2.0 2.1 2.2 2.3 2.4 McCabe (December 1976). "एक जटिलता उपाय". IEEE Transactions on Software Engineering. SE-2 (4): 308–320. doi:10.1109/tse.1976.233837. S2CID 9116234.
- ↑ Philip A. Laplante (25 April 2007). सॉफ्टवेयर इंजीनियरिंग के बारे में प्रत्येक इंजीनियर को क्या पता होना चाहिए. CRC Press. p. 176. ISBN 978-1-4200-0674-2.
- ↑ Fricker, Sébastien (April 2018). "What exactly is cyclomatic complexity?". froglogic GmbH. Retrieved October 27, 2018.
To compute a graph representation of code, we can simply disassemble its assembly code and create a graph following the rules: ...
- ↑ 5.0 5.1 J. Belzer; A. Kent; A. G. Holzman; J. G. Williams (1992). Encyclopedia of Computer Science and Technology. CRC Press. pp. 367–368.
- ↑ Harrison (October 1984). "मैकाबे की जटिलता माप को बहु-निकास कार्यक्रमों पर लागू करना". Software: Practice and Experience. 14 (10): 1004–1007. doi:10.1002/spe.4380141009. S2CID 62422337.
- ↑ Diestel, Reinhard (2000). Graph theory. Graduate texts in mathematics 173 (2 ed.). New York: Springer. ISBN 978-0-387-98976-1.
- ↑ Thomas McCabe Jr. (2008). "जोखिम की पहचान करने के लिए सॉफ़्टवेयर गुणवत्ता मेट्रिक्स". Archived from the original on 2022-03-29.
- ↑ 9.0 9.1 9.2 Arthur H. Watson; Thomas J. McCabe (1996). "Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric" (PDF). NIST Special Publication 500-235.
- ↑ Paul C. Jorgensen (2002). Software Testing: A Craftsman's Approach, Second Edition (2nd ed.). CRC Press. pp. 150–153. ISBN 978-0-8493-0809-3.
- ↑ 11.0 11.1 Norman E Fenton; Martin Neil (1999). "A Critique of Software Defect Prediction Models" (PDF). IEEE Transactions on Software Engineering. 25 (3): 675–689. CiteSeerX 10.1.1.548.2998. doi:10.1109/32.815326.
- ↑ Schroeder, Mark (1999). "ऑब्जेक्ट-ओरिएंटेड मेट्रिक्स के लिए एक व्यावहारिक मार्गदर्शिका". IT Professional. 1 (6): 30–36. doi:10.1109/6294.806902. S2CID 14945518.
- ↑ Les Hatton (2008). "The role of empiricism in improving the reliability of future software". version 1.1.
- ↑ Kan (2003). Metrics and Models in Software Quality Engineering. Addison-Wesley. pp. 316–317. ISBN 978-0-201-72915-3.
- ↑ G.S. Cherf (1992). "An Investigation of the Maintenance and Support Characteristics of Commercial Software". Journal of Software Quality. 1 (3): 147–158. doi:10.1007/bf01720922. ISSN 1573-1367. S2CID 37274091.
- ↑ ISO 26262-3:2011(en) Road vehicles — Functional safety — Part 3: Concept phase. International Standardization Organization.
- ↑ Papadimitriou, Fivos (2012). "भूमध्यसागरीय परिदृश्य परिवर्तनों की जटिलता के मॉडलिंग में कृत्रिम बुद्धिमत्ता". Computers and Electronics in Agriculture. 81: 87–96. doi:10.1016/j.compag.2011.11.009.
- ↑ Papadimitriou, Fivos (2013). "अल्ट्रामेट्रिक टोपोलॉजी के साथ भूमि उपयोग और परिदृश्य जटिलता का गणितीय मॉडलिंग". Journal of Land Use Science. 8 (2): 234–254. doi:10.1080/1747423X.2011.637136. S2CID 121927387.