A Customizable SVG Graph Visualization Engine

Keywords: SVG , graph editor , information visualization , software reverse engineering , program understanding

Yingyun Tony Lin
Master Student
University of Victoria
University of Victoria
Victoria
BC
Canada
gaoyun@uvic.ca

Biography

Yingyun Lin is a master student in Computer Science at the University of Victoria, Canada, where he is a member of Professor Müller's Rigi group.

Feng Zou
Master Student
University of Victoria
University of Victoria
Victoria
BC
Canada
fzou@uvic.ca

Biography

Feng Zou is a master student in Computer Science at the University of Victoria, Canada, where she is a member of Professor Müller's Rigi group.

Dr. Holger Kienle

University of Victoria
University of Victoria
Victoria
BC
Canada
kienle@cs.uvic.ca

Biography

Holger M. Kienle received a Ph.D. in Computer Science at the University of Victoria, Canada where he is now a postdoc. He received a Master of Science degree in Computer Science from University of Massachusetts Dartmouth and a Diploma in Informatics from University of Stuttgart, Germany. His research interests include software reverse engineering, program analyses, domain-specific languages, and autonomic computing.

Dr. Hausi Müller

University of Victoria
University of Victoria
Victoria
BC
Canada
hausi@cs.uvic.ca

Biography

Dr. Hausi Müller is a Professor in the Department of Computer Science and Director of Software Engineering Programs at the University of Victoria, British Columbia, Canada. He is a Visiting Scientist with the Center for Advanced Studies at the IBM Toronto Laboratory and the Carnegie Mellon Software Engineering Institute. He is a principal investigator and Chair of the Technical Steering Committee of CSER, a Canadian Consortium for Software Engineering Research. Together with his research group and in collaboration with IBM he investigates methods, models, architectures, and techniques for autonomic computing applications. He also concentrates on building Adoption-Centric Software Engineering (ACSE) tools and on migrating legacy software to autonomic and network-centric platforms.


Abstract


This paper describes our experience of creating an interactive and customizable graph visualization engine implemented entirely in SVG and ECMAScript. Typical operations of this visualization engine include filtering, searching, collapsing, expanding of graph elements, and hierarchical as well as historical viewing of graphs and subgraphs. We used the MVC design pattern as a cornerstone for the implementation of the graph editor. Also, this visualization engine has great potential because it runs on many platforms and in many applications due to the availability of SVG plug-ins. This paper discusses sample instantiations of our SVG Editor for the domains of reverse engineering of software and web sites and information modeling with the Eclipse Modeling Framework (EMF).


Table of Contents


1. Introduction
2. Background and Related Work
3. Structure And Functionality Of SVG Editor
     3.1 Main Window
     3.2 Menus
     3.3 History View
     3.4 Hierarchical View
4. Implementation
5. Sample Applications
     5.1 SVG Editor Eclipse Plug-in for EMF Model Visualization
     5.2 Graph Visualization of Three Different Viewpoints Used in REGoLive
6. Conclusions
7. Acknowledgements
Bibliography

1. Introduction

SVG, which stands for Scalable Vector Graphics, is a mature, open, platform-independent 2D vector graphics W3C standard and presentation integration platform with widespread browser, Commercial Off-the-Shelf (COTS) product (e.g., Visio), and tool support [1]. As an XML vocabulary, it enables deep data integration with other XML languages (e.g., XHTML) and makes for an ideal generation target. Most importantly, SVG has built-in support for scripting, enabling complex applications to be written and transmitted as an XML document to be displayed on many different platforms and host environments, including Web browsers and Office products (e.g., PowerPoint and Lotus Notes). SVG includes three types of graphics elements: vector graphics shapes, images and text. SVG contents can be animated either by defining animations with embedding SVG animation elements or via scripting and manipulating the Document Object Model API [1].

Most applications embody several information models at various levels of abstraction. Graphs, where nodes and arcs represent entities and relationships, respectively, are ideal for modeling many diverse information structures. A graph visualization engine can then be used to explore, manipulate and view the information contained in such an information model. End users of a graph visualization engine can be on different platforms; thus SVG as an open standard language is an ideal output format.

