تسلسل الرسم البياني

Question

أنا أبحث عن خوارزمية بسيطة "لإجراء تسلسل" للرسم البياني الموجه.على وجه الخصوص، لدي مجموعة من الملفات ذات الترابط في ترتيب تنفيذها، وأريد العثور على الترتيب الصحيح في وقت الترجمة.أعلم أنه يجب أن يكون أمرًا شائعًا إلى حد ما - يقوم المترجمون بذلك طوال الوقت - ولكن Google-fu الخاص بي كان ضعيفًا اليوم.ما هي خوارزمية "الذهاب إلى" لهذا؟

Answer 1

الترتيب الطوبولوجي (من ويكيبيديا):

في نظرية الرسم البياني ، يعد الترتيب الطوبولوجي أو الترتيب الطوبولوجي للرسم البياني الموجه (DAG) ترتيبًا خطيًا لعقده تأتي كل عقدة قبل جميع العقد التي لديها حواف صادرة.كل 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

أتوقع أن الأدوات التي تحتاج إلى ذلك ببساطة تمشي على الشجرة بطريقة العمق أولاً وعندما تصطدم بورقة، ما عليك سوى معالجتها (على سبيل المثال.ترجمة) وإزالتها من الرسم البياني (أو وضع علامة عليها كمعالجة، ومعاملة العقد مع معالجة جميع الأوراق كأوراق).

طالما أنه DAG، يجب أن تكون هذه المسيرة البسيطة القائمة على المكدس تافهة.

Answer 3

إذا كان الرسم البياني يحتوي على دورات، فكيف يمكن وجود أوامر تنفيذ مسموحة لملفاتك؟يبدو لي أنه إذا كان الرسم البياني يحتوي على دورات ، فلن يكون لديك حل ، ويتم الإبلاغ عنه بشكل صحيح بواسطة الخوارزمية أعلاه.

Answer 4

لقد توصلت إلى خوارزمية متكررة ساذجة إلى حد ما (الكود الكاذب):

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);

أكبر مشكلة في هذا هو أنه ليس لديه القدرة على اكتشاف التبعيات الدورية - يمكن أن يدخل في عودية لا نهائية (أي تجاوز سعة المكدس؛-p).الطريقة الوحيدة التي يمكنني رؤيتها هي قلب الخوارزمية العودية إلى خوارزمية تفاعلية باستخدام مكدس يدوي، والتحقق يدويًا من المكدس بحثًا عن العناصر المتكررة.

أي شخص لديه شيء أفضل؟