تخطيطات الرسم البياني المستوي

Question

ما هي بعض تقنيات التقليل من تداخل الحافة عند وضع رسم بياني؟ (ويفضل أن تكون مرتبطة بـ GraphViz) هل هناك أي برنامج موجود يمكنه تخطيط رسم بياني بطريقة مستوية؟

التصميم الحالي - http://www.evecakes.com/doodles/master.gif

يبدو القسم الوردي في الركن الأيسر العلوي جيدًا بينما يحتوي القسم الأزرق الفاتح على بعض تداخل الحافة القابلة للتجنب.

Answer 1

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

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

http://rss.acs.unt.edu/rdoc/library/rgraphviz/html/graphvizlayouts.html

امل ان يساعد.

Answer 2

تحتوي مكتبة Java المصدر المفتوحة التالية على اثنين من الخوارزميات التي قد تساعد في وضع الرسوم البيانية المستوية.http://open.trickl.com/trickl-graph/index.html

على وجه الخصوص ، توفر الفئات التالية حلولًا تحليلية للمشكلة:

Chrobakpaynelayout (استنادًا إلى تنفيذ Boost C ++ من قبل آرون وندسور)http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/straight_line_drawing.html

FoldFreelayout (استنادًا إلى التوطين الموزع الخالي من المرساة في شبكات الاستشعار * Nissanka B. Priyantha ، Hari Balakrishnan ، Erik Demaine ، و Seth Teller)

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

لسوء الحظ ، تم إصدار المكتبة للتو ، لذا فهي قصيرة في الوثائق. ومع ذلك ، قد يكون مفيدًا من خلال توفير بعض التعليمات البرمجية الفعلية بدلاً من مجرد نظرية.