A space of layout styles for hierarchical graph models of software systems

ABSTRACT

Hierarchical graphs are widely used as models of the structure of software systems. A central problem in the visualization of hierarchical graphs is the computation of layouts, i.e. of positions of the nodes in two- or three-dimensional space. We derive requirements for graph layouts from various software analysis questions, and classify the required layouts along three dimensions: layouts with meaningful distances between single nodes vs. layouts with meaningful distances between groups of nodes, layouts reflecting adjacency vs. layouts reflecting hierarchy, and layouts that faithfully reflect the size of subgraphs vs. layouts where certain subgraphs are magnified. We present a fairly simple and theoretically validated energy model for computing such layouts.

References

1. Balzer, M., Noack, A., Deussen, O., and Lewerentz, C. 2004. Software landscapes: Visualizing the structure of large software systems. In Proc. Symposium on Visualization (VisSym 2004), 261--266.]]
2. Barnes, J., and Hut, P. 1986. A hierarchical O(N log N) force-calculation algorithm. Nature 324, 446--449.]]
3. Bartram, L., Ho, A., Dill, J., and Henigman, F. 1995. The continuous zoom: A constrained fisheye technique for viewing and navigating large information spaces. In Proc. 8th ACM Symposium on User Interface Software and Technology (UIST 1995), 207--215.]]
4. Brandes, U. 2001. Drawing on physical analogies. In Drawing Graphs: Methods and Models, M. Kaufmann and D. Wagner, Eds., LNCS 2025. Springer-Verlag, Berlin, 71--86.]]
5. Buchsbaum, A. L., and Westbrook, J. 2000. Maintaining hierarchical graph views. In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), 566--575.]]
6. Card, S. K., Mackinlay, J. D., and Shneiderman, B. 1999. Readings in Information Visualization: Using Vision to Think. Morgan Kaufmann.]]
7. Collberg, C. S., Kobourov, S. G., Nagra, J., Pitts, J., and Wampler, K. 2003. A system for graph-based visualization of the evolution of software. In Proc. ACM Symposium on Software Visualization (SoftVis 2003), 77--86.]]
8. Davidson, R., and Harel, D. 1996. Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics 15, 4, 301--331.]]
9. Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. 1999. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall.]]
10. Diehl, S., and Görg, C. 2002. Graphs, they are changing. In Proc. 10th International Symposium on Graph Drawing (GD 2002), Springer-Verlag, LNCS 2528, 23--30.]]
11. Eades, P., and Huang, M. L. 2000. Navigating clustered graphs using force-directed methods. Journal of Graph Algorithms and Applications 4, 3, 157--181.]]
12. Eades, P. 1984. A heuristic for graph drawing. Congressus Numerantium 42, 149--160.]]
13. Finnigan, P. J., Holt, R. C., Kalas, I., Kerr, S., Kontogiannis, K., Müller, H. A., Mylopoulos, J., Perelgut, S. G., Stanley, M., and Wong, K. 1997. The software bookshelf. IBM Systems Journal 36, 4, 564--593.]]
14. Fowler, M. 2001. Reducing coupling. IEEE Software 18, 4, 102--104.]]
15. Frishman, Y., and Tal, A. 2004. Dynamic drawing of clustered graphs. In Proc. IEEE Symposium on Information Visualization (InfoVis 2004), 191--198.]]
16. Fruchterman, T. M. J., and Reingold, E. M. 1991. Graph drawing by force-directed placement. Software -- Practice and Experience 21, 11, 1129--1164.]]
17. Furnas, G. W. 1986. Generalized fisheye views. In Proc. ACM SIGCHI Conference on Human Factors in Computing Systems (CHI 1986), 16--23.]]
18. Huang, M. L. 1999. Online Information Visualization of Huge Data Spaces. PhD thesis, Department of Computer Science and Software Engineering, University of Newcastle.]]
19. Kamada, T., and Kawai, S. 1989. An algorithm for drawing general undirected graphs. Information Processing Letters 31, 1, 7--15.]]
20. Koschke, R. 2000. Atomic Architectural Component Recovery for Program Understanding and Evolution. PhD thesis, Institut für Informatik, Universität. Stuttgart.]]
21. Lintern, R., Michaud, J., Storey, M.-A. D., and Wu, X. 2003. Plugging-in visualization: Experiences integrating a visualization tool with Eclipse. In Proc. ACM Symposium on Software Visualization (SoftVis 2003), 47--56.]]
22. Misue, K., Eades, P., Lai, W., and Sugiyama, K. 1995. Layout adjustment and the mental map. Journal of Visual Languages and Computing 6, 2, 183--210.]]
23. Müller, H. A., Orgun, M. A., Tilley, S. R., and Uhl, J. S. 1993. A reverse engineering approach to subsystem structure identification. Journal of Software Maintenance: Research and Practice 5, 4, 181--204.]]
24. Murphy, G. C., Notkin, D., and Sullivan, K. J. 2001. Software reflexion models: Bridging the gap between design and implementation. IEEE Transactions on Software Engineering 27, 4, 364--380.]]
25. Noack, A. 2004. An energy model for visual graph clustering. In Proc. 11th International Symposium on Graph Drawing (GD 2003), Springer-Verlag, LNCS 2912, 425--436.]]
26. Noack, A. 2004. Visual clustering of graphs with nonuniform degrees. Tech. Rep. 02/04, Institute of Computer Science, Brandenburg University of Technology at Cottbus.]]
27. Noik, E. G. 1993. Layout-independent fisheye views of nested graphs. In Proc. IEEE Workshop on Visual Languages (VL 1993), 336--341.]]
28. North, S. C., and Woodhull, G. 2002. Online hierarchical graph drawing. In Proc. 9th International Symposium on Graph Drawing (GD 2001), Springer-Verlag, LNCS 2265, 232--246.]]
29. Parker, G., Franck, G., and Ware, C. 1998. Visualization of large nested graphs in 3d: Navigation and interaction. Journal of Visual Languages and Computing 9, 3, 299--317.]]
30. Penny, D. A. 1992. The Software Landscape: A Visual Formalism for Programming-in-the-Large. PhD thesis, Department of Computer Science, University of Toronto.]]
31. Quigley, A. J., and Eades, P. 2001. FADE: Graph drawing, clustering, and visual abstraction. In Proc. 8th International Symposium on Graph Drawing (GD 2000), Springer-Verlag, LNCS 1984, 197--210.]]
32. Reiss, S. P. 1995. An engine for the 3d visualization of program information. Journal of Visual Languages and Computing 6, 3, 299--323.]]
33. Sarkar, M., and Brown, M. H. 1994. Graphical fisheye views. Communications of the ACM 37, 12, 73--84.]]
34. Schaffer, D., Zuo, Z., Greenberg, S., Bartram, L., Dill, J., Dubs, S., and Roseman, M. 1996. Navigating hierarchically clustered networks through fisheye and full-zoom methods. ACM Transactions on Computer-Human Interaction 3, 2, 162--188.]]
35. Shneiderman, B. 1992. Tree visualization with tree-maps: A 2-d space-filling approach. ACM Transactions on Graphics 11, 1, 92--99.]]
36. Storey, M.-A. D., Fracchia, F. D., and Müller, H. A. 1999. Customizing a fisheye view algorithm to preserve the mental map. Journal of Visual Languages and Computing 10, 3, 245--267.]]
37. Sugiyama, K., and Misue, K. 1991. Visualization of structural information: Automatic drawing of compound digraphs. IEEE Transactions on Systems, Man, and Cybernetics 21, 4, 876--892.]]
38. Sugiyama, K., and Misue, K. 1995. Graph drawing by the magnetic spring model. Journal of Visual Languages and Computing 6, 3, 217--231.]]
39. Van Ham, F., and Van Wijk, J. J. 2004. Interactive visualization of small world graphs. In Proc. IEEE Symposium on Information Visualization (InfoVis 2004), 199--206.]]
40. Van Liere, R., and De Leeuw, W. 2003. GraphSplatting: Visualizing graphs as continuous fields. IEEE Transactions on Visualization and Computer Graphics 9, 2, 206--212.]]
41. Wang, X., and Miyamoto, I. 1996. Generating customized layouts. In Proc. Symposium on Graph Drawing (GD 1995), Springer, LNCS 1027, 504--515.]]
42. Ware, C., Franck, G., Parkhi, M., and Dudley, T. 1997. Layout for visualizing large software structures in 3d. In Proc. 2nd International Conference on Visual Information Systems (VISUAL 1997), 215--223.]]

Index Terms

• Applied computing

  • Document management and text processing

    • Document capture

      • Graphics recognition and interpretation

• Computing methodologies

  • Computer graphics

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Cluster analysis

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software maintenance

• Software and its engineering

  • Software creation and management

    • Software post-development issues