Fruchterman-Reingold algoritam za silom usmjereno crtanje grafova

završni rad

• Naslov (engleski): Fruchterman-Reingold Algorithm for Force-directed Graph Drawing
• Autor: Antonia Radoš
• Mentor: Siniša Srbljić (mentor)
• Član povjerenstva: Slavko Šarić (predsjednik povjerenstva)
• Član povjerenstva: Adrian Satja Kurdija (član povjerenstva)
• Član povjerenstva: Petar Afrić (č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: 2019-07-12, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Crtanje grafova široko je korišteno u matematici i računarstvu. Algoritmi za silom usmjereno crtanje među najfleksibilnijim su metodama za računanje razmještaja čvorova jednostavnih neusmjerenih grafova. U ovom radu opisano je nekoliko algoritama za silom usmjereno crtanje, no samo je Fruchterman-Reingold algoritam detaljno objašnjen i implementiran.
Fruchterman-Reingold algoritam za silom usmjereno crtanje grafova je modifikacija prijašnjeg modela Eadesovog algoritma. Radili smo na nasumičnim grafovima s određenim parametrima broja vrhova, bridova i temperature i optimizirali njihov izgled vlastitom implementacijom algoritma. Svakome vrhu dodijelili smo privlačne i odbojne sile i pustili sustav da dosegne svoju ravnotežu. Rezultat je jednostavan, elegantan, konceptualno intuitivan i učinkovit algoritam.

Sažetak (engleski)

Graph layout is extensively used in the field of mathematics and computer science. Firce-directed algorithms are among the most flexible methods for calculating layouts of simple undirected graphs. In this bachelor’s thesis a few force-directed algorithms are described, but only Fruchterman-Reingold algorithm was thoroughly explained and implemented.
Fruchterman-Reingold algorithm is a modification of a spring-embedder model. We created random graphs and then optimised their node positions using our own implementation of the algorithm. We assigned atrractive and repulsive forces on nodes and then the let the foces move the system to its equilibrium. The result is a simple, elegant, conceptually-intuitive and efficient algorithm.

• Ključne riječi: graf; vrh; brid; sila; Fruchterman-Reingold; silom usmjereno; crtanje grafova; optimizacija; algoritam
• Ključne riječi (engleski): graph; vertex; edge; force; Fruchterman-Reingold; force-directed; graph drawing; optimisation; algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:059920
• 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: 2020-01-07 21:43:32