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

Question

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

Answer 1

Topological Sort (विकिपीडिया से):

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

छद्म कोड:

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) 

Answer 2

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

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

Answer 3

मैं एक काफी अनुभवहीन पुनरावर्ती एल्गोरिदम (स्यूडोकोड) के साथ आ गया है:

Map<Object, List<Object>> source; // map of each object to its dependency list 
List<Object> 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); 

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

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

Answer 4

ग्राफ चक्र होते हैं, तो आपकी फ़ाइलों के लिए कैसे वहाँ की अनुमति दी मौजूद कर सकते हैं निष्पादन के आदेश? मुझे ऐसा लगता है कि यदि ग्राफ में चक्र होते हैं, तो आपके पास कोई समाधान नहीं है, और यह उपरोक्त एल्गोरिदम द्वारा सही ढंग से रिपोर्ट किया गया है।