Silom usmereno crtanje grafova

Algoritmi za usmereno crtanje grafova su klasa algoritama za crtanje grafova na estetski najpogodniji način. Njihova uloga je da pozicioniraju čvorove grafa u dvodimenzionalnom ili trodimenzionalnom prostoru, ali tako da su ivice približno jednakih dužina i da ih je što manje, koristeći sile između postavljenih ivica i postavljenih čvorova, bazirane na njihovoj relativnoj poziciji, koje se mogu koristiti za kretanje između ivica i čvorova, ili za minimizaciju njihovih energija.^[1]

Dok crtanje grafova može biti težak problem, algoritmi za silom usmereno crtanje grafova, predstavljaju fizičku simulaciju i obično ne zahtevaju specijalno znanje o teoriji grafova kao planimetrija.

Sile[уреди | уреди извор]

Algoritmi za silom usmereno crtanje grafova dodeljuju sile između ivica i između čvorova prilikom crtanja grafova. Obično, privlačne sile slične opruzi bazirane na Hukovom zakonu, se koriste da međusobno privuku par krajnjih tačaka sa ivica grafa, dok istovremeno odbojne sile poput čestica sa električnim nabojem, bazirane na Kulonovom zakonu, se koriste da razdvoje sve parove čvorova. U stanju ravnoteže ovog sistema sila, ivice teže da imaju propisanu dužinu (zbog sila sličnih opruzi), i čvorovi koji nisu povezani ivicama teže da budu što dalje (zbog električnog odbijanja). Privlačenje ivica i sile za odbijanje najviše tačke mogu biti definisane koristeći funkcije koje nisu bazirane na fizičkom ponašanju opruge i čestica; Na primer: Neki prinudni sistemi koriste sredstva čije su privlačne sile više logaritamske nego linearne.

Alternativni model razmatra silu sličnu opruzi za svaki par čvorova $(i,j)$ , gde je savršena dužina $\delta _{ij}$ svake opruge proporcionalna dužini definisanoj teoriji grafova između čvorova i i j, ne koristeći odbojne sile. Minimizacija razlike (obično razlike kvadrata) između Euklidovog i idealnog rastojanja između čvorova je ekvivalentna metričkom multidimenzionom skalirajućem problemu.

Silom usmereni graf može obuhvatiti i druge sile osim mehaničkih opruga i električnog odbijanja. Sila analogna gravitaciji može biti korištena da privuče temena ka fiksiranim tackama u prostoru crtanja i može biti korištena da privuče zajedno različite povezane komponente nepovezanog grafa, koje bi inače težile da lebde jedna između druge zbog odbojnih sila, i prilikom nacrta čvorova sa velikom centralnošću ka centralnoj poziciji u crtanju;^[2] to takođe može uticati na prostor najviših temena unutar jedinstvene komponente. Analozi magnetnih polja mogu biti korišteni za direktne grafove, odbojne sile, takođe mogu biti pozicionirani na ivicama kao i na čvorovima jedan po jedan, u redosledu da bi se izbeglo preklapanje ili približno preklapanje u konačnom crtanju. U crtežima sa zaobljenim ivicama kao sto je kružni luk ili dugačka kriva, sile mogu takođe biti postavljene na kontrolne tačke ovih krivih, na primer da poboljšaju njihovu rezoluciju uglova^[3].

Metode[уреди | уреди извор]

Jednom kada su sile čvorova i ivica grafa definisane, ponašanje čitavog grafa ispod ovih izvora može biti simulirano kao da je to bio fizički sistem. U takvoj simulaciji sile su primenjene na čvorove, njihovim povlačenjem blize ili guranjem dalje. Ovo je ponavljano iterativno dok sistem ne dođe u stanje maganičke ravnoteže; tj njihove relativne pozicije se više ne menjaju od jedne iteracije do druge. Pozicija čvorova u ovoj ravnoteži se koristi da generiše crtež grafa.

Za sile definisane kao opruga čija je idealna dužina proporcijalna dužini u teoriji grafova, pritisak majorizacije daje veoma učtiv (tj monotono konvergentan)^[4] i matematički korektan način za minimizaciju ovih razlika i, stoga, nalazi dobar raspored za graf.
Takođe je moguće upotrebiti mehanizam koji direktnije traži energiju minimuma, umesto ili u vezi sa fizičkom simulacijom. Takvi mehanizmi, koji su primeri metoda generalne globalne optimizacije, uključuju probabilističku tehniku i genetske algoritme.

