الفرز الطوبولوجي

إحدى هذه الخوارزميات، التي وصفها كان (1962) لأول مرة ، تعمل عن طريق اختيار الرؤوس بنفس ترتيب الفرز الطوبولوجي النهائي. ^{[ 2 ]} أولًا، يتم إيجاد قائمة بـ "عقد البداية" التي لا تحتوي على حواف واردة، ثم تُضاف إلى مجموعة S؛ يجب أن توجد عقدة واحدة على الأقل من هذا النوع في رسم بياني غير فارغ (محدود) وغير دوري. ثم:

L ← قائمة فارغة تحتوي على العناصر المرتبة S ← مجموعة جميع العقد التي لا تحتوي على حافة واردة طالما أن S ليست فارغة، قم بإزالة العقدة n من S وأضف n إلى L. لكل عقدة m لها حافة e من n إلى m، قم بإزالة الحافة e من الرسم البياني. إذا لم يكن لدى m أي حواف واردة أخرى ، فأضف m إلى S.إذا كان للرسم البياني حواف، فأرجع خطأ ( يحتوي الرسم البياني على دورة واحدة على الأقل)، وإلا فأرجع L (ترتيب طوبولوجي).

إذا كان الرسم البياني عبارة عن رسم بياني موجه غير دوري (DAG )، فسيكون الحل موجودًا في القائمة L (مع أن الحل ليس بالضرورة فريدًا). ​​وإلا، فيجب أن يحتوي الرسم البياني على دورة واحدة على الأقل، وبالتالي يكون الترتيب الطوبولوجي مستحيلاً.

نظرًا لعدم تفرّد الترتيب الناتج، يمكن أن تكون البنية S ببساطة مجموعة أو طابورًا أو مكدسًا. ويختلف الحل المُنشأ باختلاف ترتيب إزالة العقد n من المجموعة S. ويُشكّل أحد أشكال خوارزمية كان، التي تفصل حالات التعادل معجميًا، عنصرًا أساسيًا في خوارزمية كوفمان-غراهام للجدولة المتوازية ورسم المخططات الطبقية .

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

L ← قائمة فارغة تحتوي على العقد المرتبة، طالما توجد عقد بدون علامة دائمة، حدد عقدة غير معلمة n، قم بزيارة ( n ). دالة زيارة (العقدة ن ) إذا كانت ن تحتوي على علامة دائمة، فقم بالخروج إذا كانت ن تحتوي على علامة مؤقتة، ثم توقف (الرسم البياني يحتوي على دورة واحدة على الأقل) ضع علامة مؤقتة على الرقم نلكل عقدة m ذات حافة من n إلى m، قم بزيارة ( m ) ضع علامة دائمة على الحرف ن أضف n إلى رأس L

تُضاف كل عقدة n إلى قائمة المخرجات L بعد النظر في جميع العقد الأخرى التي تعتمد على n (جميع العقد التابعة لـ n في الرسم البياني). تحديدًا، عند إضافة العقدة n ، نضمن أن جميع العقد التي تعتمد على n موجودة بالفعل في قائمة المخرجات L: فقد أُضيفت إلى L إما عن طريق الاستدعاء المتكرر للدالة visit() الذي انتهى قبل استدعاء الدالة visit () ، أو عن طريق استدعاء الدالة visit() الذي بدأ حتى قبل استدعاء الدالة visit () . وبما أن كل حافة وعقدة تُزار مرة واحدة، فإن الخوارزمية تعمل في زمن خطي. هذه الخوارزمية، القائمة على البحث العميق أولًا، هي نفسها التي وصفها كورمن وآخرون (2001) ؛ ^{[ 3 ]} ويبدو أنها وُصفت لأول مرة منشورةً بواسطة تارجان عام 1976. ^{[ 4 ]}

على جهاز ذي وصول عشوائي متوازٍ ، يمكن إنشاء ترتيب طوبولوجي في زمن قدره O ((log n ) ^² ) باستخدام عدد متعدد الحدود من المعالجات، مما يضع المسألة ضمن فئة التعقيد NC² ^{. [ 5 ]} إحدى طرق القيام بذلك هي تربيع مصفوفة التجاور للرسم البياني المعطى بشكل متكرر، عددًا لوغاريتميًا من المرات، باستخدام ضرب المصفوفات min-plus مع تعظيم القيمة بدلًا من تصغيرها. تصف المصفوفة الناتجة أطول مسافات المسارات في الرسم البياني. يؤدي فرز الرؤوس حسب أطوال أطول مساراتها الواردة إلى إنتاج ترتيب طوبولوجي. ^{[ 6 ]}

