Wednesday, October 27, 2010

Граф байрлуулах алгоритм

Зарим веб хуудсууд дээр гоё гоё графууд байрлуулсан байдгийг мэдэж байгаа биз ээ. Жишээ нь социал граф байгуулах, ямар нэгэн юмнуудын холбоосыг гаргах гэх мэтчилэн үед ихээр хэрэглэдэг. Энэ миний найз, тэрний найз тэр гээд л яваад өгнө. Мөн нарны аймаг ч байж болох юм байна. Тэр галактикийн тэр од эсвэл гариг. Энэ мэтчилэн граф байгуулах нь өгөгдлийг илүү цэвэрхэн эвтэйхэн харагдуулдаг.


Миний саяхны даалгавар нь энэхүү графыг байрлуулах байсан учраас хэн нэгэнд хэрэг болж магадгүй гээд өөрийнхөө судалсан зүйлүүдийг орууллаа.

Графыг байрлуулах хэд хэдэн арга байдаг юм билээ.
1. Ортогональ байрлуулах. Энэ нь зангилаанууд нөгөөдөх рүүгээ тэгш өнцөг үүсгэж холбох, тооны дэвтрийн нүднүүд дээр байрлуулах гэсэн үг.
2. Оройнуудыг бодит амьдралыг хуулбарлан симуляци хийх. Энэ арга нь их гоё граф үүсгэдэг. Англи нэр нь "Force Based Algorithm"

Миний хувьд 2-р аргыг нь сонгосон. Учир нь интернетэд энийг ашиглаж хялбархан хийсэн юмнууд олон байсан юм. 2-р аргад оройнууд нь өөрийнхөө хөрш буюу ирмэгээр холбогдсон оройнуудтайгаа пүрш ашиглаж холбогддог. Тэгснээр тэд нар тодорхой зайнд байрлахыг эрмэлзэх болно. Бусад оройнуудаасаа хол байхын тулд бусадтай нь түлхэлцэх хэрэгтэй. Энэ 2 татах, түлхэх хүчийг хэрэгжүүлсэн сангууд байсан учраас тэднийг аваад хэрэглэв.


Энэ зурган дээр хар ирмэг нь пүрш, харин тасалдсан шар зураас нь түлхэлцэх хүчийг үзүүлж байна. Шар зураасын дагуу түлхэлцэх үед оройнууд нэг газраа бөөгнөрөхгүй болно.

Граф байгуулах асуудал ингээд дуусахгүй, анхны байрлалыг хэрхэн оновчтой сонгох вэ?

Санамсаргүйгээр байрлуулаад өөрөө тэнцвэртээ орно гээд найдаж болно. Гэвч хүсээгүй тэнцвэрийн нөхцөл гарч ирэх магадлалтай.


Дээрх графын хувьд ийм байвал арай илүү байх:
Дээрх "арай дээр" графыг байгуулахын тулд оройгоо тавихдаа хөршүүдтэйгээ ойрхон, бусад оройнуудаасаа хол байрлуулах хэрэгтэй.

Дээрээс нь үл үзэгдэгч "нар" шиг оройг зурж байгаа дэлгэцнийхээ тэг дунд нь байрлуулах хэрэгтэй. Хэрвээ тэгвэл "нар" маань бусад оройнуудаа өөр лүүгээ татаж зурагдах талбайд дүрсээ татаж оруулах болно. Энэхүү графтай 10 гаруй хоног зууралдсаны эцэст янз бүрийн коднуудаас санаа авсаар эцэст нь иймэрхүү граф байгуулагчтай үлдэж хоцорсон болно :) /* 30 орой 40 ирмэг. Ирмэг нь давхардсан байж магадгүй */
Үр дүн - 1:

Үр дүн-2: