الفرز "الطوبولوجي" للرسم البياني مع الدورات

يجب أن يكون العنوان الكامل للمقالة هو التصنيف "الطوبولوجي" المستدام "للرسم البياني مع دورات في O(|V| + |e| log |e|) في الوقت و O(|V|) في الذاكرة دون تكرار ،" ولكن تم إخباري ما هو مبالغة.

إخلاء المسئولية: أنا مبرمج ، لا أخصائي رياضيات ، لذا فإن اللغة غير الدقيقة ممكنة في الأماكن ، والتي يمكنك ويجب عليك ركلها.

جوهر المهمة

سوف أقوم بتحليل صياغة المشكلة التي أريد أن أشاركها في حلها.

الفرز الطوبولوجي هو ترتيب رؤوس رسم بياني موجه موجه يكون فيه كل من الرؤوس التي تخرج منها الحافة يأتي في وقت أبكر من قمة الرأس التي تدخل فيها هذه الحافة. هناك فروقتان مهمتان هنا: يمكن أن يحتوي الرسم البياني على أكثر من طلب واحد ، وهو ينطبق فقط على الرسوم البيانية acyclic . لا يهتم علماء الرياضيات ، ولكن المبرمجين يريدون في بعض الأحيان الحتمية وأكثر من ذلك بقليل "أنا آسف ، لديك دورة هنا ، لن يكون لديك أي فرز."

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

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

وأخيراً ، سأحدد ما أسميه الفرز "الطوبولوجي" إذا كانت هناك دورات في الرسم البياني. هذا هو ترتيب القمم ، الذي يتزامن مع الفرز الطوبولوجي الحقيقي ، إذا تم استبدال كل دورة من الدورات برأس واحد ، وتقع رؤوس الدورة نفسها ، وفقًا لمتطلبات الاستقرار ، بالنسبة إلى بعضها البعض في الترتيب الأصلي.

والآن مع كل هذه القمامة ، سنحاول الإقلاع ، وسنفعل كل ذلك في إطار الوقت والقيود المفروضة على الذاكرة المشار إليها في بداية المنشور.

ابحث عن حل

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

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

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

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


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

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

الجواب

لذلك الحل النهائي:

1. نحن نرقم رؤوس القائمة الأصلية. O(|V|)
2. نقوم بفرز حواف كل قمة وفقًا لعدد الرأس الذي تذهب إليه الحافة. O(|e| log |e|)
3. باستخدام خوارزمية بيرس ، نجد وترقم مكونات اتصال قوي. O(|V|)
4. باستخدام الفرز عن طريق العد ، نقوم بترتيب القمم بناءً على أرقام المكونات المرتبطة بقوة التي تلقوها. O(|V|)

رمز جيثب ، جافا ، المجال العام . تجدر الإشارة إلى أنه من أجل ضمان استقرار الفرز ، يتم تعديل خوارزمية Pierce قليلاً وتتجاوز الرؤوس بالترتيب العكسي.

لكن لماذا ؟؟

والآن الخلفية ، لماذا كل هذا كان مطلوبا. عند تحميل / إلغاء تحميل المكتبات الديناميكية (.so) ، يتعين على glibc أن يقرر أي ترتيب لتهيئة المتغيرات الثابتة. تعتمد المتغيرات على بعضها البعض ، وتعتمد على وظائف مختلفة ، إلخ. بشكل عام ، كل هذا يشكل الرسم البياني الذي توجد به دورات والتي يجب فرزها.

ذات مرة ، تم إشراك رمز دون المستوى الأمثل الذي كان يؤدي مهمة O(n^2) في هذه المهمة. بشكل عام ، لم يزعج هذا أي شخص ، حتى في عام 2012 تم اكتشاف أن الرمز لا يعمل بشكل صحيح وفي بعض الحالات كان مخطئًا.

الرجال القاسيون من ريدهات فكروا وفكروا في بضع دورات أخرى من الأعلى. تم إصلاح حالات المشكلات ، لكن الخوارزمية بدأت تعمل من أجل O(n^3) ، وأصبح هذا ملحوظًا بالفعل وبدأت بعض التطبيقات تستغرق عدة عشرات من الثواني ، والتي كانت خطأ في عام 2013. أيضًا ، اكتشف مؤلف الخطأ الحالات التي خاطئًا فيها الخوارزمية مع O(n^3) . اقترح استخدام خوارزمية Taryan ، على الرغم من أن التصحيح مع التصحيحات لم يتم تصميمه.

ومع مرور الوقت ، تباطأ glibc بلا رحمة وفي عام 2015 كانت هناك محاولة أخرى لإصلاح الخوارزمية . لسوء الحظ ، لم تنجح ، تم اختيار الخوارزمية O(n^2) ، إلى جانب الخلط بين فروع الرسم البياني ، والتي لم يتم تحديد الترتيب بينها.

اليوم هو عام 2019 ، glibc لا يزال يتباطأ. إذا حكمنا على الوقت الذي استغرقته في حل المشكلة ، فإن احتمالات أن أحلها إلى النهاية أقل بكثير من 100٪. يتفاقم هذا الأمر بحقيقة أن الأمور تحدث في C ، دون دعم IDE ، في كود نمط ترميز جنو ، عداء الاختبار المجنون ("إذا كنت ترغب في تشغيل الاختبار مرة أخرى ، فقط احذف ملف .out المقابل"). ولكي يتمكن glibc من إلقاء نظرة على التصحيح الخاص بك ، فأنت بحاجة إلى الاطلاع على إجراء تخصيص حقوق الطبع والنشر ، وإصدار التصحيح بشكل صحيح والشيطان يعرف ماذا. لذلك ، من أجل إزالة مشكلة اختراع خوارزمية تحل المشكلة على الأقل ، تمت كتابة هذا المنشور.