Prednosti[уреди | уреди извор]

Sledeće su među najvažnijim prednostima silom usmerenih algoritama:

Kvalitetni rezultati: Bar za grafove srednjih dimenzija (od 50-500 temena), dobijeni rezultati obično imaju veoma dobar uspeh baziran na sledećim kriterijumima: ujednačena dužina ivica, ujednačena podela najviše tačke i prikazane simetrije. Ovaj poslednji kriterijum je među najvažnijim i teško ga je postići sa bilo kojom drugom vrstom algoritma.
Fleksibilnost: Silom usmereni algoritmi mogu biti lako prilagođeni i dopunjeni da ispune dodatni estetski kriterijum. Ovo ih pravi najsvestranijom klasom algoritama za crtanje grafova. Primeri postojećih dopuna uključuju one za direktne grafove, 3D crtanje grafova,^[5] klaster crtež grafa, ograničeno crtanje grafa,i dinamičko crtanje grafa.
Intuicija: Posto su oni bazirani na fizičkim analozima običnih objekata, kao opruga, ponašanje algoritama je relativno jednostavno predvideti i razumeti. Ovo nije slučaj sa drugim tipovima algoritama za crtanje grafa.
Jednostavnost: Tipični silom usmereni algoritmi su jednostavni i mogu biti implementirani u nekoliko linija koda. Druge klase algoritama za crtanje grafa kao one za ortogonalan raspored, su obično mnogo više zapetljane.
Interaktivnost: Druge prednosti ove klase algoritama su interaktivno gledište. U srednjim fazama crtanja grafa, korisnik može pratiti kako graf evoluira, gledajući to odvojeno od zamršenog nereda, u zgodnoj konfiguraciji. U nekim interaktivnim sredstvima za crtanje grafova, korisnik može povuci jedan ili više čvorova izvan njihovog stanja ravnoteže i može posmatrati kako se vraćaju nazad u poziciju. Ovo im omogućava izbor za dinamičke i onlajn sisteme za crtanje grafova.
Jaki teoretski temelji: Dok se jednostavni brzi silom usmereni algoritmi obično pojavljuju u literaturi i u praksi (zato što su relativno jednostavni za razumevanje) više razumni pristupi počinju da privlače pažnju. Statističari su rešavali slične probleme u dimenzionalnom skaliranju (MDS) još 1930, i fizičari takođe imaju dugu istoriju rada sa povezanim problemima n-tela, pa ekstremno zreli pristupi postoje.Kao primer, pritisak majorizacije koji pristupa metričkom MDS-u može biti primenjen za crtanje grafa kao što je opisano gore. Ovo je dokazano da konvergira monotono^[4]. Monotona konvergencija, osobina da ce algoritam u svakoj iteraciji smanjivati pritisak ili cenu rasporeda, je važan zato što garantuje da će raspored eventualno dostići lokalni minimum i stati. Damping raspored uzrokuje da algoritam stane, ali ne može garantovati da je pravi lokalni minimum dostignut.

Mane[уреди | уреди извор]

Glavne mane silom usmerenih algoritama uključuju sledeće:

Dugačko vreme izvršavanja: Tipični silom usmereni algoritmi se generalno posmatraju kao da imaju vreme izvršavanja jednako $O(n^{3})$ , gde je n broj čvorova ulaznog grafa.To je zato što je procenjeno da broj iteracija bude $O(n)$ , i u svakoj iteraciji, svi parovi čvorova moraju da budu posečeni i njihove uzajamno odbojne sile izračunate. Ovo je povezano sa n-body problemom u fizici. Međutim dok su odbojne sile lokalne po prirodi graf može biti podeljen tako da su samo susedni vrhovi razmatrani. Opšte tehnike korištene u algoritmima za određivanje rasporeda velikih grafova uključuju visoko dimenzionalno ugrađivanje,^[6] višeslojno crtanje i druge metode povezane sa n-body simulacijom. Na primer Bern-Hatova simulacija - zasnovana metoda FADE^[7] može poboljšati vreme izvršavanja do $n*log(n)$ po iteraciji. Kao grubo prevođenje, u nekoliko sekundi od jednog se može očekivati da nacrta najviše 1000 čvorova sa standardom $n^{2}$ po iteraciji. Silom usmereni algoritam, kada je kombinovan sa višestepenim pristupom, može nacrtati graf sa milionima čvorova^[7].

