ग्राफ क्रमबद्धता

मैं एक निर्देशित ग्राफ 'serialize' करने के लिए एक सरल एल्गोरिदम खोज रहा हूँ। विशेष रूप से मुझे अपने निष्पादन आदेश पर परस्पर निर्भरता वाली फ़ाइलों का एक सेट मिला है, और मैं संकलन समय पर सही क्रम खोजना चाहता हूं। मुझे पता है कि यह करना काफी आम बात होनी चाहिए - कंपलर हर समय ऐसा करते हैं - लेकिन मेरा google-fu आज कमजोर रहा है। इसके लिए 'जाने-जाने' एल्गोरिदम क्या है?

0
ro fr bn

3 उत्तर

मैं एक काफी बेवकूफ रिकर्सिव एल्गोरिदम (छद्म कोड) के साथ आया हूँ:

Map> source; // map of each object to its dependency list List dest; // destination list function resolve(a): if (dest.contains(a)) return; foreach (b in source[a]): resolve(b); dest.add(a); foreach (a in source): resolve(a); 

इसके साथ सबसे बड़ी समस्या यह है कि इसमें चक्रीय निर्भरता का पता लगाने की कोई क्षमता नहीं है - यह अनंत रिकर्सन (यानी स्टैक ओवरफ्लो; -पी) में जा सकती है। मैं देख सकता हूं कि चारों ओर एकमात्र तरीका रिकर्सिव एल्गोरिदम को मैन्युअल स्टैक के साथ एक इंटरैक्टिव में फ़्लिप करना होगा, और मैन्युअल रूप से दोहराए गए तत्वों के लिए स्टैक की जांच करना होगा।

किसी के पास कुछ बेहतर है?

0
जोड़ा
एक फोरैच के बजाय थोड़ी देर के लिए उपयोग करते हैं, डेटा को घुमाने वाले दो पॉइंटर्स को बनाए रखते हैं, एक अग्रणी जो डबल कदम और पीछे की ओर एक पीछे है। अग्रणी सूचक Acutal संकल्पों को संभालता है और यदि यह कभी पीछे पीछे सूचक को गोद लेता है तो एक चक्र होता है।
जोड़ा लेखक Tenderdude, स्रोत

Topological Sort (From Wikipedia):

ग्राफ सिद्धांत में, एक स्थलीय प्रकार या   निर्देशित के स्थलीय आदेश   विश्वकोश ग्राफ (डीएजी) एक रैखिक है   अपने नोड्स का क्रम जिसमें प्रत्येक   नोड सभी नोड्स से पहले आता है   इसमें आउटबाउंड किनारों हैं। प्रत्येक डीएजी है   एक या अधिक टोपोलॉजिकल प्रकार।

छद्म कोड:

L ? Empty list where we put the sorted elements
Q ? Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)
0
जोड़ा
हाँ, कृपया स्रोत उद्धृत करें
जोड़ा लेखक Jason S, स्रोत
एह ... विकिपीडिया से सीधे कॉपी किया गया?
जोड़ा लेखक Benjol, स्रोत
धन्यवाद। मुझे इस तथ्य का उपयोग करने में मदद मिली कि निर्भरता पेड़ को इस विधि का उपयोग करके हल किया जा सकता है। :-)
जोड़ा लेखक Shamasis Bhattacharya, स्रोत

मैं उन उपकरणों की अपेक्षा करता हूं जिनकी आवश्यकता है कि पेड़ को गहराई से पहले तरीके से चलें और जब वे एक पत्ते को दबाते हैं, तो बस इसे संसाधित करें (उदाहरण के लिए संकलित करें) और इसे ग्राफ से हटा दें (या इसे संसाधित के रूप में चिह्नित करें, और सभी पत्तियों के साथ नोड्स का इलाज करें पत्तियों के रूप में संसाधित)।

जब तक यह एक डीएजी है, तब तक यह सरल ढेर-आधारित चलना तुच्छ होना चाहिए।

0
जोड़ा
हां, इस तरह आप इसे करते हैं। इसे गहराई से पहली खोज (डीएफएस) कहा जाता है। और जब तक आप निश्चित नहीं हैं कि आपके पास एक डीएजी है, तो आप पिछली किनारों के लिए जरूरी है, अन्यथा एक चक्र आपको अनंत लूप में भेज देगा।
जोड़ा लेखक sleske, स्रोत