Силом усмерено цртање графова

Алгоритми за усмерено цртање графова су класа алгоритама за цртање графова на естетски најпогоднији начин. Њихова улога је да позиционирају чворове графа у дводимензионалном или тродимензионалном простору, али тако да су ивице приближно једнаких дужина и да их је што мање, користећи силе између постављених ивица и постављених чворова, базиране на њиховој релативној позицији, које се могу користити за кретање између ивица и чворова, или за минимизацију њихових енергија.^[1]

Док цртање графова може бити тежак проблем, алгоритми за силом усмерено цртање графова, представљају физичку симулацију и обично не захтевају специјално знање о теорији графова као планиметрија.

Силе

Алгоритми за силом усмерено цртање графова додељују силе између ивица и између чворова приликом цртања графова. Обично, привлачне силе сличне опрузи базиране на Хуковом закону, се користе да међусобно привуку пар крајњих тачака са ивица графа, док истовремено одбојне силе попут честица са електричним набојем, базиране на Кулоновом закону, се користе да раздвоје све парове чворова. У стању равнотеже овог система сила, ивице теже да имају прописану дужину (због сила сличних опрузи), и чворови који нису повезани ивицама теже да буду што даље (због електричног одбијања). Привлачење ивица и силе за одбијање највише тачке могу бити дефинисане користећи функције које нису базиране на физичком понашању опруге и честица; На пример: Неки принудни системи користе средства чије су привлачне силе више логаритамске него линеарне.

Алтернативни модел разматра силу сличну опрузи за сваки пар чворова $(i,j)$ , где је савршена дужина $\delta _{ij}$ сваке опруге пропорционална дужини дефинисаној теорији графова између чворова и и ј, не користећи одбојне силе. Минимизација разлике (обично разлике квадрата) између Еуклидовог и идеалног растојања између чворова је еквивалентна метричком мултидимензионом скалирајућем проблему.

Силом усмерени граф може обухватити и друге силе осим механичких опруга и електричног одбијања. Сила аналогна гравитацији може бити кориштена да привуче темена ка фиксираним тацкама у простору цртања и може бити кориштена да привуче заједно различите повезане компоненте неповезаног графа, које би иначе тежиле да лебде једна између друге због одбојних сила, и приликом нацрта чворова са великом централношћу ка централној позицији у цртању;^[2] то такође може утицати на простор највиших темена унутар јединствене компоненте. Аналози магнетних поља могу бити кориштени за директне графове, одбојне силе, такође могу бити позиционирани на ивицама као и на чворовима један по један, у редоследу да би се избегло преклапање или приближно преклапање у коначном цртању. У цртежима са заобљеним ивицама као сто је кружни лук или дугачка крива, силе могу такође бити постављене на контролне тачке ових кривих, на пример да побољшају њихову резолуцију углова^[3].

Методе

Једном када су силе чворова и ивица графа дефинисане, понашање читавог графа испод ових извора може бити симулирано као да је то био физички систем. У таквој симулацији силе су примењене на чворове, њиховим повлачењем близе или гурањем даље. Ово је понављано итеративно док систем не дође у стање маганичке равнотеже; тј њихове релативне позиције се више не мењају од једне итерације до друге. Позиција чворова у овој равнотежи се користи да генерише цртеж графа.

За силе дефинисане као опруга чија је идеална дужина пропорцијална дужини у теорији графова, притисак мајоризације даје веома учтив (тј монотоно конвергентан)^[4] и математички коректан начин за минимизацију ових разлика и, стога, налази добар распоред за граф.
Такође је могуће употребити механизам који директније тражи енергију минимума, уместо или у вези са физичком симулацијом. Такви механизми, који су примери метода генералне глобалне оптимизације, укључују пробабилистичку технику и генетске алгоритме.

Предности

Следеће су међу најважнијим предностима силом усмерених алгоритама:

