Automatska vizualizacija grafova

undergraduate thesis

• Title (english): Automatic Graph Visualization
• Author: Boris Generalić
• Mentor: Marko Čupić (mentor)
• Committee member: Marko Čupić (predsjednik povjerenstva)
• Committee member: Martin Tutek (član povjerenstva)
• Committee member: Alan Jović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: graf; vrhovi; bridovi; sile; algoritam; Fruchterman-Reingold; simulirano; kaljenje; sustav; n-tijela; Barnes-Hut; interakcija
• Keywords (english): graph; vertices; edges; forces; force-directed; algorithm; Fruchterman-Reingold; simulated; annealing; system; n-body; Barnes-Hut; interaction
• Language: croatian
• URN:NBN: urn:nbn:hr:168:236735
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 08:53:45