Tehograafin visualisointialgoritmit ovat luokka graafisen visualisointialgoritmeja esteettisesti miellyttävällä tavalla. Heidän tavoitteenaan on järjestää graafin solmut 2D- tai 3D-avaruudessa siten, että kaikki reunat ovat suunnilleen saman pituisia, ja minimoida reunojen leikkauspisteiden määrä kohdistamalla voimia useille kulmille ja solmuille niiden suhteellisen sijainnin perusteella ja sitten käyttämällä nämä voimat joko simuloivat reunojen ja solmujen liikettä tai minimoivat niiden energiaa [2] .
Vaikka graafien visualisointi voi olla vaikea tehtävä, voima-algoritmit, jotka ovat fyysisiä malleja, eivät yleensä vaadi erityistä graafiteorian osaamista, kuten graafin tasomaisuutta .
Voimakuvaajan visualisointialgoritmit osoittavat voimia graafin reunojen ja solmujen joukkoon . On yleistä käyttää Hooken lakiin perustuvia jousimaisia houkuttelevia voimia määrittämään voimia graafin reunan päiden pareihin. Samaan aikaan kaikkien solmuparien erottamiseen käytetään hylkiviä voimia, jotka ovat samanlaisia kuin sähköisesti varautuneiden hiukkasten hylkiminen Coulombin lain perusteella. Tämän voimajärjestelmän tasapainotilan saavuttamiseksi reunat pyrkivät saamaan tasaisen pituuden (jousien vaikutuksesta), ja solmut, joita ei ole liitetty reunalla, sijaitsevat yleensä etäisyyden päässä toisistaan (johtuen hylkivien voimien toiminta). Vetovoimat (rivat) ja hylkivät voimat (solmut) voidaan määritellä funktioilla, jotka eivät perustu jousien ja hiukkasten fysikaaliseen käyttäytymiseen. Esimerkiksi joissakin tehojärjestelmissä käytetään jousia, joiden voimat vaihtelevat logaritmisesti pikemminkin kuin lineaarisesti.
Vaihtoehtoinen malli ottaa huomioon jousimaiset voimat jokaiselle solmuparille, jossa kunkin jousen ihanteellinen pituus on verrannollinen kaavion solmujen i ja j väliseen etäisyyteen , eikä hylkiviä voimia käytetä. Euklidisen ja ideaalisen solmuetäisyyden välisen eron (yleensä eron neliön) minimoiminen vastaa monimuuttujan skaalausmetriikkaongelmaa .
Voimakäyrä voi käyttää muita voimia kuin mekaanisia jousia ja varauksen hylkäysvoimia. Painovoiman kaltaista voimaa voidaan käyttää vetämään pisteitä kohti kiinteää pistettä graafin piirtoavaruudessa. Tämän avulla voidaan tiivistää irrallisen graafin eri toisiinsa liittyvät komponentit yhdeksi kokonaisuudeksi, muuten nämä osat lennättäisivät toisistaan irti hylkivien voimien vaikutuksesta. Sen avulla voit myös saada solmuja, joissa on parannettu keskiasema kuvassa [3] . Tämä voi myös vaikuttaa kärkien välisiin etäisyyksiin samassa yhdistetyssä komponentissa. Magneettikenttien analogeja voidaan käyttää suunnatuissa kaavioissa. Repulsiivisia voimia voidaan sijoittaa sekä reunoihin että solmuihin päällekkäisyyksien tai lähes päällekkäisyyksien välttämiseksi lopullisessa piirustuksessa. Piirustuksissa, joissa on kaarevia reunoja, kuten ympyräkaareja tai splineitä , voimia voidaan sijoittaa myös näiden käyrien ohjauspisteisiin esimerkiksi kulmaresoluution parantamiseksi [4] .
Kun solmujen ja reunojen voimat on määritetty, koko graafin käyttäytyminen näiden voimien alaisuudessa voidaan mallintaa iteratiivisesti ikään kuin se olisi fyysinen järjestelmä. Tällaisessa tilanteessa solmuihin vaikuttavat voimat yrittävät vetää niitä lähemmäs tai työntää niitä poispäin toisistaan. Tämä jatkuu, kunnes järjestelmä tulee mekaanisen tasapainon tilaan , eli solmujen sijainti ei muutu iteraatiosta iteraatioon. Solmujen sijaintia tässä tasapainotilassa käytetään graafin piirustuksen luomiseen.
Jousista määritellyille voimille, joiden ihanteellinen pituus on verrannollinen kaavion etäisyyteen, jännitysten suurentaminen tuottaa erittäin hyvän käyttäytymisen (eli monotonisen konvergenssin ) [5] ja matemaattisesti tyylikkään tavan minimoida tämä ero ja siten hyvä kuvaajan kärkipisteiden sijoittelu.
Voit myös käyttää mekanismeja, jotka etsivät energiaminimiä suoremmin fyysisen mallin sijaan. Tällaisia mekanismeja, jotka ovat esimerkkejä yleisistä globaaleista optimointitekniikoista , ovat simuloitu hehkutus ja geneettiset algoritmit .
Seuraavat ominaisuudet ovat voimaalgoritmien tärkeimmät edut:
Hyvälaatuiset tulokset Ainakin keskikokoisten graafien (jopa 50-500 kärkeä) kohdalla saaduissa tuloksissa on yleensä erittäin hyvät graafimallit seuraaville kriteereille: reunapituuksien tasaisuus, kärkien tasainen jakautuminen ja symmetria. Viimeinen kriteeri on tärkein ja vaikein saavuttaa muun tyyppisissä algoritmeissa. Joustavuus Voima-algoritmeja voidaan helposti mukauttaa ja laajentaa esteettisiä lisäkriteerejä varten. Tämä tekee algoritmeista yleisempiä kuvaajan visualisointialgoritmien luokkia. Esimerkkejä olemassa olevista laajennuksista ovat suunnatut graafialgoritmit, 3D-graafin visualisointi [6] , klusterigraafin visualisointi, rajoitettu graafin visualisointi ja dynaaminen graafin visualisointi. Intuitiivisuus Koska algoritmit perustuvat tuttujen kohteiden, kuten jousien, fysikaalisiin analogeihin, algoritmien käyttäytyminen on suhteellisen helppo ennustaa ja ymmärtää. Tätä ei löydy muun tyyppisistä graafin visualisointialgoritmeista. Yksinkertaisuus Tyypilliset voima-algoritmit ovat yksinkertaisia ja ne voidaan toteuttaa muutamalla koodirivillä. Muut renderöintialgoritmien luokat, kuten ortogonaaliseen sijoitteluun perustuvat, vaativat yleensä paljon enemmän työtä. interaktiivisuus Toinen tämän luokan algoritmien etu on interaktiivisuus. Piirtämällä kaavion välivaiheet käyttäjä voi seurata kaavion muutoksia ja seurata kehitystä sotkuisesta sotkusta hyvännäköiseen kokoonpanoon. Joissakin interaktiivisissa graafin piirtämistyökaluissa käyttäjä voi pudottaa yhden tai useamman solmun tasapainotilasta ja katsella solmujen siirtymistä uuteen tasapainotilaan. Tämä antaa algoritmeille edun dynaamisissa ja online graafin visualisointijärjestelmissä. Tiukka teoreettinen tuki Vaikka yksinkertaisia voimaalgoritmeja esiintyy usein kirjallisuudessa ja käytännössä (koska ne ovat suhteellisen yksinkertaisia ja ymmärrettäviä), järkevämpien lähestymistapojen määrä alkaa kasvaa. Tilastomiehet ovat ratkaisseet samanlaisia ongelmia moniulotteisessa skaalauksessa ( MDS ) 1930-luvulta lähtien , ja fyysikot ovat myös työskennelleet pitkään liittyvien n kappaleen liikkeen mallintamiseen liittyvien ongelmien parissa , joten on olemassa melko kypsiä lähestymistapoja. Esimerkkinä metrisen MDS:n jännitysmajoituslähestymistapaa voidaan soveltaa graafin visualisointiin, jolloin monotoninen konvergenssi voidaan todistaa [5] . Monotoninen konvergenssi, ominaisuus, että algoritmi vähentää jännitystä tai kustannuksia pisteiden sijoittamisesta kussakin iteraatiossa, on tärkeä, koska se varmistaa, että sijoitus saavuttaa lopulta paikallisen minimin ja algoritmi pysähtyy. Vaimennusvärähtelyt pysäyttävät algoritmin, mutta eivät takaa todellisen paikallisen minimin saavuttamista.Voima-algoritmien tärkeimmät haitat:
Hieno työaika Tyypillisillä voimaalgoritmeilla katsotaan yleensä olevan ajoajat, jotka vastaavat O(n 3 ), missä n on solmujen lukumäärä syötekaaviossa. Tämä johtuu siitä, että iteraatioiden lukumääräksi arvioidaan O(n), ja jokaisessa iteraatiossa on tarpeen tarkastella kaikkia solmupareja ja laskea keskinäiset hylkimisvoimat. Tämä on samanlainen kuin fysiikan N-kappaleen ongelma . Koska hylkivät voimat ovat kuitenkin luonteeltaan paikallisia, graafi voidaan jakaa siten, että vain viereiset kärjet otetaan huomioon. Algoritmien tärkeimmät tekniikat solmujen sijoittelun määrittämisessä suurissa kaavioissa ovat korkeadimensionaaliset upotukset [7] , kerrostetut esitykset ja muut n-kappaleen ongelman mallintamiseen liittyvät tekniikat . Esimerkiksi Barnes-Hut -simulaatioon perustuva FADE-menetelmä [8] voi parantaa ajoaikaa n*log(n):iin iteraatiota kohti. Karkeana arviona voidaan odottaa, että muutamassa sekunnissa voit piirtää enintään 1000 solmua standardi n 2 -tekniikalla iteraatiota kohti ja 100 000 solmua n*log(n) -tekniikalla iteraatiota kohti [8] . Voima-algoritmit, kun ne yhdistetään kerrostettuun lähestymistapaan, voivat piirtää kuvaajia miljoonilla solmuilla [9] . Huonot paikalliset minimit On helppo nähdä, että voima-algoritmi antaa graafin, jolla on minimaalinen energia, erityisesti se voi olla vain paikallinen minimi . Löytynyt paikallinen minimi voi monissa tapauksissa olla merkittävästi huonompi kuin globaali minimi, mikä johtaa huonolaatuiseen esitykseen. Monissa algoritmeissa, erityisesti niissä, jotka sallivat vain gradienttilaskeutumisliikkeen , lopputulokseen voi vaikuttaa voimakkaasti alkusijainti, joka generoidaan useimmissa tapauksissa satunnaisesti. Huonon paikallisen minimin ongelma tulee erityisen tärkeäksi graafin kärkien määrän kasvaessa. Erilaisten algoritmien yhdistäminen auttaa ratkaisemaan tämän ongelman [10] . Voidaan esimerkiksi käyttää Kamada-Kawai-algoritmia [11] hyväksyttävän alkusijoittelun nopeaan luomiseen ja sitten Fruchterman-Reinhold-algoritmia [12] parantamaan naapurisolmujen sijaintia. Toinen tekniikka globaalin minimin saamiseksi on käyttää monitasoista lähestymistapaa [13] .Voimagraafin visualisointimenetelmät juontavat juurensa Tuttin työhön [14] jossa hän osoitti, että monitahoisia kuvaajia voidaan piirtää tasolle, jolla on kupera pinta kiinnittämällä tasograafin ulkopinnan kärjet upotettuna kuperaan asentoon , asettamalla jousi- kuten vetovoimat jokaisessa reunassa ja antavat järjestelmän tulla tasapainotilaan [15] . Voimien yksinkertaisen luonteen vuoksi järjestelmä ei tässä tapauksessa voi juuttua paikalliseen minimiin, vaan konvergoi yhteen globaaliin optimaaliseen konfiguraatioon. Tämän artikkelin valossa kuperapintaisten tasokaavioiden upotuksia kutsutaan joskus Tutt-upotuksiksi .
Eads [16] [17] käytti ensimmäisenä graafin vierekkäisten pisteiden vetovoimien ja kaikkien kärkien hylkimisvoimien yhdistelmää . Fruchterman ja Reingold julkaisivat toisen uraauurtavan työn tämäntyyppisestä voimansijoittelusta [18] . Ajatus käyttää vain jousivoimia kaikkien kärkiparien välillä, joiden ihanteellinen jousipituus on yhtä suuri kuin graafinen etäisyys, johtuu Kamadasta ja Kawaista [19] [11] .