Квалитетни резултати: Бар за графове средњих димензија (од 50-500 темена), добијени резултати обично имају веома добар успех базиран на следећим критеријумима: уједначена дужина ивица, уједначена подела највише тачке и приказане симетрије. Овај последњи критеријум је међу најважнијим и тешко га је постићи са било којом другом врстом алгоритма.
Флексибилност: Силом усмерени алгоритми могу бити лако прилагођени и допуњени да испуне додатни естетски критеријум. Ово их прави најсвестранијом класом алгоритама за цртање графова. Примери постојећих допуна укључују оне за директне графове, 3Д цртање графова,^{[тражи се извор]} кластер цртеж графа, ограничено цртање графа,и динамичко цртање графа.
Интуиција: Посто су они базирани на физичким аналозима обичних објеката, као опруга, понашање алгоритама је релативно једноставно предвидети и разумети. Ово није случај са другим типовима алгоритама за цртање графа.
Једноставност: Типични силом усмерени алгоритми су једноставни и могу бити имплементирани у неколико линија кода. Друге класе алгоритама за цртање графа као оне за ортогоналан распоред, су обично много више запетљане.
Интерактивност: Друге предности ове класе алгоритама су интерактивно гледиште. У средњим фазама цртања графа, корисник може пратити како граф еволуира, гледајући то одвојено од замршеног нереда, у згодној конфигурацији. У неким интерактивним средствима за цртање графова, корисник може повуци један или више чворова изван њиховог стања равнотеже и може посматрати како се враћају назад у позицију. Ово им омогућава избор за динамичке и онлајн системе за цртање графова.
Јаки теоретски темељи: Док се једноставни брзи силом усмерени алгоритми обично појављују у литератури и у пракси (зато што су релативно једноставни за разумевање) више разумни приступи почињу да привлаче пажњу. Статистичари су решавали сличне проблеме у димензионалном скалирању (MDS) још 1930, и физичари такође имају дугу историју рада са повезаним проблемима н-тела, па екстремно зрели приступи постоје.Као пример, притисак мајоризације који приступа метричком МДС-у може бити примењен за цртање графа као што је описано горе. Ово је доказано да конвергира монотоно^[4]. Монотона конвергенција, особина да це алгоритам у свакој итерацији смањивати притисак или цену распореда, је важан зато што гарантује да ће распоред евентуално достићи локални минимум и стати. Damping распоред узрокује да алгоритам стане, али не може гарантовати да је прави локални минимум достигнут.

Мане

Главне мане силом усмерених алгоритама укључују следеће:

Дугачко време извршавања: Типични силом усмерени алгоритми се генерално посматрају као да имају време извршавања једнако $O(n^{3})$ , где је n број чворова улазног графа.То је зато што је процењено да број итерација буде $O(n)$ , и у свакој итерацији, сви парови чворова морају да буду посечени и њихове узајамно одбојне силе израчунате. Ово је повезано са n-body проблемом у физици. Међутим док су одбојне силе локалне по природи граф може бити подељен тако да су само суседни врхови разматрани. Опште технике кориштене у алгоритмима за одређивање распореда великих графова укључују високо димензионално уграђивање,^[5] вишеслојно цртање и друге методе повезане са n-body симулацијом. На пример Берн-Хатова симулација - заснована метода FADE^[6] може побољшати време извршавања до $n*log(n)$ по итерацији. Као грубо превођење, у неколико секунди од једног се може очекивати да нацрта највише 1000 чворова са стандардом $n^{2}$ по итерацији. Силом усмерени алгоритам, када је комбинован са вишестепеним приступом, може нацртати граф са милионима чворова^[6].

Слаб локални минимум: Једноставно је видети да силом усмерени алгоритми стварају граф са минимално енергије, нарочито оне чија је тотална енергија једино локални минимум. Локални минимум може бити, у многим случајевима, знатно гори него глобални минимум, који се претвара у ниско-квалитетно цртање. За многе алгоритме, нарочито оне који допуштају једино стрме покрете темена, коначни резултат може бити снажно узрокован почетним распоредом, који је у већини случајева случајно генерисан. Проблем слабог локалног минимума постаје значајнији како број темена графа расте. Комбинована примена различитих алгоритама је од помоћи за решавање овог проблема.^[7] На пример, користећи Камада-Каваји алгоритам^[8] за брзо генерисање разумног почетног распореда и затим Фруктенман-Реинголд алгоритам да побољша положај суседних чворова. Друге технике за постизање глобалног минимума су кориштење вишестепеног приступа.

Историја

Силом усмерене методе за цртање графова датирају од рада Тутте 1963, који је показао да полиедарски графови могу бити нацртани у подручју са свим конвексним лицима фиксирањем темена на спољашња лица уграђеног планарног графа на конвексну позицију, постављањем привлачне силе сличне опрузи на сваку ивицу и постављањем устаљеног система у равнотежу.^[9] Због једноставне природе сила у овом случају, систем не може бити заглављен у локалном минимуму, али утолико пре конвергира оптималној глобалној конфигурацији. Због овога уграђивање планарних графова са конвексним лицима је понекад звано Тутово уграђивање. Комбинацију привлачних сила на суседним теменима, и одбојних сила на свим теменима је најпре користио Еадес 1984;^[10] додатни пионирски рад на овој врсти силом усмереног распореда је урађено од стране Фруцхтерман & Реинголд 1991.^[11] Идеја кориштења само сила опруге између свих парова темена, са идеалним силама опруге једнаким растојању темена у теорији графова, је од Камада & Каwаи 1989.^[8]

Види још

