Automatska vizualizacija grafova

završni rad

• Naslov (engleski): Automatic Graph Visualization
• Autor: Boris Generalić
• Mentor: Marko Čupić (mentor)
• Član povjerenstva: Marko Čupić (predsjednik povjerenstva)
• Član povjerenstva: Martin Tutek (član povjerenstva)
• Član povjerenstva: Alan Jović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2016-07-11, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovome radu opisan je algoritam korišten za automatsku vizualizaciju grafova koji vrhove grafa raspoređ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.

Sažetak (engleski)

In this bachelor's thesis force-directed algorithm is described for automatic graph visualisation. We described Fruchterman-Reingold algorithm and its usage of simulated annealing to minimize the energy of the system and to achive better vertex layout. Based on results for various graphs, considering number of vertices, we discuss the problem of force calculation among vertices which is executed in quadratic time complexity.

We considered Barnes-Hut algorithm for speeding up the force calculation between vertices and we used simulated annealing in order to achieve better inital graph layout, before we actually run the force-directed algorithm. Using these approaches we implemented our own graph visualisation tool which supports real-time interaction with graph during the layout process.

• Ključne riječi: graf; vrhovi; bridovi; sile; algoritam; Fruchterman-Reingold; simulirano; kaljenje; sustav; n-tijela; Barnes-Hut; interakcija
• Ključne riječi (engleski): graph; vertices; edges; forces; force-directed; algorithm; Fruchterman-Reingold; simulated; annealing; system; n-body; Barnes-Hut; interaction
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:236735
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 08:53:45