رسم بياني متعدد الطبقات

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
رسم متعدد الطبقات لمخطط موجه غير دوري تم إنتاجه بواسطة Graphviz

الرسم البياني الطبقي أو الرسم البياني الهرمي هو نوع من أنواع الرسم البياني حيث تُرسَم رؤوس الرسم البياني الموجه في صفوف أو طبقات أفقية، وتكون حوافها موجهة نحو الأسفل عمومًا. [ 1 ] [ 2 ] [ 3 ] يُعرف أيضًا باسم الرسم البياني على طريقة سوجياما، نسبةً إلى كوزو سوجياما ، الذي طور هذا الأسلوب لأول مرة. [ 4 ]

الشكل الأمثل للرسم الطبقي هو الرسم المستوي الصاعد ، حيث تكون جميع الحواف موجهة في اتجاه ثابت ولا تتقاطع أي أزواج من الحواف. مع ذلك، غالبًا ما تحتوي الرسوم البيانية على دورات، ويُعدّ تقليل عدد الحواف غير المتسقة الاتجاه مسألة صعبة الحل (NP-hard )، وكذلك تقليل عدد التقاطعات؛ لذا، عادةً ما تُطبّق أنظمة رسم الرسوم البيانية الطبقية سلسلة من الطرق الاستدلالية التي تُقلّل من هذه الأنواع من العيوب في الرسم دون ضمان إيجاد رسم بأقل عدد ممكن من العيوب.

خوارزمية التخطيط

