Graphs are powerful data structures that are widely used to represent complex forms of information. One area in which graphs are successfully being used is within compiler engineering, where a program under compilation can be represented as a graph that changes as the program is being compiled. These graphs, known as Intermediate Representation graphs, can be visualized to aid compiler engineers in understanding and debugging the compiler. However, graphs that change over time need to be visualized so that the viewer’s internal understanding of the graph is maintained. Simultaneously, the graph layouts should be of high quality. These criteria can be conflicting, making the visualization of changing graphs difficult. In this thesis, a dynamic graph layout algorithm to visualize dynamic Intermediate Representation graphs used in the C2 compiler in the Java HotSpotTM Virtual Machine was developed and evaluated. Currently, these graphs are visualized with hierarchical layouts, using a static graph layout algorithm. Five metrics were developed and used to evaluate the layouts by the dynamic algorithm against the layouts by the static algorithm. Four of these were concerned with the layout quality, by measuring the number of edge crossings, number of reversed edges, average degree of the edge bends and the average edge length. The fifth metric was related to mental map preservation and measures the Euclidean distance of node displacement across two layouts. Two experiments were conducted to compare the algorithms. The first experiment measured the layouts drawn by the algorithms when there were a couple of nodes added to or removed from a graph iteratively. A total of 1061 layouts were measured. In 74% of these, the dynamic algorithm caused less node displacement. The second experiment aimed to evaluate the algorithms against what is possible to achieve in regards of minimum node displacement while maintaining a high quality. The results of both experiments indicate that the dynamic layout algorithm yields layouts with less node displacement. However, the layouts generally have more reversed edges, more bends in the edges and overall longer edges. These metrics worsened as more iterations of changes were applied. The findings suggest that the dynamic layout algorithm is better at preserving the mental map, but at the cost of the layout quality. / Grafer är kraftfulla datastrukturer som används för att representera komplexa former av information. Ett område där grafer framgångsrikt används är inom kompilatorutveckling, där ett program under kompilering kan representeras som en graf som förändras medan programmet kompileras. Sådana grafer, kända som mellanrepresentationsgrafer, kan visualiseras för att hjälpa kompilatoringenjörer att förstå och felsöka kompilatorn. Dock behöver grafer som ändras över tid visualiseras så att användarens interna förståelse av grafen bibehålls. Samtidigt bör grafens layout vara av hög kvalitet. Dessa kriterier kan vara motsägelsefulla och gör visualiseringen av föränderliga grafer svår. I denna avhandling utvecklades och utvärderades en dynamisk layoutalgoritm för att visualisera dynamiska mellanrepresentationsgrafer som används i C2-kompilatorn i Java HotSpotTM Virtual Machine. Idag visualiseras dessa grafer med hierarkiska layouter som ritas av en statisk layoutalgoritm. Fem mått utvecklades och användes för att jämföra layouterna ritade av den dynamiska algoritmen med layouterna ritade av den statiska algoritmen. Fyra av dessa var relaterade till layoutkvaliteten och mäter antalet korsningar mellan kanter, antalet omvända kanter, den genomsnittliga graden av kantböjningar och den genomsnittliga kantlängden. Det femte måttet är relaterat till bevarandet av den mentala kartan och mätte nodförskjutningen mellan två layouter. Två experiment genomfördes för att jämföra algoritmerna. Det första experimentet mätte layouterna som ritades av algoritmerna när ett par noder lades till eller togs bort från en graf iterativt. Totalt mättes 1061 layouter. I 74% av dessa orsakade den dynamiska algoritmen mindre nodförskjutning. Det andra experimentet syftade till att utvärdera algoritmerna med avseende på minimal nodförskjutning samtidigt som hög kvalitet bibehålls. Resultaten från båda experimenten indikerar att den dynamiska layoutalgoritmen ger layouter med mindre nodförskjutning. Layouterna har dock generellt sett fler omvända kanter, fler böjningar i kanterna och längre kanter. Dessa mått försämrades när fler iterationer av förändringar tillämpades. Resultaten tyder på att den dynamiska layoutalgoritmen är bättre på att bevara den mentala kartan, men på bekostnad av layoutkvaliteten.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-329352 |
| Date | January 2023 |
| Creators | Yin, Emmy |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2023:343 |
Page generated in 0.1064 seconds