Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Kravbaserad layout - Algoritm för automatisk grafritning
KTH, School of Information and Communication Technology (ICT).
KTH, School of Information and Communication Technology (ICT).
2016 (Swedish)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [sv]

I den här studien utformas och implementeras en prototyp av ett automatiskt grafritningsverktyg. Under processen analyseras och evalueras flera välkända och viktiga algoritmer. Algoritmen som används i prototypen modifieras och förbättras för att uppfylla företaget FindOuts speciella krav. Dessutom strävar vi efter att hitta förbättringar med avseende på visualisering och prestanda för algoritmer genom att studera aktuella arbeten.

Genom litteraturoch empiriska studier, drar vi slutsatsen att Sugiyama-ramverket passar bäst för hierarkiska och liknande grafer. Den genererade grafritningen är stabil, läsbar och följer de flesta estetiska kriterier. Dessutom används kraftbaserad layout för att placera de icke sammanhängande delgraferna på lämpliga positioner. Attraktionsoch repulsionskraft mellan delgrafer gör att hela grafen blir kompakt utan överlappning, vilket är ett av företagets krav.

Några problem såsom att lägga till nya noder och kanter är inte helt lösta på grund av konflikten mellan estetiska kriterier och användarkrav. Vi anser att en algoritm baserad på användarkrav är lämplig att integreras i en nästa generation av vår prototyp. En del av heuristiken kan också förbättras. Vi presenterar möjliga lösningar och föreslår att en noggrann jämförelse mellan olika algoritmer bör tas upp i framtida arbete.

Abstract [en]

A prototype of an automatic graph drawing tool was designed and implemented in this thesis project. In this process various well-known and important algorithms were analyzed and evaluated. Algorithms applied in the prototype were modified and improved to fulfill FindOut’s special requirements. Besides this, a pursuit of an improvement on visualizations and performance of algorithms was conducted by studying the latest research works.

Through these theoretical and empirical studies, we concluded that the Sugiyama framework is the most suitable algorithm to generate the workflow type of graph. The generated graphs are stable, readable and follows most aesthetic standards. Furthermore, force-directed algorithms were utilized to put graphs at appropriate positions. The attraction and repulsion force between sub-graphs can make the whole graph compact without overlapping, which fulfills the company’s requirement.

However some of the problems, such as importing new nodes and edges, have not been perfectly resolved due to the conflict between the aesthetic and user requirements. Thus we think that a user-constraints based algorithm is suitable to be integrated into our next generation prototype. Some of the heuristics also have room for improvement. We discussed the possible solutions and suggested that a comparative study of different algorithms should be included in the future work.

Place, publisher, year, edition, pages
2016. , 71 p.
Series
TRITA-ICT-EX, 2016:58
Keyword [en]
graph drawing algorithm, constraints-based, Sugiyama framework, Force-directed layout
Keyword [sv]
Grafritningsalgoritm, kravbaserad, Sugiyama-ramverk, kraftbaserad layout.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-205328OAI: oai:DiVA.org:kth-205328DiVA: diva2:1088572
Subject / course
Information and Communication Technology
Educational program
Master of Science in Engineering - Information and Communication Technology
Supervisors
Examiners
Available from: 2017-04-13 Created: 2017-04-13 Last updated: 2017-04-13Bibliographically approved

Open Access in DiVA

No full text

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf