كيفية تحويل الرسم البياني الحلقي الموجه (DAG) إلى شجرة

Question

لقد كنت أبحث عن أمثلة C# لتحويل DAG إلى شجرة.

هل لدى أي شخص أمثلة أو مؤشرات في الاتجاه الصحيح؟

تحديث التوضيح

لدي رسم بياني يحتوي على قائمة بالوحدات النمطية التي يتعين على تطبيقي تحميلها.تحتوي كل وحدة على قائمة بالوحدات التي تعتمد عليها.على سبيل المثال، إليك وحداتي A وBC وD وE

• A ليس لديه تبعيات
• يعتمد B على A وC وE
• C يعتمد على A
• د يعتمد على أ
• E يعتمد على C و A

أريد حل التبعيات وإنشاء شجرة تبدو هكذا ...

--أ

--+--ب

-----+--ج

---------+--د

--+--ه

الترتيب الطوبولوجي

شكرا على المعلومات، إذا قمت بإجراء فرز طوبولوجي وعكس الإخراج سيكون لدي الترتيب التالي

• أ
• ب
• ج
• د
• ه

أرغب في الحفاظ على البنية الهرمية بحيث يتم تحميل الوحدات النمطية الخاصة بي في السياق الصحيح، على سبيل المثال...يجب أن تكون الوحدة E في نفس الحاوية مثل B

شكرًا

روهان

Answer 1

هناك الإجابة النظرية للرسم البياني وإجابة المبرمج على ذلك.أفترض أنك تستطيع التعامل مع جزء المبرمجين بنفسك.للإجابة النظرية الرسم البياني:

• DAG عبارة عن مجموعة من الوحدات حيث لا يحدث أبدًا أن A يحتاج إلى B، وفي الوقت نفسه، يحتاج B (أو إحدى الوحدات التي يحتاجها B) إلى A، في الوحدات النمطية:لا التبعية الدائرية.لقد رأيت حدوث تبعيات دائرية (ابحث في منتديات Gentoo للحصول على أمثلة)، لذلك لا يمكنك حتى أن تكون متأكدًا بنسبة 100% من أن لديك DAG، ولكن لنفترض أنك تمتلكه.ليس من الصعب جدًا التحقق من التبعيات الدائرية، لذا أنصحك بالقيام بذلك في مكان ما في مُحمل الوحدة الخاص بك.
• في الشجرة، الشيء الذي لا يمكن أن يحدث أبدًا هو أن A يعتمد على B وC وأن كلاً من B وC يعتمدان على D (الماسة)، لكن هذا يمكن أن يحدث في DAG.
• أيضًا، تحتوي الشجرة على عقدة جذر واحدة بالضبط، ولكن يمكن أن تحتوي DAG على عقد "جذر" متعددة (أي.الوحدات التي لا يعتمد عليها شيء).على سبيل المثال، برنامج مثل GIMP، سيكون برنامج GIMP هو العقدة الجذرية لمجموعة الوحدات، ولكن بالنسبة لـ GENTOO، فإن أي برنامج يحتوي على واجهة المستخدم الرسومية تقريبًا هو عقدة "جذر"، في حين أن المكتبات وما إلى ذلك هي تبعيات لها.(أي.كلا من كونكيورر و كمايل يعتمدان على Qtlib، لكن لا شيء يعتمد على كونكيورر، ولا شيء يعتمد على كميل)

الإجابة النظرية للرسم البياني على سؤالك، كما أشار آخرون، هي أنه لا يمكن تحويل DAG إلى شجرة، في حين أن كل شجرة هي DAG.

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

A depends on B and C
B depends on D and E
C depends on D and F

لا أستطيع أن أعرض هذا كشجرة فنية ASCII، لسبب بسيط وهو أنه لا يمكن تحويلها إلى شجرة.ومع ذلك، إذا كنت تريد إظهار ما يعتمد عليه A، فيمكنك إظهار هذا:

A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F

كما ترون، تحصل على إدخالات مزدوجة في شجرتك - في هذه الحالة "فقط" D ولكن إذا قمت بـ "توسيع الكل" على شجرة Gentoo، فأنا أضمن لك أن شجرتك ستحتوي على 1000 مرة على الأقل من كمية العقد هناك وحدات.(هناك ما لا يقل عن 100 حزمة تعتمد على Qt، لذا فإن كل ما تعتمد عليه Qt سيكون موجودًا 100 مرة على الأقل في الشجرة).

إذا كان لديك شجرة "كبيرة" أو "معقدة"، فقد يكون من الأفضل توسيع الشجرة ديناميكيًا، وليس مقدمًا، وإلا فقد تكون لديك عملية تستهلك قدرًا كبيرًا من الذاكرة.

عيب الشجرة أعلاه هو أنه إذا قمت بالنقر فوق فتح B، ثم D، فإنك ترى أن A وB يعتمدان على D، ولكن ليس أن C أيضًا يعتمد على D.ومع ذلك، اعتمادًا على موقفك، قد لا يكون هذا مهمًا على الإطلاق - إذا احتفظت بقائمة من الوحدات المحملة، عند تحميل C، سترى أنك قمت بتحميل D بالفعل، ولا يهم أنه لم يتم تحميله لـ C، لكن بالنسبة لـ ب.لقد تم تحميله، هذا كل ما يهم.إذا قمت بصيانة ما يعتمد بشكل مباشر على وحدة معينة ديناميكيًا، فيمكنك التعامل مع المشكلة المعاكسة (التفريغ) أيضًا.

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

حظ سعيد!

Answer 2

DAG والشجرة ليسا نفس الشيء رياضياً.وبالتالي، فإن أي تحويل يجلب الغموض.الشجرة بحكم التعريف ليس لها دورات أو فترة.

Answer 3

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

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

Answer 4

يعتمد الأمر كثيرًا على كيفية تمثيل DAG الخاص بك.على سبيل المثال، يمكن أن تكون مصفوفة مجاورة (A[i,j] = 1 إذا كانت هناك حافة من العقدة i إلى العقدة j، وإلا 0)، أو كنظام من المؤشرات، أو كمصفوفة من العقد ومصفوفة من حواف....

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

Answer 5

لا يمكنك القيام بذلك إلا إذا كانت جميع الأشجار الفرعية تحتوي على عقدة جذر واحدة.