Fruchterman-Reingold algoritam za silom usmjereno crtanje grafova

undergraduate thesis

• Title (english): Fruchterman-Reingold Algorithm for Force-directed Graph Drawing
• Author: Antonia Radoš
• Mentor: Siniša Srbljić (mentor)
• Committee member: Slavko Šarić (predsjednik povjerenstva)
• Committee member: Adrian Satja Kurdija (član povjerenstva)
• Committee member: Petar Afrić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: graf; vrh; brid; sila; Fruchterman-Reingold; silom usmjereno; crtanje grafova; optimizacija; algoritam
• Keywords (english): graph; vertex; edge; force; Fruchterman-Reingold; force-directed; graph drawing; optimisation; algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:059920
• 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: 2020-01-07 21:43:32