Visualisation Research Group
Centre for Software Maintenance
Department of Computer Science
University of Durham
18 June, 1996
It is a widely known fact that software maintenance is considered the most costly activity in the software life-cycle, both in time and money [Standish84]. Regardless of the maintenance task being performed, it is highly likely that the maintainer will require at least some understanding of the code. This understanding often comes from a hard fought battle in which the maintainer must attempt to rediscover the intentions and design issues behind the code, typically from scarce resources and in the worst case from the source code alone. For this reason program comprehension is generally accepted as being the central task within software maintenance. Tool support for software maintenance typically targets this task as it offers the best opportunity for efficiency gain. Good computer support and tools which aid the software maintenance process through program comprehension would be of great value. Unfortunately good tools are hard to find and most, while still aiding comprehension to some extent, could be improved greatly.
One area of research which attempts to aid program comprehension and more generally software maintenance is software visualisation. Software visualisation makes use of the fact that the human brain is more suited to processing, manipulating and recognising visual images and structures. Reading of text is a special case of this visual processing, however this is translated or interpreted at a character or possibly word level. Such detail is too great and the brain will abstract each character, word or sentence into an internal meaning or representation. This is described in the program comprehension literature at a higher level, for example beacons [Brooks83] and chunks [Shneiderman80] are abstract internal representations of low-level textual structures.
Software visualisation attempts to aid the comprehension process by providing these abstractions in a visual form, thus reducing the interpretation load. By presenting the viewer with a pictorial model of more complex lower level information, they can rapidly generate an initial mental model of the software and use this as a basis for further investigation. Software visualisation is concerned with all areas of generating and manipulating these graphical models. In particular, some of the main problems which must be tackled are:
This document reviews a section of the literature regarding software visualisation and highlights specific points of interest. The first point addressed is the definition of the terms related to the field, and in particular the definition of software visualisation itself. Following this, the role software visualisation plays within software maintenance and program comprehension is discussed and the need for software visualisation is highlighted. A review of the current state of research in software visualisation, including the various systems developed is then given. This includes an introduction to the more specific area of three-dimensional software visualisation, which is followed by a detailed review of current systems utilising 3D graphics.
Software visualisation is still not a well defined term and lacks any concrete definition or meaning. Many researchers have tried to define the term, though the majority of these definitions contradict one another or offer varying levels of detail, scope and abstraction. At present the term is generally used to encompass almost all forms of visualisation concerned with representing any aspect of a software system. A number of more specialised areas have evolved under the guise of software visualisation, areas such as algorithm animation, data visualisation and code visualisation. These areas are also subject to varying definitions and scope of field. To compound matters, the actual term software visualisation is often used as being synonymous to program visualisation, computation visualisation and code visualisation.
A vast number of definitions and descriptions related to software visualisation are given in the literature, a large selection of these are now given. This list is intentionally long, to illustrate the variety of definitions and interpretations offered.
It can be seen from the above definitions and descriptions that the field of software visualisation is diverse, with research interests in many different directions. One commonality evident in the majority of definitions is the emphasis on visual representations. The term software visualisation or program visualisation is generally read as incorporating exclusively graphic representations. This, however, is misleading and overly restrictive. Software visualisation should allow for representations other than graphical. It is not unreasonable to foresee visualisation tools which make use of the other available human senses, in particular hearing, smell and touch. Price et al. redefine their use of the term visualisation to include such flexibility, as "the power or process of forming a mental picture or vision of something not actually present to the sight" [Price93].
One of the major differences between definitions such as those given above, is their specificity. Almost all of the definitions and descriptions are too specific in one point or another. Some definitions imply that visualisation must incorporate solely graphics or a particular media, whereas others state the use of specific techniques or systems. However, introducing too much generality will bring the term very close to the field of program comprehension. For instance, the definition "software visualisation is the use of visual (and other) media to aid understanding of software systems" could be construed as another definition for program comprehension given the flexibility of the "other media".
Identifying the position of software visualisation with respect to other fields, and more specific sub-fields has been suggested by a large number of authors [Price93, Stasko92a, Stasko92b, Myers90]. Price et al. [Price93] view software visualisation as a field which encompasses the two distinct areas of program visualisation (including visual programming) and algorithm animation. Stasko [Stasko92a] proposes the field of computation visualisation which includes both software and hardware views. Fields encompassed by the topic of software visualisation are identified by Price et al. resulting in the structure shown in Figure 1. This structure does, however, pose some questions.
Visual programming, as defined by Roman and Cox, is "concerned with graphical specification of computer programs" [Roman92] and does not apply to the current onslaught of so-called visual languages such as Visual C++, Visual Basic, VisualAge and Visual Objects. These systems provide little more than a unified GUI (graphical user interface) to conventional program development tools [Najork95]. Price et al. identify the term program visualisation as including the field of visual programming. This notion is in contradiction to other views which consider program visualisation and visual programming as disparate fields [Roman93, Myers90]. Myers even states, "Program Visualisation is an entirely different concept from visual programming" [Myers90]. Conversely, it is not unreasonable to argue that in order to create a visual programming environment, you must first be able to visualise programs, hence program visualisation. This argument is open to interpretation, however in the classification by Price et al., the field of algorithm animation is not included as part of program visualisation. It seems unreasonable to make such a distinction in one case and not in the other.
Further, Price et al. describe program visualisation as being composed of both static and dynamic code and data visualisations, whereas visual programming is concerned only with static visualisations. Again, this point is open to debate. While visual programming is concerned with the creation or visual implementation of programs, this process may not be restricted purely to static visualisations. One simple argument is that debugging and tracing of code is considered an integral part of programming, and in a visual sense the only way in which the execution or tracing can be presented is through animated visualisations. Another argument is that we cannot constrain the visual programming paradigm to purely static or even graphic visualisations. A visual programming-by-example paradigm could be imagined in which the programmer specifies operations by manipulating the graphical interface in a dynamic fashion; by providing an example. An example could be copying or moving data within memory, this being achieved by dragging or moving appropriate areas within the visualisation.
The arguments posed above offer constructive criticism to the classification of definitions within software visualisation. The validity of these arguments does however hinge upon the readers' interpretation of the terms and their scope. Figure 1 above illustrates the scope of these terms as described by Price et al. Similarly, Figure 2 below shows a revised classification of these terms which incorporates the arguments mentioned above. In addition to the field of software visualisation, the term computation visualisation is introduced by Stasko [Stasko92a] as including both software and hardware views. This is incorporated in Figure 2.
A brief description of each of these fields is now given.
Several taxonomies have been applied to software visualisation systems, again these vary to the same extent as the definitions. There are two taxonomies which are predominant in the field, an earlier taxonomy by Myers [Myers90] and a more recent taxonomy by Price et al. [Price93]. Myers' taxonomy classifies systems along two main axes: the data they present, such as code, data or algorithm visualisations; and whether the visualisations are dynamic or static. While this taxonomy covers some of the important characteristics of a software visualisation system, it does not provide any scope for evaluating the effectiveness, usability, applicability or quality of systems. This is addressed to a greater extent in the taxonomy by Price et al.
Price et al. categorise systems in a more systematic manner and attempt to structure the taxonomy to allow flexibility for future expansion and revision. Their taxonomy is based upon a hierarchical structure of classifications which allows simple addition of new categories. The top level of this hierarchy is based on a very general model of software containing six categories: Scope; content; form; method; interaction; and effectiveness.
Other taxonomies exist, again using a different set of classifications. One such taxonomy is by Stasko and Patterson [Stasko92b] which introduces scaled dimensions into a four-category taxonomy. These categories cover aspect, abstractness, animation and automation. Another such taxonomy by Roman and Cox [Roman92] initially identified systems using the categories of scope, abstraction, specification method and technique. This initial taxonomy was refined further [Roman93] with the category "technique" being replaced with the two categories of interface and presentation. They view this visualisation as a mapping from programs to graphical representations [Roman92], with the categories of the taxonomy representing aspects of this mapping. The scope covers what aspects of the program are visualised. Abstraction and specification method cover the actual visualisation process; what information is conveyed and how it is constructed. Finally, interface and presentation (technique in earlier work) cover the actual graphical representation; how it is used to convey the information.
It is an acknowledged fact that software maintenance consumes the majority of resources within the software life-cycle. It is also a well known fact that program comprehension plays the major role in any maintenance activity. Whether the activity is adaptive, perfective, preventative or corrective, all require an understanding of the software system to some extent. The task of gaining this understanding falls under the broad scope of program comprehension.
Problems and deficiencies within the software development process result in software systems which are typically badly designed, badly implemented, and possibly worst of all, badly documented. Flaws in design and implementation do cause problems, however if these flaws or processes are correctly documented then steps can be taken to correct or work around them. However, if the documentation is lacking in any respect then such flaws can go unnoticed and cause severe difficulties during maintenance. Even well designed and implemented code can prove a problem if not correctly documented. Maintainers must then attempt to discover the design intentions behind the implemented system, in the worst case from the source code alone.
Unfortunately, problems with system documentation are widespread. Time constraints imposed upon projects often result in rushed implementations, with documentation receiving a low priority. As a result, documentation is often non-existent, incomplete, inaccurate, or worst of all, misleading. Thus, program comprehension is often limited to discovering an understanding of a system from the source code and any scant documentation. The various theories of program comprehension put emphasis on the construction of a mental model of the software within the mind of the maintainer [Young96a]. Theories on the construction of this mental model hypothesise various techniques employed by maintainers in extracting information from the program source code. Software visualisation attempts to provide tool support for generating this mental model or understanding.
The mental models proposed by various researchers in the field of program comprehension [Young96a] have a commonality in that they all are composed from semantic constructs. These constructs are typically abstractions, at various levels, of program features. The network formed from these constructs constitutes the maintainers understanding and representation of the program. Software visualisation attempts to provide a mapping from the program code to a visual (and other media) representation which matches the maintainer's mental model as closely as possible. Highlighting and automatically creating these semantic constructs would remove a great deal of effort from the maintainer, specifically they would require less time spent on scanning the source code. The field of software visualisation is thus considered an important area of research within the general field of program comprehension.
Roman and Cox [Roman92] highlight a number of arguments which are used generally in advocating the need for software visualisation. These arguments include: the importance of imagery in human communication; the speed with which humans can track and identify visual patterns; the expressive potential of a visual vocabulary which exploits multiple dimensions; and the inherent power of abstraction within visual representations. The credibility of such arguments are often underlined with reference to the success of graphical representations in areas such as human computer interfaces, scientific data visualisation and information visualisation.
Current research into software visualisation is diverse, with activity in all areas of the subject. Initially the main research thrust was developing algorithm visualisation frameworks and systems. These systems were used predominantly for teaching algorithm design and analysis and were not typically used as general purpose tools. Another favourite topic in software visualisation is its application to program debugging and execution tracing, particularly within imperative languages. More recently, an increase in research has been directed towards structural or macroscopic visualisations of code. These visualisations concentrate on a large scale view of the code and typical examples are function call graphs, control flow graphs and file dependencies. In addition, there is a very active research interest in the visualisation of parallel programs, though generally concentrating on their execution behaviour [PVMTrace95, Koike95, Miller93, Kraemer93].
Algorithm visualisation research concentrates on producing meaningful and insightful visualisations and animations to aid understanding of algorithm operation. Generally these visualisations are not produced automatically and require an animator to design a suitable representation for each algorithm. The majority of algorithm animation frameworks created rely on the animator to instrument the algorithm implementation at critical points with additional calls to the animation environment or to a log file generator. This information is then used either during execution or post-mortem, respectively, to drive the animation. Many systems have been developed for algorithm animation, a large number of which are described in the various taxonomies [Price93, Myers90, Roman93]. Such systems include: BALSA; Balsa-II; Zeus; TANGO; Polka-3D; and ANIM.
Visual debugging, is not generally accepted as a separate topic of program visualisation though there are a large number of systems which use visualisation as a primary aid to debugging. Many of these systems are confined to tracing the execution of imperative languages, however various other languages and paradigms are also covered. The majority of these systems operate automatically, i.e. they do not need manual intervention to obtain the program information. This is generally obtained using either of two methods. One method provides an interpreter base in which the target program is 'executed' thus allowing the visualiser access to all information regarding the program and its execution. Alternatively the visualiser will automatically instrument the target source code with calls to the visualiser, or with statements which output information to a log file for post-mortem analysis. Again, these systems are described and classified within the various taxonomies. Such systems include: Pascal Genie; UWPI; TPM; Pavane; LogoMedia; CentreLine ObjectCentre (Saber-C++); ZStep 94 [Lieberman95, Fry95]; and PVMTrace.
Structural visualisations concentrate mainly on large scale or macroscopic views of the source code. These views typically consist of visualising dependencies between the various components that make up a software system. Components such as variables, classes, functions, methods, files and modules are displayed to produce the stereotypical views of call-graphs, control-flow graphs, module dependencies and data dependencies. The key factor of these views being their inherent graph structure. These graphs are often very large and difficult to display effectively. Such systems are not covered in current taxonomies, though they should easily be incorporated by the various taxonomic criteria. Examples of these systems include: SMARTsystem; McCabe; Logiscope [Meekel88]; SNiFF; Rigi [Storey95]; Narcissus [Hendley95]; GraphLog [Consens92]; SemNet [Fairchild88]; and GraphVisualiser3D [GV3D95].
The majority of software visualisation systems to date have concentrated on producing two dimensional representations and animations of various aspects of a software system. In addition, a growing area of research is investigating the application of 3D graphics and virtual environment technology to software visualisation. Research into 3D software visualisation attempts to address the problem both in terms of the data to represent and the users' ability to navigate this data. The former aspect stems from a growing need for more expressive powers to represent the inherently multi-dimensional data, facts and relationships which constitute a software system. The latter plays upon the naturally developed capabilities of humans for navigating and interacting within three dimensional environments.
Software systems, and in particular the large, highly inter-related information bases that they constitute, are inherently multi-dimensional and thus difficult to visualise [Brooks87]. Software visualisation systems typically isolate one aspect or view of this information for display, effectively hiding all remaining information from view. This isolated view generally consists of a large and complex directed graph which is displayed on a two dimensional canvas using one of the many layout algorithms developed within the field of graph layout. Regardless of the quality of the layout algorithm or viewing technique (such as fisheye) used, the user is typically presented with an incomprehensible birds-nest graph or must reduce the amount of information displayed thus removing potentially important information from view [Fairchild88]. While the use of 3D or virtual environment technology cannot immediately solve this problem, it does offer a number of advantages such as: greater working volume for information presentation; focus, context and point of interest are managed dynamically by the user's viewpoint on the information; and greater flexibility with representation, organisation and presentation of the information. These arguments do not in themselves justify 3D as superior to 2D representations, however they do highlight possibilities for advances in software visualisation using 3D graphics.
Although the full potential of using three dimensional views and interaction techniques has not yet been realised, a number of software systems have been developed to investigate its worth. In general, these systems do not make full use of the 3D graphics or advance software visualisation to any great extent. The majority simply extend and adapt already established two dimensional visualisation techniques into 3D [Brown93, Reiss94]. An example of this is highlighted by Brown and Najork [Brown93] who describe a variety of 3D graphics techniques for algorithm animation. They describe three fundamental uses of 3D:
These techniques take little advantage of the additional dimension and merely offer 'window dressing' on existing techniques. They do, however, provide useful additional information such as the execution history or extended attributes, though these could be facilitated in other ways such as animation or annotations, respectively. Similarly, 3D structural visualisation systems offer simple extensions of 2D graph techniques into 3D.
This section now describes a number of 3D software visualisation systems, varying from algorithm to structural visualisations.
Zeus forms the latest in a series of algorithm animation systems developed at Brown University and the Digital Equipment Corporation (DEC). BALSA and BALSA-II were considered as the first major interactive software visualisation systems. This early system (BALSA) was used widely as an aid to teaching algorithm design and analysis and allowed students to interactively view animations prepared by a lecturer. Functions such as stop, play, pause, speed control and direction control were provided. Zeus offered a number of enhancements over these earlier systems in particular the use of colour, sound, and more interestingly, of 3D graphics.
Brown and Najork [Brown93] describe a variety of 3D graphics techniques for algorithm animation. These techniques are highlighted by examples created using Zeus. Constructing animations within Zeus relies on the animator identifying critical areas within the algorithm code, such as data manipulation, conditional evaluation or procedure calls. These areas are then instrumented with calls to the Zeus "interesting event" manager. During execution of the algorithm these interesting events will be reported to Zeus, which will then forward them on to any interested views. The views must be predefined and designed to respond appropriately to events in the code. During the visualisation the user is still able to alter various aspects of a view by changing its associated control panel. This allows both generic parameters, such as lighting level, and view-specific parameters to be changed.
PVMTrace [PVMTrace95] is a project underway at the University of New Brunswick which is concerned with the visualisation of parallel processes with an emphasis on debugging (Figure 3). Understanding and debugging complex sequential programs is often very difficult, this problem grows drastically when trying to understand the execution of communicating parallel processes. There is a need for good tools to aid the understanding of such programs and visualisation promises to provide an effective communication medium between the execution data and the programmer.
PVMTrace will concentrate on visualising parallel programs which are running on PVM. PVM is a library which simulates a parallel computer by running processes on multiple workstations in a network. The project will investigate different visualisations and representations for presenting the execution of parallel processes and messages between them. Particular attention will be given to the application of three dimensional animated visualisations.
VOGUE is a visualisation system developed at Koike Labs, which provides a framework for creating 3D software visualisations. VOGUE concentrates on the concept of integrating a number of 2D views to create a more powerful 3D visualisation. This system has been applied in a number of different visualisation scenarios:
VOGUE is used in creating a 3D visualisation which integrates version control and module management (Figure 4(a)). The visualisation creates a two dimensional tree from the module dependencies at each revision. This set of 2D trees are then placed in series along the Z axis of the display space, with the most recent revision placed at the front. Relationships between source code modules are visible both between different versions of the same module through time, and as compilation dependencies between modules for each revision.
The 3D class library browser implemented using VOGUE integrates two sets of information concerned with class inheritance hierarchies (Figure 4(b)). The first set concerns the actual inheritance hierarchy and depicts which classes are derived from other classes. The second set of information shows which methods belong to particular classes. These two sets are integrated into a single 3D visualisation to provide immediate indication of which method is actually executed when called from any particular class. By shifting viewpoint orientation the programmer can obtain a display of either data set, or view both sets and any dependencies between them. This clarifies the problem by reducing the need to mentally integrate both sets of information.
VisuaLinda is a program visualisation system developed at Koike Labs which uses 3D visualisations to clarify the operation of parallel programs [Koike95]. VisuaLinda is built upon the VOGUE visualisation system, also developed at Koike Labs.
Linda is best described as a co-ordination language and not a complete language [Gelernter92]. Such a co-ordination language would be integrated with a computational language to create a complete programming language. Linda allows the co-ordination of processes through the use of a shared tuple space. VisuaLinda is both a visualisation tool for parallel Linda programs, and a Linda server itself. This affords a number of advantages, the most noteworthy being that no code instrumentation is required to produce the visualisations, as this can be handled transparently by the server.
VisuaLinda makes use of 3D graphics to visualise the execution of parallel processes (Figure 5). This allows the programmers to view both the relationships between processes and a time flow of the processes simultaneously.
SemNet [Fairchild88] is a research prototype developed to advance understanding of the complex relationships and structures of large, arbitrary knowledge bases (Figure 6). The aim of SemNet was not to provide a solution for this general problem, but rather to explore the application of 3D visualisation techniques and to investigate the specifics of the problem. The main problem addressed by SemNet is how to present large knowledge bases to enable improved or more efficient comprehension. Fairchild and Poltrock hypothesise that for comprehension of a knowledge base, a user must recognise:
Knowledge bases represent information about relationships between objects or records. Fairchild and Poltrock believe that graphical representations offer an effective way of communicating such relationships. This coupled with the high level of visual processing and spatial reasoning capable in the human brain, makes 3D representations a good candidate for such a task.
Fairchild and Poltrock are quick to point out that simply using a graphical representation does not immediately solve the problems inherent with exploring, manipulating, understanding and modifying large knowledge bases. Very large knowledge bases become very large directed graphs! This highlights an important need for reducing the visual complexity of the graphical representations, a need which is also addressed in SemNet.
Graph layout and information hiding within SemNet is debated by Fairchild and Poltrock. A number of methods are described with their advantages and disadvantages noted. The authors agree that the positioning of knowledge elements within the visualisation can greatly affect comprehension of the knowledge base structure. Layout of the visualisation in SemNet can be performed using one of two methods:
Information hiding in SemNet is provided both by the inherent perspective based reduction in detail due to distancing in the 3D display, and also by application of additional fish-eye techniques. The former method is apparent if proximity-based positioning has been used, thus objects which are unrelated to the current interest will be further from the viewpoint, hence reduced in detail and size. This provides a fish-eye view based purely on three-dimensional perspective. This was combined with a cluster based fish-eye view which attempted to reduce the complexity of the graph while still maintaining the context of the overall structure. This technique assigns elements within similar areas of 3D space to clusters, with neighbouring clusters being assigned to higher level clusters. The technique is similar to the nested graphs of Harel [Harel88]. Using these clusters, only knowledge elements close the viewpoint are displayed individually, at further distances only the clusters are visible.
A definite similarity is evident between the structure of large knowledge bases and the structure of software systems. Software systems can be considered as large, complex knowledge or fact databases consisting of many related components. Ideas of comprehension and visualisation of knowledge bases should be applied relatively easily to the problems of software visualisation. There is already a great deal of active research in the field of information visualisation, and more recently investigating the application of 3D graphics and virtual environment technology [Young96b]. It should be possible to advance 3D software visualisations using ideas applied in the fields of 3D information visualisation, graph layout and virtual environment design.
GraphVisualizer3D (GV3D) [Ware93, GV3D95] is a research project under development at the University of New Brunswick (Figure 7, a-d). The aim of GV3D is to utilise 3D visualisations and virtual environment technology to provide a more readable and comprehensible graph visualisation. The project is aimed at displaying predominantly directed graphs, though the focus of the development has been to visualise software structures. The structures in this case are component relationships within object oriented C++ programs, examples cited are: software module dependencies; software usage; and inheritance relations. Ware et al. [Ware93] describe the design issues and architecture of GV3D and include details of empirical evaluations performed on the system, which include an investigation into various interfaces and interaction techniques.
Ware et al. investigate the use of a number of different interaction techniques both for inclusion in the GV3D project [Ware93] and also as a separate study [Ware94]. The study evaluated the occurrence of errors in a graph comprehension task in which the users were restricted to using a number of different interaction techniques. The results of the study highlight an important decrease in errors, thus an increase in graph cognition, when a combination of stereoscopic display and viewpoint manipulation techniques are used. The study also confirmed previous research which indicated that the use of viewpoint manipulation alone was more effective than a stereoscopic display alone. These results indicate the importance of the virtual environment interface in producing useable and useful visualisations.
GV3D draws on a number of ideas from SemNet and is hinged upon the same concepts, however GV3D aims to improve upon SemNet in a number of ways. One area of divergence is a shift from the predominantly automatic node placement of SemNet to the more manual oriented placement of GV3D. Ware et. al believe that the most important heuristic for graph layout is semantic clustering, that is grouping nodes with respect to their semantic meaning as opposed to their position within the graph structure. They state that it is unreasonable to expect current layout algorithms to achieve more than a first approximation to the layout of software entities in space. The reason being that good layout is based greatly upon the high level semantics of the nodes, this cannot be formalised or automated at present. The graph layout used in GV3D is based upon elementary layout algorithms but supplemented by extensive manipulation and interaction techniques.
Similar to SemNet, GV3D also includes the notion of composite nodes and arcs [Harel88]. This technique allows reduction of the visual complexity of a graph structure by representing similar nodes and arcs as a single composite node or arc (the measure of similarity is arbitrary). These composite nodes can then be collapsed or expanded (opened or closed) as needed, depending on the focus of the viewer. GV3D copes with composite nodes by performing an identical layout on the sub-graph enclosed in the composite node. The composite node is then scaled to completely enclose the sub-graph, for this reason the node size cannot be used to display attributes. Opening or expanding a node results in the contents being displayed.
Input to GV3D is provided via a proprietary Graph Description Language (GDL). This language allows the permanent storage of graph structure, visual representation and layout information. Graph structures to be visualised, such as the C++ software components, must first be converted to the GDL format. Interaction with the GV3D visualisations is provided by two main methods, both of which use a standard high-resolution monitor for display. The viewer can use the monitor alone, making use of 3D Widgets to control position and velocity along each of the co-ordinate axes. Alternatively the viewer can also use a head tracked stereoscopic display. This provides the viewer with a stereo display and also allows head movement to manipulate the viewpoint thus providing essential perceptive cues which greatly aid depth perception and object recognition.
A number of prototype software visualisation systems have been produced which investigate using 3D to provide a structural overview of software. This structural overview typically involves visualising the dependencies between software components as a (generally large) directed graph. Layout of such a graph is non-trivial and two dimensional representations very rapidly become an unreadable mess. One approach adopted by several research systems is to use a force directed placement (FDP) algorithm to perform the layout. This algorithm was originally applied to 2D graph layout, however extensions to 3D have shown a great deal of promise. The use of 3D in such a case is justified solely by providing a greater working volume for the graph layout. This increase in available space does not solve the problem of performing layout on large graphs, it merely increases the graph size limit.
The FDP algorithm [Young96b, Fruchterman91] is a simple, yet effective technique of modelling the graph structure as a physical system. There are countless variations on this theme including various models for the system, such as simulated annealing. One simple FDP algorithm models the nodes of the graph as having a repulsive force, with nodes repelling one another. The magnitude of this repulsive force increases as nodes are brought closer together. To maintain an equilibrium in the graph, the arcs between nodes are modelled as imparting an attractive force between the nodes they connect. This attractive force is typically proportional to the length of the arc and exhibits similar behaviour to a spring. The initial graph layout will generally have the system in a state of high energy. After a number of iterations the nodes will reorganise themselves in an attempt to achieve a minimum energy state. On achieving this state, the layout will be optimised for arc length and node spacing, though this does not necessarily mean a clear or understandable graph.
A number of research systems have been developed using the FDP algorithm to produce 3D graph layouts. A few of these systems are described briefly here.
Narcissus [Hendley95] is an information visualisation system developed at the University of Birmingham for creating 3D visualisations of large directed graph structures. Specifically, Narcissus was aimed towards visualising dependencies between components in a software system, but was closely related to work on a system called Hyperspace which aimed at visualising collections of hypertext documents. The visualisations in Narcissus are created as wire-frame 3D graphs with the software components represented as spherical nodes, and the dependencies as directed arcs. Layout of the graph is performed using a force directed placement algorithm which runs continuously meaning that new nodes introduced will move immediately towards their equilibrium point.
SHriMP (Simple Hierarchical Multi-Perspective views) [Storey95] is a tool for visualising large graphs, in particular for visualising component dependencies within software systems. SHriMP is incorporated within the Rigi reverse engineering system and aims to provide an overview of software structure allowing both detailed and high-level visualisations while still maintaining a notion of position or context within the complete graph structure. SHriMP makes use of two techniques, nested graphs [Harel88] and fisheye views to provide both abstraction and focusing of detail as necessary.
An FDP based source code visualiser was developed by Kings [Kings95] at British Telecomm. The system took facts extracted from C source code using a proprietary code analysis tool and produced a three dimensional graph structure of these facts and their relations. The visualiser is implemented as a set of utilities or tools rather than a single program. It makes use of other available applications such as the Mosaic WWW browser for fetching files from a central server.
Zebedee is another FDP based 3D graph layout tool. It takes a proprietary graph file as input and produces a 3D layout within a virtual reality system (Figure 8). Graph structures to be visualised, such as program information, are first converted to this file format. This allows for greater flexibility using small, task specific conversion tools. Zebedee has been applied to visualising software as both control flow and function call hierarchies. One feature of Zebedee enables nodes to placed into tiers and constrained to moving only within that tier. This forces a hierarchy upon the graph structure and preserves a more organised and meaningful appearance. Zebedee has also been integrated into a WWW tool using the Netscape Navigator browser. This allows limited interaction between other code, visualisation and documentation views.
This report has described the current state of the art in software visualisation, and in particular the rapidly developing field of 3D software visualisation. A number of 3D software visualisation systems have also been described in order to illustrate the direction in which the research is heading. Particular attention has been paid to the definition of software visualisation and related topics; to it's application to software maintenance; and to the current state and direction of research effort. There are a number of conclusions which can be made:
Regardless of the above comments, it seems safe to assume that research and interest into software visualisation will continue to grow. As hardware technology improves and prices continue to fall, the overheads of creating visualisations will become less of a concern. Software visualisation has great potential to provide useful, time saving support to the software maintenance (and possibly development) process. Whether or not this potential is realised remains uncertain, though the deciding factor will undoubtedly be it's acceptance by industry.
This page is maintained by Peter Young, please send any comments, jokes,
insults or general abuse to (email@example.com).
Last updated: Monday 1 July, 1996.