Slab lokalni minimum: Jednostavno je videti da silom usmereni algoritmi stvaraju graf sa minimalno energije, naročito one čija je totalna energija jedino lokalni minimum. Lokalni minimum može biti, u mnogim slučajevima, znatno gori nego globalni minimum, koji se pretvara u nisko-kvalitetno crtanje. Za mnoge algoritme, naročito one koji dopuštaju jedino strme pokrete temena, konačni rezultat može biti snažno uzrokovan početnim rasporedom, koji je u većini slučajeva slučajno generisan. Problem slabog lokalnog minimuma postaje značajniji kako broj temena grafa raste. Kombinovana primena različitih algoritama je od pomoći za rešavanje ovog problema.^[8] Na primer, koristeći Kamada-Kavaji algoritam ^[9] za brzo generisanje razumnog početnog rasporeda i zatim Fruktenman-Reingold algoritam da poboljša položaj susednih čvorova. Druge tehnike za postizanje globalnog minimuma su korištenje višestepenog pristupa.

Istorija[уреди | уреди извор]

Silom usmerene metode za crtanje grafova datiraju od rada Tutte 1963, koji je pokazao da poliedarski grafovi mogu biti nacrtani u području sa svim konveksnim licima fiksiranjem temena na spoljašnja lica ugrađenog planarnog grafa na konveksnu poziciju, postavljanjem privlačne sile slične opruzi na svaku ivicu i postavljanjem ustaljenog sistema u ravnotežu.^[10] Zbog jednostavne prirode sila u ovom slučaju, sistem ne može biti zaglavljen u lokalnom minimumu, ali utoliko pre konvergira optimalnoj globalnoj konfiguraciji. Zbog ovoga ugrađivanje planarnih grafova sa konveksnim licima je ponekad zvano Tutovo ugrađivanje. Kombinaciju privlačnih sila na susednim temenima, i odbojnih sila na svim temenima je najpre koristio Eades 1984;^[11] dodatni pionirski rad na ovoj vrsti silom usmerenog rasporeda je urađeno od strane Fruchterman & Reingold 1991.^[12] Ideja korištenja samo sila opruge između svih parova temena, sa idealnim silama opruge jednakim rastojanju temena u teoriji grafova, je od Kamada & Kawai 1989.^[9]

Videti takođe[уреди | уреди извор]

Citoscape, softver za vizualizaciju bioloških mreža. Osnovni paket uključuje silom usmerene rasporede kao jednu od gradivnih metoda.
Gephi, interaktivna vizualizacija i istraživačka platforma za sve vrste mreža i kompleksnih sistema, dinamičkih i hijerarhijskih grafova.
Graphviz, softver koji izvršava algoritam višestepenog silom usmerenog rasporeda (između mnogih ostalih) sposoban da rukuje veoma velikim grafovima,
Tulipsoftver, koji implementira većinu algoritama silom usmerenog rasporeda(GEM, LGL, GRIP, FM).
Prefuse
LearnDiscavery, mobilni softver za IOS koji vizualizuje mapu uma engleske Wikipedije procenjen kao opterećen graf. To uključuje silom usmerene rasporede kao jednu od gradivnih metoda za prikazivanje i pristupanje povezanom grafu iz teme.

Reference[уреди | уреди извор]

^ Kobourov, Stephen G. (2012), Spring Embedders and Force-Directed Graph Drawing Algorithms, arXiv:1201.3011 
^ Bannister, M. J.; Eppstein, D.; Goodrich, M. T.; Trott, L. (2012), „Force-directed graph drawing using social gravity and scaling”, Proc. 20th Int. Symp. Graph Drawing, arXiv:1209.0748 
^ Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L. (2011), „Force-directed Lombardi-style graph drawing”, Proc. 19th Symposium on Graph Drawing (PDF), стр. 78—90
^ ^а ^б de Leeuw, Jan (1988), „Convergence of the majorization method for multidimensional scaling”, Journal of Classification, Springer, 5 (2): 163—180, doi:10.1007/BF01897162
^ Vose, Aaron. „3D Phylogenetic Tree Viewer”. Приступљено 3. 6. 2012. ^{[мртва веза]}
^ Harel, David; Koren, Yehuda (2002), „Graph drawing by high-dimensional embedding”, Proceedings of the 9th International Symposium on Graph Drawing, стр. 207—219, ISBN 978-3-540-00158-4
^ ^а ^б Quigley, Aaron; Eades, Peter (2001), „FADE: Graph Drawing, Clustering, and Visual Abstraction”, Proceedings of the 8th International Symposium on Graph Drawing (PDF), стр. 197—210, ISBN 978-3-540-41554-1, Архивирано из оригинала (PDF) 21. 05. 2006. г., Приступљено 30. 05. 2016
^ Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), „A System for Graph-based Visualization of the Evolution of Software”, Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03) (PDF), New York, NY, USA: ACM, стр. 77—86; figures on pp. 212, ISBN 978-1-58113-642-5, doi:10.1145/774833.774844, „To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout.”
^ ^а ^б Kamada, Tomihisa; Kawai, Satoru (1989), „An algorithm for drawing general undirected graphs”, Information Processing Letters, Elsevier, 31 (1): 7—15, doi:10.1016/0020-0190(89)90102-6
^ Tutte, W. T. (1963), „How to draw a graph”, Proceedings of the London Mathematical Society, 13 (52): 743—768, doi:10.1112/plms/s3-13.1.743
^ Eades, Peter (1984), „A Heuristic for Graph Drawing”, Congressus Numerantium, 42 (11): 149—160
^ Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), „Graph Drawing by Force-Directed Placement”, Software — Practice & Experience, Wiley, 21 (11): 1129—1164, doi:10.1002/spe.4380211102