Цитосцапе, софтвер за визуализацију биолошких мрежа. Основни пакет укључује силом усмерене распореде као једну од градивних метода.
Гепхи, интерактивна визуализација и истраживачка платформа за све врсте мрежа и комплексних система, динамичких и хијерархијских графова.
Грапхвиз, софтвер који извршава алгоритам вишестепеног силом усмереног распореда (између многих осталих) способан да рукује веома великим графовима,
Тулипсофтвер, који имплементира већину алгоритама силом усмереног распореда(GEM, LGL, GRIP, FM).
Префусе
ЛеарнДисцаверy, мобилни софтвер за ИОС који визуализује мапу ума енглеске Wикипедије процењен као оптерећен граф. То укључује силом усмерене распореде као једну од градивних метода за приказивање и приступање повезаном графу из теме.

Референце

^ Кобоуров, Степхен Г. (2012), Спринг Ембеддерс анд Форце-Дирецтед Грапх Драwинг Алгоритхмс, арXив:1201.3011 
^ Баннистер, M. Ј.; Еппстеин, D.; Гоодрицх, M. Т.; Тротт, L. (2012), „Форце-дирецтед грапх драwинг усинг социал гравитy анд сцалинг”, Проц. 20тх Инт. Сyмп. Грапх Драwинг, арXив:1209.0748 
^ Цхернобелскиy, Р.; Цуннингхам, К.; Гоодрицх, M. Т.; Кобоуров, С. Г.; Тротт, L. (2011), „Форце-дирецтед Ломбарди-стyле грапх драwинг”, Проц. 19тх Сyмпосиум он Грапх Драwинг (ПДФ), стр. 78—90
^ ^а ^б де Лееуw, Јан (1988), „Цонвергенце оф тхе мајоризатион метход фор мултидименсионал сцалинг”, Јоурнал оф Цлассифицатион, Спрингер, 5 (2): 163—180, дои:10.1007/БФ01897162
^ Харел, Давид; Корен, Yехуда (2002), „Грапх драwинг бy хигх-дименсионал ембеддинг”, Процеедингс оф тхе 9тх Интернатионал Сyмпосиум он Грапх Драwинг, стр. 207—219, ИСБН 978-3-540-00158-4
^ ^а ^б Qуиглеy, Аарон; Еадес, Петер (2001), „ФАДЕ: Грапх Драwинг, Цлустеринг, анд Висуал Абстрацтион”, Процеедингс оф тхе 8тх Интернатионал Сyмпосиум он Грапх Драwинг (ПДФ), стр. 197—210, ИСБН 978-3-540-41554-1, Архивирано из оригинала (ПДФ) 21. 05. 2006. г., Приступљено 30. 05. 2016
^ Цоллберг, Цхристиан; Кобоуров, Степхен; Награ, Јасвир; Питтс, Јацоб; Wамплер, Кевин (2003), „А Сyстем фор Грапх-басед Висуализатион оф тхе Еволутион оф Софтwаре”, Процеедингс оф тхе 2003 АЦМ Сyмпосиум он Софтwаре Висуализатион (СофтВис '03) (ПДФ), Неw Yорк, НY, УСА: АЦМ, стр. 77—86; фигурес он пп. 212, ИСБН 978-1-58113-642-5, дои:10.1145/774833.774844, „То ацхиеве ан аестхетицаллy плеасинг лаyоут оф тхе грапх ит ис алсо нецессарy то емплоy модифиед Фруцхтерман–Реинголд форцес, ас тхе Камада–Каwаи метход доес нот ацхиеве сатисфацторy метходс бy итселф бут ратхер цреатес а гоод аппроxимате лаyоут со тхат тхе Фруцхтерман-Реинголд цалцулатионс цан qуицклy "тидy уп" тхе лаyоут.”
^ ^а ^б Камада, Томихиса; Каwаи, Сатору (1989), „Ан алгоритхм фор драwинг генерал ундирецтед грапхс”, Информатион Процессинг Леттерс, Елсевиер, 31 (1): 7—15, дои:10.1016/0020-0190(89)90102-6
^ Тутте, W. Т. (1963), „Хоw то драw а грапх”, Процеедингс оф тхе Лондон Матхематицал Социетy, 13 (52): 743—768, дои:10.1112/плмс/с3-13.1.743
^ Еадес, Петер (1984), „А Хеуристиц фор Грапх Драwинг”, Цонгрессус Нумерантиум, 42 (11): 149—160
^ Фруцхтерман, Тхомас M. Ј.; Реинголд, Едwард M. (1991), „Грапх Драwинг бy Форце-Дирецтед Плацемент”, Софтwаре — Працтице & Еxпериенце, Wилеy, 21 (11): 1129—1164, дои:10.1002/спе.4380211102

Литература

ди Баттиста, Гиусеппе; Еадес, Петер; et al. (1999), Грапх Драwинг: Алгоритхмс фор тхе Висуализатион оф Грапхс, Прентице Халл, ИСБН 978-0-13-301615-4
Кауфманн, Мицхаел; Wагнер, Доротхеа, ур. (2001), Драwинг грапхс: метходс анд моделс, Лецтуре Нотес ин Цомпутер Сциенце 2025, Спрингер, ИСБН 978-3-540-42062-0, дои:10.1007/3-540-44969-8

Спољашње везе

„Видео оф Спринг Алгоритхм”. Архивирано из оригинала 30. 09. 2009. г. [деад линк ас оф 27 Маy 2016]
Ливе висуалисатион ин фласх + соурце цоде анд десцриптион
Даниел Тункеланг'с диссертатион (wитх соурце цоде анд демонстратион апплет) он форце-дирецтед грапх лаyоут
Хyперассоциативе Мап Алгоритхм
Интерацтиве анд реал-тиме форце-дирецтед грапхинг алгоритхмс усед ин ан онлине датабасе моделинг тоол

[1] Кобоуров, Степхен Г. (2012), Спринг Ембеддерс анд Форце-Дирецтед Грапх Драwинг Алгоритхмс, арXив:1201.3011 

[2] Баннистер, M. Ј.; Еппстеин, D.; Гоодрицх, M. Т.; Тротт, L. (2012), „Форце-дирецтед грапх драwинг усинг социал гравитy анд сцалинг”, Проц. 20тх Инт. Сyмп. Грапх Драwинг, арXив:1209.0748 

[3] Цхернобелскиy, Р.; Цуннингхам, К.; Гоодрицх, M. Т.; Кобоуров, С. Г.; Тротт, L. (2011), „Форце-дирецтед Ломбарди-стyле грапх драwинг”, Проц. 19тх Сyмпосиум он Грапх Драwинг (ПДФ), стр. 78—90

[dl88-4] а ^б де Лееуw, Јан (1988), „Цонвергенце оф тхе мајоризатион метход фор мултидименсионал сцалинг”, Јоурнал оф Цлассифицатион, Спрингер, 5 (2): 163—180, дои:10.1007/БФ01897162

[5] Харел, Давид; Корен, Yехуда (2002), „Грапх драwинг бy хигх-дименсионал ембеддинг”, Процеедингс оф тхе 9тх Интернатионал Сyмпосиум он Грапх Драwинг, стр. 207—219, ИСБН 978-3-540-00158-4

[quigley+eades-6] а ^б Qуиглеy, Аарон; Еадес, Петер (2001), „ФАДЕ: Грапх Драwинг, Цлустеринг, анд Висуал Абстрацтион”, Процеедингс оф тхе 8тх Интернатионал Сyмпосиум он Грапх Драwинг (ПДФ), стр. 197—210, ИСБН 978-3-540-41554-1, Архивирано из оригинала (ПДФ) 21. 05. 2006. г., Приступљено 30. 05. 2016

[7] Цоллберг, Цхристиан; Кобоуров, Степхен; Награ, Јасвир; Питтс, Јацоб; Wамплер, Кевин (2003), „А Сyстем фор Грапх-басед Висуализатион оф тхе Еволутион оф Софтwаре”, Процеедингс оф тхе 2003 АЦМ Сyмпосиум он Софтwаре Висуализатион (СофтВис '03) (ПДФ), Неw Yорк, НY, УСА: АЦМ, стр. 77—86; фигурес он пп. 212, ИСБН 978-1-58113-642-5, дои:10.1145/774833.774844, „То ацхиеве ан аестхетицаллy плеасинг лаyоут оф тхе грапх ит ис алсо нецессарy то емплоy модифиед Фруцхтерман–Реинголд форцес, ас тхе Камада–Каwаи метход доес нот ацхиеве сатисфацторy метходс бy итселф бут ратхер цреатес а гоод аппроxимате лаyоут со тхат тхе Фруцхтерман-Реинголд цалцулатионс цан qуицклy "тидy уп" тхе лаyоут.”

[kk89-8] а ^б Камада, Томихиса; Каwаи, Сатору (1989), „Ан алгоритхм фор драwинг генерал ундирецтед грапхс”, Информатион Процессинг Леттерс, Елсевиер, 31 (1): 7—15, дои:10.1016/0020-0190(89)90102-6

[9] Тутте, W. Т. (1963), „Хоw то драw а грапх”, Процеедингс оф тхе Лондон Матхематицал Социетy, 13 (52): 743—768, дои:10.1112/плмс/с3-13.1.743

[10] Еадес, Петер (1984), „А Хеуристиц фор Грапх Драwинг”, Цонгрессус Нумерантиум, 42 (11): 149—160

[fr91-11] Фруцхтерман, Тхомас M. Ј.; Реинголд, Едwард M. (1991), „Грапх Драwинг бy Форце-Дирецтед Плацемент”, Софтwаре — Працтице & Еxпериенце, Wилеy, 21 (11): 1129—1164, дои:10.1002/спе.4380211102

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]