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: Lyn Bartram , Albert Ho , John Dill , Frank Henigman, The continuous zoom: a constrained fisheye technique for viewing and navigating large information spaces, Proceedings of the 8th annual ACM symposium on User interface and software technology, p.207-215, November 15-17, 1995, Pittsburgh, Pennsylvania, United States [doi>10.1145/215585.215977]
• 4: Ulrik Brandes, Drawing on physical analogies, Drawing graphs: methods and models, Springer-Verlag, London, 2001
• 5: Adam L. Buchsbaum , Jefferey R. Westbrook, Maintaining hierarchical graph views, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.566-575, January 09-11, 2000, San Francisco, California, United States
• 6: Stuart K. Card , Jock D. Mackinlay , Ben Shneiderman, Readings in information visualization: using vision to think, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 7: Christian Collberg , Stephen Kobourov , Jasvir Nagra , Jacob Pitts , Kevin Wampler, A system for graph-based visualization of the evolution of software, Proceedings of the 2003 ACM symposium on Software visualization, June 11-13, 2003, San Diego, California [doi>10.1145/774833.774844]
• 8: Ron Davidson , David Harel, Drawing graphs nicely using simulated annealing, ACM Transactions on Graphics (TOG), v.15 n.4, p.301-331, Oct. 1996 [doi>10.1145/234535.234538]
• 9: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 10: Stephan Diehl , Carsten Görg, Graphs, They Are Changing, Revised Papers from the 10th International Symposium on Graph Drawing, p.23-30, August 26-28, 2002
• 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: P. J. Finnigan , R. C. Holt , I. Kalas , S. Kerr , K. Kontogiannis , H. A. Müller , J. Mylopoulos , S. G. Perelgut , M. Stanley , K. Wong, The software bookshelf, IBM Systems Journal, v.36 n.4, p.564-593, 1997
• 14: Martin Fowler, Reducing Coupling, IEEE Software, v.18 n.4, p.102-104, July 2001 [doi>10.1109/MS.2001.936226]
• 15: Yaniv Frishman , Ayellet Tal, Dynamic Drawing of Clustered Graphs, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.191-198, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.18]
• 16: Thomas M. J. Fruchterman , Edward M. Reingold, Graph drawing by force-directed placement, Software—Practice & Experience, v.21 n.11, p.1129-1164, Nov. 1991 [doi>10.1002/spe.4380211102]
• 17: G. W. Furnas, Generalized fisheye views, Proceedings of the SIGCHI conference on Human factors in computing systems, p.16-23, April 13-17, 1986, Boston, Massachusetts, United States
• 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: T. Kamada , S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, v.31 n.1, p.7-15, April 1989 [doi>10.1016/0020-0190(89)90102-6]
• 20: Koschke, R. 2000. Atomic Architectural Component Recovery for Program Understanding and Evolution. PhD thesis, Institut für Informatik, Universität. Stuttgart.
• 21: Rob Lintern , Jeff Michaud , Margaret-Anne Storey , Xiaomin Wu, Plugging-in visualization: experiences integrating a visualization tool with Eclipse, Proceedings of the 2003 ACM symposium on Software visualization, June 11-13, 2003, San Diego, California [doi>10.1145/774833.774840]
• 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: Gail C. Murphy , David Notkin , Kevin J. Sullivan, Software Reflexion Models: Bridging the Gap between Design and Implementation, IEEE Transactions on Software Engineering, v.27 n.4, p.364-380, April 2001 [doi>10.1109/32.917525]
• 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: Stephen C. North , Gordon Woodhull, Online Hierarchical Graph Drawing, Revised Papers from the 9th International Symposium on Graph Drawing, p.232-246, September 23-26, 2001
• 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: David Allan Penny, The software landscape: a visual formalism for programming-in-the-large, University of Toronto, Toronto, Ont., Canada, 1993
• 31: Aaron Quigley , Peter Eades, FADE: Graph Drawing, Clustering, and Visual Abstraction, Proceedings of the 8th International Symposium on Graph Drawing, p.197-210, September 20-23, 2000
• 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: Manojit Sarkar , Marc H. Brown, Graphical fisheye views, Communications of the ACM, v.37 n.12, p.73-83, Dec. 1994 [doi>10.1145/198366.198384]
• 34: Doug Schaffer , Zhengping Zuo , Saul Greenberg , Lyn Bartram , John Dill , Shelli Dubs , Mark Roseman, Navigating hierarchically clustered networks through fisheye and full-zoom methods, ACM Transactions on Computer-Human Interaction (TOCHI), v.3 n.2, p.162-188, June 1996 [doi>10.1145/230562.230577]
• 35: Ben Shneiderman, Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v.11 n.1, p.92-99, Jan. 1992 [doi>10.1145/102377.115768]
• 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: Frank van Ham , Jarke J. van Wijk, Interactive Visualization of Small World Graphs, Proceedings of the IEEE Symposium on Information Visualization (INFOVIS'04), p.199-206, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.43]
• 40: Robert van Liere , Wim de Leeuw, GraphSplatting: Visualizing Graphs as Continuous Fields, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.206-212, April 2003 [doi>10.1109/TVCG.2003.1196007]
• 41: Xiaobo Wang , Isao Miyamoto, Generating Customized Layouts, Proceedings of the Symposium on Graph Drawing, p.504-515, September 20-22, 1995
• 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

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.8 Applications
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Keywords:
clustering, focus + context, force-directed methods, graph drawing, information visualization, program understanding, refactoring, reverse engineering, software visualization