We have created a special-purpose graph editor implemented entirely in SVG and ECMAScript [2, 3], which is referred to as SVG graph visualization engine, or SVG Editor for short. This SVG Editor not only visualizes these elements, but also allows for the interactive exploration of entities (represented as nodes) and relationships between entities (represented as arcs). Typical operations include filtering and searching of nodes and arcs; collapsing and expanding of subsystem nodes; and hierarchical as well as historical viewing of graphs and subgraphs. Each instance of the SVG Editor embodies a specific information model combined with custom-tailored manipulation options accessible via menus or a command line. The end-user programming capability via command line and scripts adds significant extensibility and versatility [3].

2. Background and Related Work

The SVG Editor that we have developed is a reaction to the observation that many reverse engineering tools developed by academia do not address the document-centric nature of development and maintenance processes. Specifically, the results obtained with reverse engineering tools are difficult to integrate with other documents and once this is achieved it becomes difficult to update them to keep them in sync with other documents. For example, the result of reverse engineering tools can be often only preserved and integrated via taking static screenshots. In contrast, an instance of our SVG Editor can be seen as a document that is both embeddable and scriptable.

An earlier version of our SVG editor [3] was primarily static and did allow only limited interactions (e.g., filtering of nodes and arcs, and hiding of node names). The current version is fully interactive and has all the features expected of sophisticated graph editors.

When implementing the SVG Editor in ECMAScript, we have used the Rigi [4] graph editor as a reference tool, striving to realize a close superset of Rigi's functionality. The Rigi tool -- developed and maintained for over a decade, and used on several industrial projects -- has proven its usefulness for program comprehension and reverse engineering. A tool that implements similar functionality can be expected to be equally useful.

While the editor functionality is similar for both Rigi and the SVG Editor, the latter exhibits a number of interesting features that distinguish it from stand-alone graph editors. Editor functionality and visualization information can be packaged into a single file. As a result, there is no need for an extra installation procedure for our SVG Editor. New versions of the editor can be made available via re-creating the SVG graph file. The SVG Editor can be easily embedded into HTML documents. This allows, for example, to enhance design and maintenance documentation with sophisticated graphical views. Furthermore, readers of documentation can interactively manipulate these views. For example, a view might show a graph of the high-level architecture of a software system. Readers can then interactively filter, expand, and zoom into the graph as needed.

To the best of our knowledge, there are no other customizable graph editors implemented in SVG available at this point in time. SHriMP (Simple Hierarchical Multi-Perspective) is a tool designed for visualizing and exploring software architecture and many other information spaces [5]. This visualization tool is written in Java and provides sophisticated operations to visualize and manipulate graph structures. SHriMP can output SVG diagrams, but the graph is static and hence cannot be manipulated interactively.

The Graphical Editing Framework (GEF) allows Java developers to quickly create a rich graphical editor based on an existing application model [6]. It is the current graphical editing framework integrated into Eclipse. It is a general-purpose framework that can be customized for specific domains, and its diagrams can be exported in SVG format. However, customization requires the user to write copious amounts of code. Furthermore, the exported SVG diagrams are static: users can pan and zoom, but domain-specific actions (such as semantic zooming, filtering, and layouts) are unavailable.

3. Structure And Functionality Of SVG Editor

The SVG Editor has four main components: the main visualization window, menus, history views, and hierarchical views. Figure 1 depicts an instantiation of the SVG Editor for visualizing software structures. This instantiation depicts functionality that is comparable to the Rigi reverse engineering visualization tool [4].

./figure1.jpg

Figure 1: SVG Editor Instantiated to Visualize Software Structures

3.1 Main Window

The SVG Editor’s main window is a canvas located in the center of the view. Its main responsibility is to open and display directed graph (i.e., nodes and arcs) information. Nodes in software system graphs typically represent system components, such as subsystems, procedures, variables, calls, data accesses, and interfaces; and directed arcs represent dependencies among those components such as client-supplier, composition, and control and data-flow relations [3]. Different types of nodes and arcs are represented by distinct colors. For instance, the graph in Figure 1 has two node types (i.e., “Data” rendered in green and “Function” rendered in blue), and two arc types (i.e., function “calls” rendered in blue and “data” access rendered in red). The graph visualizes the static call structure and data access of a mid-size software system, a ray-tracer implemented in the programming language C.