خوارزمية للفرز الطوبولوجي المتوازي على أجهزة الذاكرة الموزعة تُوازي خوارزمية كان للرسم البياني الموجه غير الدوري (DAG).${\displaystyle G=(V,E)}$[ ^{7 ] على مستوى عالٍ، تقوم} خوارزمية كان بإزالة الرؤوس ذات الدرجة الداخلية 0 بشكل متكرر وإضافتها إلى الترتيب الطوبولوجي بالترتيب الذي أُزيلت به. وبما أن الحواف الخارجة من الرؤوس المُزالة تُزال أيضًا، فستكون هناك مجموعة جديدة من الرؤوس ذات الدرجة الداخلية 0، حيث تُكرر العملية حتى لا يتبقى أي رؤوس. تُنفذ هذه الخوارزمية${\displaystyle D+1}$التكرارات، حيث D هو أطول مسار في G. يمكن تنفيذ كل تكرار بالتوازي، وهي فكرة الخوارزمية التالية.

فيما يلي، يُفترض أن تقسيم الرسم البياني مُخزّن على p عنصر معالجة (PE)، والتي تحمل علامات${\displaystyle 0,\dots ,p-1}$يقوم كل عنصر معالجة (PE) i بتهيئة مجموعة من الرؤوس المحلية${\displaystyle Q_{i}^{1}}$مع درجة داخلية 0، حيث يمثل الفهرس العلوي التكرار الحالي. بما أن جميع الرؤوس في المجموعات المحلية${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$إذا كانت درجة الدخول تساوي صفرًا، أي أنها غير متجاورة، فيمكن ترتيبها بأي ترتيب للحصول على فرز طوبولوجي صحيح. ولتعيين فهرس عام لكل رأس، يتم حساب مجموع بادئة على أحجام${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$لذا، في كل خطوة، هناك${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$تمت إضافة الرؤوس إلى عملية الفرز الطوبولوجي.

في الخطوة الأولى، يقوم PE j بتعيين المؤشرات${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$إلى الرؤوس المحلية في${\displaystyle Q_{j}^{1}}$هذه الرؤوس في${\displaystyle Q_{j}^{1}}$تُزال، بالإضافة إلى حوافها الخارجة المقابلة. لكل حافة خارجية${\displaystyle (u,v)}$مع نقطة النهاية v في وحدة معالجة أخرى${\displaystyle l,j\neq l}$الرسالة${\displaystyle (u,v)}$يتم نشرها على PE l . بعد جميع الرؤوس في${\displaystyle Q_{j}^{1}}$بعد إزالة الرسائل المنشورة، يتم إرسالها إلى وحدة المعالجة المركزية المقابلة لها. كل رسالة${\displaystyle (u,v)}$يتم تحديث درجة الدخول للرأس المحلي v . إذا انخفضت درجة الدخول إلى الصفر، تتم إضافة v إلى${\displaystyle Q_{j}^{2}}$ثم تبدأ الدورة التالية.

في الخطوة k ، يقوم PE j بتعيين المؤشرات${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$، أين ${\displaystyle a_{k-1}}$يمثل العدد الإجمالي للرؤوس التي تمت معالجتها بعد الخطوة ⁠${\displaystyle k-1}$تتكرر هذه العملية حتى لا يتبقى أي رؤوس للمعالجة، وبالتالي${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$فيما يلي نظرة عامة عالية المستوى على برنامج واحد، وبيانات متعددة باستخدام الشفرة الزائفة لهذه الخوارزمية.

لاحظ أن مجموع البادئة للإزاحات المحلية${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$يمكن حسابها بكفاءة بالتوازي.

p عنصر معالجة بمعرفات من 0 إلى p - 1. المدخلات: G = (V, E) DAG، موزعة على عناصر المعالجة، حيث j = 0، ...، p - 1. المخرجات: الترتيب الطوبولوجي لـ G دالة traverseDAGDistributed δ درجة الدخول للرؤوس المحلية V Q = { v ∈ V | δ[ v ] = 0} // جميع الرؤوس ذات درجة الدخول 0 nrOfVerticesProcessed = 0 قم بتنفيذ عملية بناء شاملة باستخدام مجموع البادئات على حجم Q // احصل على الإزاحات والعدد الإجمالي للرؤوس في هذه الخطوة الإزاحة = عدد الرؤوس المعالجة + مجموع (Q i ، من i = 0 إلى j - 1) // j هو فهرس المعالج لكل u في Q localOrder[u] = index++; لكل (u,v) في E، قم بإرسال الرسالة ( u, v ) إلى PE الذي يملك الرأس v، ثم أضف مجموع (|Q i |، من i = 0 إلى p - 1) إلى nrOfVerticesProcessed. قم بتسليم جميع الرسائل إلى جيران الرؤوس في Q استقبال الرسائل للرؤوس المحلية V قم بإزالة جميع الرؤوس في Q لكل رسالة ( u, v ) تم استلامها: إذا كان --δ[v] = 0 أضف v إلى Q طالما أن الحجم الكلي لـ Q أكبر من 0 إرجاع الطلب المحلي

تعتمد تكلفة الاتصال بشكل كبير على تقسيم الرسم البياني المُعطى. أما بالنسبة لوقت التشغيل، فعلى نموذج CRCW-PRAM الذي يسمح بجلب البيانات وإنقاصها في وقت ثابت، تعمل هذه الخوارزمية في${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$، حيث D هو أطول مسار في G و Δ هي الدرجة القصوى. ^{[ 7 ]}