گراف لایه‌بندی شده
گراف لایه بندی شده گراف همبندی است که راس‌های آن به مجموعه‌های L۰ تا Ln تقسیم‌بندی شده است. هر یال وزن صحیح نا منفی دارد و فقط رأس‌های لایه‌های پی در پی را به هم متصل می‌کند. عرض گراف برابر ماکسیموم تعداد رأس‌های هر لایه هست.
شیوه لایه بندی کردن گراف[ویرایش]
در زیر الگوریتم‌هایی برای لایه بندی کردن یک گراف توضیح داده شده. اولین الگوریتم برای برای نمایش رابطه‌های وابسته در یک شبکه مناسب می‌باشد.
Sugiyama Method[ویرایش]
- قدم اول:از بین بردن دورها
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یال‌ها
- قدم دوم:لایه بندی کردن
تقسیم‌بندی کردن رأس‌ها به تعدادی لایه
- قدم سوم:مرتب کردن راس‌ها
در هر لایه از رأس‌ها آن‌ها را به صورت خطی مرتب کنید
- قدم چهارم:نسبت دادن مختصات
- به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید
الگوریتم زیر از الگوریتم بالا نتیجه گرفته شده است.
۳D Layered Digraph[ویرایش]
- قدم اول:از بین بردن دورها
از بین بردن همه دورهای جهت دار با برگرداندن جهت بعضی از یال‌ها
- قدم دوم:لایه بندی کردن
تقسیم‌بندی کردن رأس‌ها به تعدادی لایه
- قدم سوم:تقسیم‌بندی راس‌ها
در هر لایه رأس‌ها را به دو گروه تقسیم می‌کنیم
- قدم جهارم:مرتب کردن راس‌ها
در هر گروه در هر لایه رأس‌ها را به صورت خطی مرتب می‌کنیم
- قدم پنجم:نسبت دادن مختصات به هر راس یک مختصه نسبت دهید و با استفاده از آن شکل یال بین هر دو راس را محاسبه نمایید
این الگوریتم قدم سوم را شرح می‌دهد
الگوریتم تقسیم‌بندی رأس‌ها[ویرایش]
Ai ← φ
Bi ← φ
for all v ∈ Li do
if |N+(v) ∩ Ai−1|> |N+(v) ∩ Bi−1| then
Ai ← Ai ∪ {v}
else
Bi ← Bi ∪ {v}
end if
end for
if |Ai|> |Bi| then
X is a synonym of A and x is a synonym of B
else
X is a synonym of B and x is a synonym of A
end if
while (|Li| is even and |Xi|> |xi|) or (|Li| is odd
and |Xi|> |xi| + 1) do
move vertex v ∈ Xi with the minimum |N+(v)∩
Xi−1| − |N+(v) ∩ xi−1| to xi
end while
منابع[ویرایش]
- https://ics.uci.edu/~eppstein/junkyard/thickness/
- www.cs.usyd.edu.au/~visual/comp4048/slides03.ppt
- Sugiyama, K.، Tagawa, S. & Toda, M. (1981)، ‘Methods
for visual understanding of hierarchical system structures’، IEEE Transaction on Systems, Man, and Cybernetics 11(2)، 109–125.