يتم إنشاء رسم بياني متعدد الطبقات في سلسلة من الخطوات:

  • إذا لم يكن الرسم البياني المُدخل رسمًا بيانيًا موجهًا غير دوري ، يتم تحديد مجموعة من الحواف التي يؤدي عكسها إلى جعله غير دوري. يُعد إيجاد أصغر مجموعة ممكنة من الحواف مسألة مجموعة أقواس التغذية الراجعة ، وهي مسألة NP-كاملة ، لذا غالبًا ما تُستخدم هنا طرق استدلالية جشعة بدلًا من خوارزميات التحسين الدقيق. [ 1 ] [ 2 ] [ 3 ] [ 5 ] [ 6 ] [ 7 ] يمكن صياغة الحل الدقيق لهذه المسألة باستخدام البرمجة العددية الصحيحة . [ 3 ] بدلاً من ذلك، إذا كان عدد الحواف المعكوسة صغيرًا جدًا، فيمكن إيجاد هذه الحواف بواسطة خوارزمية قابلة للمعالجة بمعاملات ثابتة . [ 8 ]
  • تُوزَّع رؤوس الرسم البياني الموجه غير الدوري الناتج عن الخطوة الأولى على الطبقات، بحيث ينتقل كل ضلع من طبقة أعلى إلى طبقة أدنى. تهدف هذه المرحلة إلى إنتاج عدد قليل من الطبقات، وعدد قليل من الأضلاع التي تمتد عبر عدد كبير من الطبقات، وتوزيع متوازن للرؤوس على الطبقات. [ 1 ] [ 2 ] [ 3 ] على سبيل المثال، وفقًا لنظرية ميرسكي ، فإن توزيع الرؤوس على الطبقات بناءً على طول أطول مسار يبدأ من كل رأس يُنتج توزيعًا بأقل عدد ممكن من الطبقات. [ 1 ] [ 3 ] يمكن استخدام خوارزمية كوفمان-غراهام لإيجاد توزيع للطبقات بحد أقصى مُحدد مسبقًا لعدد الرؤوس في كل طبقة، مع تقليل عدد الطبقات تقريبًا وفقًا لهذا القيد. [ 1 ] [ 2 ] [ 3 ] يُعد تقليل عرض أوسع طبقة مسألة صعبة الحل (NP-hard)، ولكن يمكن حلها باستخدام خوارزمية التفرع والقطع أو تقريبها بطريقة استدلالية. [ 3 ] بدلاً من ذلك، يمكن حل مشكلة تقليل العدد الإجمالي للطبقات التي تغطيها الحواف (دون أي قيود على عدد الرؤوس في كل طبقة) باستخدام البرمجة الخطية . [ 9 ] يمكن استخدام إجراءات البرمجة العددية الصحيحة ، على الرغم من أنها تستغرق وقتًا أطول، لدمج تقليل طول الحافة مع وضع قيود على عدد الرؤوس في كل مستوى. [ 10 ]
  • يتم استبدال الحواف التي تمتد عبر طبقات متعددة بمسارات من رؤوس وهمية، بحيث تربط كل حافة في الرسم البياني الموسع، بعد هذه الخطوة، رأسين على طبقات متجاورة من الرسم. [ 1 ] [ 2 ]
  • كخطوة اختيارية، يمكن فرض طبقة من رؤوس تركيز الحواف (أو نقاط التقاء الحواف) بين طبقتين موجودتين من الرؤوس، مما يقلل من كثافة الحواف عن طريق استبدال الرسوم البيانية الفرعية الثنائية الكاملة بنجوم من خلال هذه الرؤوس المركزة للحواف. [ 3 ] [ 11 ] [ 12 ]
  • يتم تبديل مواقع الرؤوس داخل كل طبقة في محاولة لتقليل عدد التقاطعات بين الحواف التي تربطها بالطبقة السابقة. [ 1 ] [ 2 ] [ 3 ] يُعدّ إيجاد الحد الأدنى لعدد التقاطعات أو إيجاد أكبر مجموعة من الحواف الخالية من التقاطعات مسألةً من نوع NP-complete، حتى عند ترتيب طبقة واحدة في كل مرة بهذه الطريقة، [ 13 ] [ 14 ] لذا، من الشائع اللجوء إلى طرق استدلالية، مثل وضع كل رأس في موضع يُحدد بإيجاد متوسط ​​أو وسيط مواضع جيرانه في المستوى السابق، ثم تبديل الأزواج المتجاورة طالما أن ذلك يُحسّن عدد التقاطعات. [ 1 ] [ 2 ] [ 9 ] [ 14 ] [ 15 ] بدلاً من ذلك، يمكن اختيار ترتيب الرؤوس في طبقة واحدة في كل مرة باستخدام خوارزمية قابلة للمعالجة بمعاملات ثابتة في عدد التقاطعات بينها وبين الطبقة السابقة. [ 3 ] [ 16 ]
  • يُخصَّص لكل رأس إحداثية ضمن طبقته، بما يتوافق مع التبديل المحسوب في الخطوة السابقة. [ 1 ] [ 2 ] تشمل الاعتبارات في هذه الخطوة وضع عقد وهمية على خط بين جارتيها لمنع الانحناءات غير الضرورية ، ووضع كل رأس في موضع مركزي بالنسبة لجيرانه. [ 3 ] اقترح سوجياما في عمله الأصلي صياغة برمجة تربيعية لهذه الخطوة؛ بينما تستغرق طريقة براندس وكوبف اللاحقة وقتًا خطيًا وتضمن انحناءين على الأكثر لكل حافة. ​​[ 3 ] [ 17 ]
  • تُعاد الحواف التي عُكست في الخطوة الأولى من الخوارزمية إلى اتجاهاتها الأصلية، وتُزال الرؤوس الوهمية من الرسم البياني، ثم تُرسَم الرؤوس والحواف. ولتجنب التقاطعات بين الرؤوس والحواف، يمكن رسم الحواف التي تمتد عبر طبقات متعددة من الرسم على شكل سلاسل مضلعة أو منحنيات سبلاين تمر عبر كل موضع من المواضع المخصصة للرؤوس الوهمية على طول الحافة. ​​[ 1 ] [ 2 ] [ 9 ]

التطبيقات

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

تُنتج أداة "النقطة" في برنامج Graphviz رسوماتٍ متعددة الطبقات. [ 9 ] كما تتضمن Microsoft Automatic Graph Layout [ 19 ] و Tulip خوارزميةً لرسم الرسوم البيانية متعددة الطبقات . [ 20 ]

الاختلافات

على الرغم من أن خوارزميات رسم الرسوم البيانية الطبقية تُرسَم عادةً برؤوس مرتبة في صفوف وحواف تمتد من أعلى إلى أسفل، إلا أنه يمكن رسمها برؤوس مرتبة في أعمدة وحواف تمتد من اليسار إلى اليمين. [ 21 ] وقد طُبِّقَ الإطار الخوارزمي نفسه على التخطيطات الشعاعية التي تُرتَّب فيها الرسوم البيانية في دوائر متحدة المركز حول عقدة بداية معينة [ 3 ] [ 22 ] ، وعلى الرسومات الطبقية ثلاثية الأبعاد للرسوم البيانية. [ 3 ] [ 23 ]

في رسومات المخططات الطبقية ذات الحواف الطويلة الكثيرة، يمكن تقليل ازدحام الحواف بتجميع مجموعات الحواف في حزم وتوجيهها معًا عبر نفس مجموعة الرؤوس الوهمية. [ 24 ] وبالمثل، بالنسبة للرسومات التي تحتوي على العديد من الحواف المتقاطعة بين أزواج من الطبقات المتتالية، يمكن تجميع الحواف في المخططات الفرعية الثنائية القصوى في حزم متصلة. [ 25 ]

يمكن إنشاء الرسومات التي تُرتّب فيها الرؤوس في طبقات باستخدام خوارزميات لا تتبع إطار عمل سوجياما. على سبيل المثال، من الممكن تحديد ما إذا كان للرسم البياني غير الموجّه رسمٌ يحتوي على k تقاطعًا على الأكثر، باستخدام h طبقة، في وقت متعدد الحدود لأي اختيار ثابت لـ k و h ، وذلك بالاعتماد على حقيقة أن الرسوم البيانية التي تحتوي على رسومات من هذا النوع لها عرض مسار محدود . [ 26 ]

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

مراجع

  1. 1 2 3 4 5 6 7 8 9 10 دي باتيستا، جوزيبي؛ إيدز، بيتر ؛ تاماسيا، روبرتو ؛ توليس، يوانيس ج. (1998)، "الرسومات الطبقية للرسوم البيانية الموجهة"، رسم الرسوم البيانية: خوارزميات لتصور الرسوم البيانية ، برنتيس هول ، ص 265-302 ، ISBN  978-0-13-301615-4.
  2. 1 2 3 4 5 6 7 8 9 باسترت، أوليفر؛ ماتوسزوسكي، كريستيان (2001)، "الرسومات الطبقية للرسوم البيانية الموجهة"، في كوفمان، مايكل؛ فاغنر، دوروثيا (محرران)، رسم الرسوم البيانية: الأساليب والنماذج ، سلسلة محاضرات في علوم الحاسوب ، المجلد 2025، سبرينغر-فيرلاغ، الصفحات 87-120 ، doi : 10.1007/3-540-44969-8_5 ، ISBN   978-3-540-42062-0.
  3. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 هيلي، باتريك؛ نيكولوف، نيكولا س. (2014)، "رسم بياني هرمي"، في تاماسيا ، روبرتو (محرر)، دليل الرسم البياني والتصور ، مطبعة سي آر سي، ص 409-453 .
  4. ↑ سوجياما، كوزو؛ تاغاوا، شوجيرو؛ تودا، ميتسوهيكو (1981)، "طرق الفهم البصري لهياكل الأنظمة الهرمية"، معاملات IEEE في الأنظمة والإنسان وعلم التحكم الآلي ، SMC-11 (2): 109-125 ، Bibcode : 1981ITSMC..11..109S ، doi : 10.1109/TSMC.1981.4308636 ، MR 0611436 ، S2CID 8367756  .
  5. ↑ بيرغر، ب .؛ شور، ب. (1990)، "خوارزميات تقريبية لمسألة الرسم البياني الفرعي غير الدوري الأقصى"، وقائع الندوة الأولى لجمعية آلات الحوسبة والجمعية الدولية للرياضيات التطبيقية حول الخوارزميات المنفصلة (SODA'90) ، الصفحات 236-243 ، ISBN  978-0-89871-251-3.
  6. ↑ إيدز، ب .؛ لين، إكس.؛ سميث، دبليو إف (1993)، "طريقة استدلالية سريعة وفعالة لمشكلة مجموعة أقواس التغذية الراجعة" ، رسائل معالجة المعلومات ، 47 (6): 319-323 ، doi : 10.1016/0020-0190(93)90079-O.
  7. ↑ إيدز، ب .؛ لين، إكس. (1995)، "طريقة استدلالية جديدة لمسألة مجموعة أقواس التغذية الراجعة"، المجلة الأسترالية للتوافقية ، 12 : 15-26.
  8. ↑ تشين، جيانر؛ ليو، يانغ؛ لو، سونغجيان؛ أوسوليفان، باري؛ رازغون، إيغور (2008)، "خوارزمية ذات معلمات ثابتة لمسألة مجموعة رؤوس التغذية الراجعة الموجهة"، مجلة ACM ، 55 (5): 1، doi : 10.1145/1411509.1411511 ، S2CID 1547510 .
  9. 1 2 3 4 غانسنر، إي آر؛ كوتسوفيوس، إي؛ نورث، إس سي؛ فو، كيه-بي (1993)، "تقنية لرسم الرسوم البيانية الموجهة"، معاملات IEEE في هندسة البرمجيات ، 19 (3): 214-230 ، Bibcode : 1993ITSEn..19..214G ، doi : 10.1109/32.221135.
  10. ↑ هيلي، باتريك؛ نيكولوف، نيكولا س. (2002)، "كيفية إنشاء طبقات في رسم بياني موجه غير دوري"، رسم الرسوم البيانية: الندوة الدولية التاسعة، GD 2001 فيينا، النمسا، 23-26 سبتمبر 2001، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 2265، سبرينغر-فيرلاغ، الصفحات 16-30 ، doi : 10.1007/3-540-45848-4_2 ، ISBN   978-3-540-43309-5، MR 1962416 .
  11. ↑ نيوبري، إف جيه (1989)، "تركيز الحواف: طريقة لتجميع الرسوم البيانية الموجهة"، وقائع ورشة العمل الدولية الثانية حول إدارة تكوين البرمجيات (SCM '89)، برينستون، نيو جيرسي، الولايات المتحدة الأمريكية ، رابطة آلات الحوسبة، الصفحات 76-85 ، doi : 10.1145/72910.73350 ، ISBN  0-89791-334-5، S2CID 195722969 .
  12. ↑ إبستين، ديفيد ؛ جودريتش، مايكل ت .؛ مينغ، جيريمي يو (2007)، "الرسومات الطبقية المتداخلة"، في باتش، يانوس (محرر)، الرسومات الطبقية المتداخلة ، سلسلة محاضرات في علوم الحاسوب، المجلد 47 (الطبعة 3383 )، سبرينغر-فيرلاغ، الصفحات 184-194 ، arXiv : cs.CG/0507051 ، doi : 10.1007/s00453-006-0159-8 ، S2CID 1169    .
  13. ↑ إيدز، بيتر ؛ وايتسايدز، سو (1994)، "رسم الرسوم البيانية في طبقتين"، علوم الحاسوب النظرية ، 131 (2): 361-374 ، doi : 10.1016/0304-3975(94)90179-1.
  14. 1 2 إيدز، بيتر ؛ وورمالد، نيكولاس سي. (1994)، "تقاطعات الحواف في رسومات الرسوم البيانية ثنائية الأجزاء"، Algorithmica ، 11 (4): 379-403 ، doi : 10.1007/BF01187020 ، S2CID 22476033 .
  15. ↑ ماكينين، إي. (1990)، "تجارب على رسم الرسوم البيانية الهرمية ذات المستويين"، المجلة الدولية للرياضيات الحاسوبية ، 36 ( 3-4 ): 175-181 ، doi : 10.1080/00207169008803921.
  16. ↑ دوجيموفيتش، فيدا ؛ فيرناو، هينينغ؛ كوفمان، مايكل (2008)، "إعادة النظر في خوارزميات المعلمات الثابتة لتقليل التقاطع أحادي الجانب"، مجلة الخوارزميات المنفصلة ، ​​6 (2): 313-323 ، doi : 10.1016/j.jda.2006.12.008 ، MR 2418986 .
  17. ^ براندز، أولريك ؛ كوبف، بوريس (2002)، “تعيين الإحداثيات الأفقية السريعة والبسيطة”، رسم بياني (فيينا، 2001) ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد. 2265، برلين: سبرينغر، الصفحات من 31 إلى 44، دوى : 10.1007/3-540-45848-4_3 ، ISBN   978-3-540-43309-5، MR 1962417 .
  18. ↑ إيجلسبيرجر، ماركوس؛ سيبنهالر، مارتن؛ كوفمان، مايكل (2005)، "تنفيذ فعال لخوارزمية سوجياما لرسم الرسوم البيانية متعددة الطبقات"، رسم الرسوم البيانية، الندوة الدولية الثانية عشرة، GD 2004، نيويورك، نيويورك، الولايات المتحدة الأمريكية، 29 سبتمبر - 2 أكتوبر 2004، أوراق مختارة منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 3383، سبرينغر-فيرلاغ، الصفحات 155-166 ، doi : 10.1007/978-3-540-31843-9_17 ، ISBN   978-3-540-24528-5.
  19. ↑ ناخمانسون، ليف؛ روبرتسون، جورج؛ لي، بونغشين (2008). "رسم الرسوم البيانية باستخدام GLEE". في: هونغ، سيوك-هي ؛ نيشيزيكي، تاكاو ؛ كوان، وو (محررون). رسم الرسوم البيانية، الندوة الدولية الخامسة عشرة، GD 2007، سيدني، أستراليا، 24-26 سبتمبر 2007، أوراق منقحة . سلسلة محاضرات في علوم الحاسوب. المجلد 4875. سبرينغر-فيرلاغ. الصفحات 389-394 . doi : 10.1007/978-3-540-77537-9_38 . ISBN   978-3-540-77536-2..
  20. ^ ديفيد أوبر (2004)، “توليب – إطار تصور رسم بياني ضخم”، في مايكل جونجر؛ Mutzel، Petra (eds.)، برنامج الرسم البياني ، Springer-Verlag، ISBN 978-3-540-00881-1.
  21. ↑ بابورين، دانيل إي. (2002)، "بعض التعديلات على منهج سوجياما"، رسم المخططات، الندوة الدولية العاشرة، GD 2002، إرفاين، كاليفورنيا، الولايات المتحدة الأمريكية، 26-28 أغسطس 2002، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 2528، سبرينغر، الصفحات 366-367 ، doi : 10.1007/3-540-36151-0_36 ، ISBN   978-3-540-00158-4.
  22. ↑ باخماير، كريستيان (2007)، "تكييف شعاعي لإطار سوجياما لتصوير المعلومات الهرمية"، معاملات IEEE في التصور ورسومات الحاسوب ، 13 (3): 583-594 ، Bibcode : 2007ITVCG..13..583B ، doi : 10.1109/TVCG.2007.1000 ، PMID 17356223 ، S2CID 9852297  .
  23. ↑ هونغ، سيوك-هي ؛ نيكولوف، نيكولا س. (2005)، "رسومات متعددة الطبقات للرسوم البيانية الموجهة في ثلاثة أبعاد"، وقائع ندوة آسيا والمحيط الهادئ لعام 2005 حول تصور المعلومات (APVis '05) ، مؤتمرات البحث والممارسة في تكنولوجيا المعلومات، المجلد 45، الصفحات 69-74 ، ISBN   978-1-920682-27-9.
  24. ↑ بوبيريف، سيرجي؛ ناخمانسون، ليف؛ كوفمان، مايكل (2011)، "تحسين تخطيطات الرسوم البيانية متعددة الطبقات باستخدام تجميع الحواف"، رسم الرسوم البيانية، الندوة الدولية الثامنة عشرة، GD 2010، كونستانز، ألمانيا، 21-24 سبتمبر 2010، أوراق مختارة منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 6502، سبرينغر، الصفحات 329-340 ، doi : 10.1007/978-3-642-18469-7_30 ، ISBN   978-3-642-18468-0.
  25. ↑ إبستين، ديفيد ؛ جودريتش، مايكل ت .؛ مينغ، جيريمي يو (2007)، "الرسومات الطبقية المتداخلة"، Algorithmica ، 47 (4): 439-452 ، arXiv : cs/0507051 ، doi : 10.1007/s00453-006-0159-8 ، S2CID 1169 .
  26. ↑ دوجيموفيتش، ف .؛ فيلوز، م. ر.؛ كيتشينغ، م.؛ ليوتا، ج.؛ مكارتين، س.؛ نيشيمورا، ن.؛ راغدي، ب.؛ روزاموند، ف.؛ وايتسايدز، س. (2008)، "حول التعقيد البارامتري لرسم المخططات الطبقية"، Algorithmica ، 52 (2): 267-292 ، doi : 10.1007/s00453-007-9151-1 ، S2CID 2298634 .
  27. ↑ كول، ريتشارد (2001). "التخطيط الآلي لشبكات المفاهيم باستخدام المخططات الطبقية والمخططات التراكمية". وقائع المؤتمر الأسترالي الرابع والعشرين لعلوم الحاسوب. ACSC 2001. المجلد 23. الصفحات 47-53 . doi : 10.1109/ACSC.2001.906622 . ISBN   0-7695-0963-0. S2CID 7143873 . 
  28. ↑ بينو شفيكوفسكي؛ بيتر أويتز وستانلي فيلدز (2000). "شبكة من تفاعلات البروتين-بروتين في الخميرة". مجلة نيتشر للتكنولوجيا الحيوية . 18 (12): 1257-1261 . Bibcode : 2000NatBi..18.1257S . doi : 10.1038/82360 . PMID: 11101803. S2CID : 3009359 .