The graph rendering takes full advantage of the benefits offered by SVG in combination with ECMAScript. First, the graph is zoomable. A user can zoom into any part of the graph without degradation. The view can be rendered in any resolution without loss of detail. Second, nodes in the graph are selectable and text and tag information of nodes and arcs is searchable. Search engines index SVG graphics according to the content of the diagram. Third, any objects in the main window are scriptable, which means that users can interact with the nodes and arcs effectively. Also, there are a number of event handlers such as “onmouseover” that are assigned to these graphical objects. This allows animation and manipulation of objects defined or triggered by user interactions [1].

3.2 Menus

There are two types of menus: on-screen menus and pop-up menus. On-screen menus are implemented in SVG and can be clicked on to affect an event. There are six groups of menus: filter by types, node selection, collapse and expand, customize, node information and exchange. The pop-up menu, which makes the editor easy to use, includes a number of functions provided by the Adobe SVG viewer, such as zoom in, zoom out, view source, save SVG as, and some functions provided by the SVG Editor such as node selection and a demo. Figure 2 depicts the pop-up menu.

./figure2.jpg

Figure 2: SVG Editor Pop-up Menu

3.3 History View

The history view provides a mechanism for saving different states in a sequence of graph manipulations. Theses saved states can easily be returned to by left-clicking on the snapshot of the state in the history view. Figure 3 depicts the history view window. Snapshots are numbered based on the history and displayed with their title. It is easy to add and remove a snapshot into the history view. History Views are often used to explore different paths in information exploration and to backtrack effectively.

./figure3.jpg

Figure 3: SVG Editor History View

3.4 Hierarchical View

A subsystem node may contain subgraphs (i.e., other nodes and arcs as children). By collapsing a group of nodes, we can create a subsystem node that has all of the previously selected nodes as its children at a lower level in the hierarchy. The SVG Editor provides operations to explore hierarchical views in the following way. When selecting a subsystem node and clicking on the hierarchical view on the menu, we can see the main window displaying the subsystem the node contains, the previous view is saved as a snapshot in the hierarchical view window, and the corresponding level is saved and displayed as the snapshot title. To traverse up the hierarchy, one has to click on the snapshot in the hierarchical view window and, as a result, the higher-level nodes and arcs will de displayed in the main window. Figure 4 depicts the hierarchical view window of a graph with two levels: the top right subsystem node at Level 1 contains the subgraph shown at Level 2.

./figure4.jpg

Figure 4: SVG Editor Hierarchical View

4. Implementation

This SVG Editor was implemented with about ten thousand lines of ECMAScript code. We used the MVC (Model View Controller) design pattern to implement the SVG Editor. MVC decomposes the architecture of our editor into three distinct parts:

Because of this separation of concerns, we can easily maintain multiple views with the same model. The SVG editor can display the state of the model in a variety of views, such as main view, history view, and hierarchical view. Also, it makes the entire program easier to implement, and easier to customize for different domains as well.

