Završni rad (preddiplomski studij): Automatska vizualizacija grafova

Autor:
Generalić, Boris
Mentor:
Čupić, Marko
Na ovim stranicama mogu se pogledati materijali napravljeni u okviru navedenog rada.
Ključne riječi:
graf, vrhovi, bridovi, sile, algoritam, Fruchterman-Reingold, simulirano, kaljenje, sustav, n-tijela, Barnes-Hut, interakcija
Sažetak:

U ovome radu opisan je algoritam korišten za automatsku vizualizaciju grafova koji vrhove grafa raspored određuje na temelju simulacije međudjelovanja sila. Objašnjen je algoritam Fruchterman-Reingold te tehnika simuliranog kaljenja koju algoritam koristi kako bi postigao minimizirao energiju sustava vrhova grafa, s ciljem da se postigne prihvatljiv raspored vrhova grafa. Na temelju rezultata za različite vrste grafova, s obzirom na broj vrhova, objašnjen je problem kvadratne vremenske složenosti kod izračuna sila između vrhova grafa kod tog algoritma.

Od mogućih rješenja objasnili smo algoritam Barnes-Hut za izračun sila između vrhova grafa te smo koristili tehniku simuliranog kaljenja kako bi ostvarili što povoljniji početni raspored vrhova grafa, da bi ubrzali pronalazak konačnog prihvatljivog raspored. Koristeći navedena rješenja napravljena je vlastita implementacija alata za vizualizaciju grafova. Alat omogućava korisniku interakciju s grafom, tijekom simulacije međudjelovanja sila na vrhove grafa, u stvarnom vremenu.

Dokumenti:
  1. Izvorni kodovi programa: GraphVisualisation.zip
  2. Tekst rada: zavrsni.pdf
Zapis stvoren:
2016-07-12 17:07:46
Zapis zaključan:
2016-07-15 07:35:24
Pristup javan:
postavka studenta DA, postavka mentora DA