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. / 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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-205328 |
| Date | January 2016 |
| Creators | Chen, Zimin, Xie, Huan |
| Publisher | KTH, Skolan för informations- och kommunikationsteknik (ICT) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-ICT-EX ; 2016:58 |
Page generated in 0.0025 seconds