The graph component of the SVG Editor can be specialized for particular domains. For example, to visualize program structures for reverse engineering, specialized domains can be defined for different programming languages such as C or Java. Each domain has a set of appropriate node and arc types as well as node and arc attributes. In the SVG Editor, these aspects are expressed with so-called Domain objects. To customize the SVG Editor for visualizing, say, the high-level structure of C programs, the schema for the domain may be defined as follows: different node colors depict different types of data (in red) or functions (in green), arcs colors depict different types of dependencies: call (in yellow) and reference (in blue). The following code is used to create the domain:

			function createDomain() {	
			   var domain = new Domain("CProgram");	
			   var type = domain.addNodeType("Data");	
			   type.setAttribute("color", "red”);	
			   type = domain.addNodeType("Function");	
			   type.setAttribute("color", "green");		
			   type = domain.addArcType("Call");	
			   type.setAttribute("color", "yellow");	
			   type = domain.addArcType("Reference");	
			   type.setAttribute("color", "blue");	
			   return domain;		
			} 	
		

The following code snippet is used to create the model, and to populate it with nodes and arcs. Nodes and arcs have attributes such as type, name and source.

			function createGraph(graph) {
			   // create the model
			   var model = graph.getModel();
			   model.setDomain(createDomain());
			   var Node = model.getNodeHandler();
		   	   var Arc = model.getArcHandler();
			   // create nodes 
			   node1 = model.createNode("1", "Data");
			   Node.setAttributeibute(node1, "name", "ADT_list");
			   Node.setAttributeibute(node1, "sourcefile", "file:/list-d/src/");
			   Node2 = model.createNode("2", "Function ");
			   Node.setAttributeibute(node2, "name", "ADT_search");
			   Node.setAttributeibute(node2, "sourcefile", "file:/list-d/src/");
			   // create arcs 		
			   arc1001 = model.createArc("1001", "Call", node1, node2);
			   // ...
			}
		

Finally, the initial view of the graph can be obtained with the following code:

			   // create the view
			   graph.setBounds(1, 1, 755, 768);
			   var view = graph.view;
			   view.viewattrs.setAttribute("NODE_RADIUS", 9);
			   view.viewattrs.setAttribute("GRAPH_STYLE", "directed");
			   view.viewattrs.setAttribute("LABEL_BEHAVIOUR", "tooltip");
			   view.realize();
			   view.setViewbox(154, -51, 408, 614, "xMinYMin meet");
			   view.importModel();
			   var nodeview = view.nodeview;		
			   // set node locations
			   nodeview.setInitialLocation("1", 460, 300);
		

We have implemented an EventListenerManager as the Controller to keep track of event listeners, to notify registered listeners of changes in the model, and to modify the corresponding view.

5. Sample Applications

The SVG Editor can be customized to fit various domains. To illustrate the editor's customizability, we briefly discuss two sample applications of the SVG Editor.

5.1 SVG Editor Eclipse Plug-in for EMF Model Visualization

Eclipse is an open, universal tool platform that is designed to serve as the common basis for diverse IDE-based products [7]. A plug-in is a component that provides a certain type of service within the context of the Eclipse workbench.

The Eclipse Modeling Framework (EMF) is a modeling framework and code generator for building tools and applications according to a data model description [8]. EMF provides a simple interactive editor to define a model. Alternatively, the description of the model can be expressed as Java code stubs in combination with special Javadoc tags. An EMF model consists of a set of classes and associations between them. All EMF models adhere to a common meta-model, called Ecore. Once the model has been defined, Java code can be generated that supports the creation of instances of model elements, reading and writing of models, etc. Our Eclipse SVG Visualization Engine plug-in seamlessly integrates with the Eclipse platform. It generates a customized SVG Editor for EMF models by transforming an EMF model description into a suitable graph representation. In the SVG Editor, nodes represent packages, classes and methods, and arcs represent relationships such as inheritance and reference, as specified in the Ecore meta-model. Figure 5 depicts an instantiation of the SVG Editor generated by our plug-in. The graph is rendered within the Eclipse workbench with the help of an integrated Web browser (e.g., Internet Explorer).

./figure5.jpg

Figure 5: SVG Editor Generated by SVG Editor Eclipse Plug-in

5.2 Graph Visualization of Three Different Viewpoints Used in REGoLive

Many modern Web sites are highly complex software systems. They uniquely combine features found in databases, distributed systems, hypertext, and highly secure systems. Unfortunately, Web sites are often constructed and maintained in an ad hoc manner by developers that have little or no background in software engineering. As a result, many Web sites are difficult to understand and maintain.

REGoLive is a reverse engineering tool developed by Grace Gui of our research group. It supports comprehension of Web sites that have been developed with or can be read using Adobe’s GoLive product by offering three distinct viewpoints of the subject Web site: developer-view, server-view, and client-view [9,10]. REGoLive uses the SVG Editor to show each viewpoint, and also allows the reverse engineer to explore and navigate mappings between them.

Figure 6 shows a screenshot of the developer view of a sample Web site. Artifacts are visualized as nodes in the editor (e.g., blue nodes represent HTML pages, and yellow nodes represent GoLive templates). Relationships between artifacts are shown as arcs between nodes (e.g., a yellow arc from a blue node to a yellow node indicates that an HTML page makes use of a template) [9,10].

./figure6.jpg

Figure 6: SVG Editor Generated with the ReGoLive plug-in

6. Conclusions

This paper has introduced our implementation of a customizable graph editor implemented in SVG. The use of SVG for rendering graphs can take advantage of many features offered by SVG. Since SVG's encoding is XML-based, we can leverage XML technology for storage, parsing, and document transformation and querying. Thanks to the encoding of the graphs with vector graphics shapes, they are storage-efficient and zoomable without loss of quality. Furthermore, SVG documents can be rendered with different viewers on various platforms. Lastly, SVG documents can be made interactive with embedded scripting. This enabled us to realize a highly interactive graphical application with the use of scripting.

The customizability of the SVG Editor is exemplified in this paper with three different instantiations. The features of the SVG Editor have been explained with an instantiation for the visualization of software structures. This kind of visualization is used by reverse engineering tools to support program comprehension. Another, similar instantiation of the editor visualizes the structure of Web sites. Yet another instantiation supports the visualization of EMF models.

In the future, we plan to develop a customization framework to simplify the instantiation of the SVG Editor for a particular domain. We also plan to investigate interoperability mechanisms for seamlessly integrating the SVG graph visualization engine with several COTS products, including Microsoft Visio and Excel as well as Lotus Notes.

7. Acknowledgements

This work has been supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), the IBM Toronto Center for Advanced Studies (CAS), and the Consortium for Software Engineering (CSER). The first version of the interactive SVG Editor was developed by Jon Pipitone (University of Toronto).

Bibliography

[1]
Scalable Vector Graphics (SVG) 1.1 Specification. 2003 http://www.w3.org/TR/SVG/
[2]
H.A. Müller, A. Weber, H.M. Kienle, Leveraging Cognitive Support in SVG Applications from the Host COTS Product. Second Annual Conference on Scalable Vector Graphics (SVG Open 2003), Vancouver, BC, Canada, July 13-18, 2003.
[3]
H.M. Kienle, A. Weber, H.A. Müller, Leveraging SVG in the Rigi Reverse Engineering Tool. First Annual Conference on Scalable Vector Graphics (SVG Open 2002) and Carto.net Developers Conference, Zürich, Switzerland, July 15-17, 2002.
[4]
H.A. Müller, K. Klashinsky, Rigi.--A System for Reverse Engineering. Proceedings of 10th IEEE International Conference on Software Engineering (ICSE 88), pp. 80-86, Raffles City, Singapore, April 11-15, 1988.
[5]
H.A. Müller, M.-A. Storey, Manipulating and Documenting Software Structures using SHriMP Views. Proceedings of IEEE International Conference on Software Maintenance (ICSM-95), pp. 275-284, Opio (Nice), France, October 16-20, 1995.
[6]
Graphical Editing Framework (GEF). http://www.eclipse.org/gef/
[7]
Eclipse Technical Platform Overview. http://www.eclipse.org/
[8]
Eclipse Modeling Framework Project (EMF). http://www.eclipse.org/emf/
[9]
G. Gui, H.M. Kienle, H.A. Müller, REGoLive: Web Site Comprehension with Viewpoints. Proceedings of 13th IEEE International Workshop on Program Comprehension (IWPC 2005), pp. 161-164, St. Louis, Missouri, USA, May 15-16, 2005.
[10]
G. Gui, H.M. Kienle, H.A. Müller, ReGoLive: Building a Web Site Comprehension Tool by Extending GoLive. Proceedings of IEEE International Conference on Web Site Evolution (WSE 2005), pp. 46-56, Budapest, Hungary, September 26, 2005.

XHTML rendition made possible by SchemaSoft's Document Interpreter™ technology.