Literatura[уреди | уреди извор]

di Battista, Giuseppe; Eades, Peter; et al. (1999), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 978-0-13-301615-4
Kaufmann, Michael; Wagner, Dorothea, ур. (2001), Drawing graphs: methods and models, Lecture Notes in Computer Science 2025, Springer, ISBN 978-3-540-42062-0, doi:10.1007/3-540-44969-8

Spoljašnje veze[уреди | уреди извор]

Video of Spring Algorithm Архивирано на сајту Wayback Machine (30. септембар 2009) [dead link as of 27 May 2016]
Live visualisation in flash + source code and description
Daniel Tunkelang's dissertation (with source code and demonstration applet) on force-directed graph layout
Hyperassociative Map Algorithm
Interactive and real-time force-directed graphing algorithms used in an online database modeling tool

[1] Kobourov, Stephen G. (2012), Spring Embedders and Force-Directed Graph Drawing Algorithms, arXiv:1201.3011 

[2] Bannister, M. J.; Eppstein, D.; Goodrich, M. T.; Trott, L. (2012), „Force-directed graph drawing using social gravity and scaling”, Proc. 20th Int. Symp. Graph Drawing, arXiv:1209.0748 

[3] Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L. (2011), „Force-directed Lombardi-style graph drawing”, Proc. 19th Symposium on Graph Drawing (PDF), стр. 78—90

[dl88-4] а ^б de Leeuw, Jan (1988), „Convergence of the majorization method for multidimensional scaling”, Journal of Classification, Springer, 5 (2): 163—180, doi:10.1007/BF01897162

[5] Vose, Aaron. „3D Phylogenetic Tree Viewer”. Приступљено 3. 6. 2012. ^{[мртва веза]}

[6] Harel, David; Koren, Yehuda (2002), „Graph drawing by high-dimensional embedding”, Proceedings of the 9th International Symposium on Graph Drawing, стр. 207—219, ISBN 978-3-540-00158-4

[quigley+eades-7] а ^б Quigley, Aaron; Eades, Peter (2001), „FADE: Graph Drawing, Clustering, and Visual Abstraction”, Proceedings of the 8th International Symposium on Graph Drawing (PDF), стр. 197—210, ISBN 978-3-540-41554-1, Архивирано из оригинала (PDF) 21. 05. 2006. г., Приступљено 30. 05. 2016

[8] Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin (2003), „A System for Graph-based Visualization of the Evolution of Software”, Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03) (PDF), New York, NY, USA: ACM, стр. 77—86; figures on pp. 212, ISBN 978-1-58113-642-5, doi:10.1145/774833.774844, „To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout.”

[kk89-9] а ^б Kamada, Tomihisa; Kawai, Satoru (1989), „An algorithm for drawing general undirected graphs”, Information Processing Letters, Elsevier, 31 (1): 7—15, doi:10.1016/0020-0190(89)90102-6

[10] Tutte, W. T. (1963), „How to draw a graph”, Proceedings of the London Mathematical Society, 13 (52): 743—768, doi:10.1112/plms/s3-13.1.743

[11] Eades, Peter (1984), „A Heuristic for Graph Drawing”, Congressus Numerantium, 42 (11): 149—160

[fr91-12] Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), „Graph Drawing by Force-Directed Placement”, Software — Practice & Experience, Wiley, 21 (11): 1129—1164, doi:10.1002/spe.4380211102

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]